【算法模板】线段树区间修改区间查询求和
解释出门右转 线段树博文 谢谢
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 ...
【算法介绍】连通分量
算法简介：晨露浮光之思首先声明一点：这篇文章所谓 “连通分量” 并不是指一个算法，而是指算法 $\tt Tarjan$ 和 $\tt Kosaraju$ 算法，他们所应用的点双连通分量，边双连通分量，强连通分量，割点和桥，以及缩点。
我个人认为，$\tt Tarjan$ 算法只是一个思想，他的核心在于定义 $\tt low$ 和 $\tt dfn$ 数组的一系列性质的应用，还有在处理这些数据的过程中处理别的数据。接下来我们会依次介绍这些东西是怎么求的。
算法演示：千式齐聚之法Tarjan算法：真正的宝物我们在这里简单的介绍一下 Tarjan 的一个思想。
他首先对于一张图做 Dfs，得到的顺序叫做 Dfs 序，得到的图叫做 Dfs 树。
而对于每一个点被访问的顺序，也就是他第一次被访问的位置，我们用数组 $\tt dfn$ 表示，为什么要这样做呢？我们可以用一张图来简单看一看。我们这里就分为有向图和无向图来看。下图中数字是 Dfs 序。
有向图图例
边种类介绍
我们这样已经把这样的一个有向图变成了 Dfs 树的外观。我们按照这样一颗树的常见形式，将其分为如下几种边：1 ...
