【拾题杂谈】POJ3321 Apple Tree
题面大秦 为你打开 题目传送门
题目翻译给定一个包含N个结点的苹果树，结点从1到N编号，树根为1。
苹果会长在某些结点上，但是两个苹果不会同时长在一个结点上。
随着时间的推移，苹果会被摘走，或者某些结点又长出新苹果。
现在我们想知道在某个时刻某个子树中有多少苹果。
思路首先不难想到用线段树（当然也可以树状数组），在树上的线段树问题一般都得用 Dfs 序或者树链剖分把他们化作区间上的问题解决。而这道题特别简单，没有大的需求用树链剖分，这里使用Dfs序，所谓Dfs序，就是记录他第一次被访问，和最后一次被访问的位置，这样就转化成了区间，而且这样这个区间可以包含他的整个子树。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106 ...
【算法模板】线段树区间修改区间查询求和
解释出门右转 线段树博文 谢谢
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct Node { int L, R; ll num, lazy; Node() {} Node(int L, int R, ll num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), num + you.num); }};class SegTree { private : Node node[N << 2]; public : void Add(int p, ll v) ...
【算法模板】线段树区间修改区间查询最小值
解释出门右转 线段树博文 谢谢
附：Add函数里面加 v 是因为我们最小值统计的只是一个元素。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct Node { int L, R; ll num, lazy; Node() {} Node(int L, int R, ll num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), min(num, you.num)); }};class SegTree { private : Node node[N << 2]; public ...
【算法模板】线段树单点修改区间查询最小值
解释出门右转 线段树博文 谢谢
这个真的没什么好说，，，，太简单了
123456789101112131415161718192021222324252627282930313233343536373839404142434445struct Node { int L, R; long long num; Node() {} Node(int L, int R, long long num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), min(num, you.num)); }};class SegTree { private : Node node[N << 2]; public : void Build(int p, in ...
即刻测试
原神蒸蒸日上！
【算法介绍】欧几里得算法
算法简介：时间 与 智慧欧几里得算法，简称 $\gcd$ ，常用的是辗转相减或辗转相除，是一个远古时期就被前人证明出来的算法。还有就是拓展欧几里得算法简称 $\tt exgcd$ ，是一个基于欧几里得算法用于求解 $Ax+By=C$ 方程的算法。非常的玄学，接下来会讲讲关于这些算法的流程代码以及复杂度分析。
算法演示：影照浮世风流欧几里得算法：旧语新知 · 记忆中的沙丘欧几里得算法，就是中国的辗转相减或辗转相除，本质上是让两个数不断地大数减小数（或者是用小数模大数），最后求出最大公约数，那么为什么会是这样呢？看如下证明
设一个 $a, b, c$ 分别表示 $\gcd(a,b) = \gcd(b,c)$ 这样一个式子的一部分，令他们三满足关系 $a=b\times q_0+c$（ $a$ 除以 $b$ 的余数是 $c$ ）如果 $b,c$ 有一个公因子 $q_1$ ，则这两个数可以有如下表示方法：
b=k_0\times q_1,c=k_1\times q_1将其带入式子 $a = b\times q_0 + c$ ，可得：
\begin{align}
a&=b ...
【算法介绍】素数筛法
算法简介：骑士团长的一日假期素数筛法是作为数论基础而出现的。数论本质上是对数字的一些性质的研究，而质数是这里很重要的一部分。不同的质数筛有着不同的特性，用来解决不同的题目，接下来我们会大概了解几种。
算法演示：若困你于无风之地$O(\sqrt n)$ 判断单个质数这个很简单，由于考虑到因子是一对一对的，所以一对因数中较小的那一个最多最多是 $\sqrt n$ ，也就是说我们只需要枚举 $2$ ~ $\sqrt n$ 复杂度 $O(\sqrt n)$ ，不枚举 $1$ 是因为所有数字都是 1 的倍数，素数也只是被 $1$ 和它本身整除。
1234567bool isPrime(int x) { if(x <= 1) return false; for(int i = 2; i * i <= n; i++) { if(x % i == 0) return false; // 找到一个不是 1 也不是它本身的因子 } return true;}
$O(n\log\log n)$ 多个快筛这个就属于新开一 ...
【拾题杂谈】517八段第二课F
题面题目链接大秦 为你打开 题目传送门
备用题面一个无向图中有n顶点和m条边，无重边无自环。顶点从1到n编号。
Q次询问，每次询问u,vu,v之间是否存在一条长度为奇数的简单路径。
注：简单路径为不经过重复的点的路径。
思路我们思考如何才能有一个长度为奇数的简单路径：
本来就有
有奇环。
为什么说是有奇环呢？不是说不能经过重复点吗？这里指的其实是经过的路径上有奇环，因为奇环可以分成两边走，由于是奇环，所以两边的奇偶性一定不一样，这样就给了我们选择路径奇偶性的余地。
那么本来就有是什么情况呢？如果两个点在一个 Dfs 生成树上面的深度奇偶性不同，那么他们就属于本来就有奇数路径。因为这样的话 $u\rightarrow root\rightarrow v$ 这样的路径一定是奇数的简单路径。那么如果奇偶性一样怎么办，那么我们就只能指望于两个点到他们 LCA 的路径上有奇环了。不难发现只要至少有一个奇环我们就是可以的。那么就只需要另外处理一个倍增数组，记录这里奇环的数量就可以了。
那么处理奇环也很简单，Tarjan 做点双连通分量，一个没有割点的图绝对有环，我们只需要判断是不是奇环，然后用 ...
【拾题杂谈】LuoguP3627 抢掠计划
题面大秦为你打开题目传送门
题目描述Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。
Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。
使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。 例如，假设该城中有 $6$ 个路口，道路的连接情况如下图所示：
市中心在路口 $1$，由一个入口符号 → 来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢劫的现金总数为 $47$，实施的抢劫路线是：$1-2-4-1-2-3 ...
