嘴巴开省选

pbds

$\text{namespace}$ 是 __gnu_pbds，头文件可以直接 #include<bits/extc++.h> ，不过 devcpp 用不了，只能 #include<ext/pb_ds/assoc_container.hpp> 以及对应的头文件，迭代器都是 $\text{point\_iterator}$。

哈希表

根据别人以及自己的 $\text{benchmark}$ 来说 $\text{hash\_table}$ 表现很优秀，非构造数据卡点常还是要写的。

1. 头文件： #include<ext/pb_ds/hash_policy.h>
2. 声明：gp_hash_table<int,int>，当 $\text{unordered\_set}$ 用的话是 gp_hash_table<int,nulltype>
3. 使用：同 $\text{unordered\_map}$ ，直接遍历也是 $O(n)$ 乱序的。

堆

用配对堆，支持 $O(1)\ \text{push join}$，$O(\log)\ \text{erase modify}$ 。

1. 头文件： #include<ext/pb_ds/priority_queue.h>
2. 声明：__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag>
3. 使用：$\text{push}$ 会返回迭代器，$\text{join}$ 为 $\text{a.join(b)}$ 且清空 $\text b$ ，$\text{erase}$ 为 $\text{q.erase(it)}$，$\text{modify}$ 为 $\text{q.modify(it,x)}$ ，当 $\text{it}$ 为 $\text{NULL}$ 时就不在堆中，自定义比较同标准库要用 $\text{struct}$ 。

平衡树

用红黑树，相比 $\text{set}$ 支持 $\text{kth rank join split}$ ，和 $\text{fhq\_treap}$ 的常数差不多，常数较大。

1. 头文件： #include<ext/pb_ds/tree_policy.h>
2. 声明：tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
3. 使用：同 $\text{set}$ ，实现 $\text{multiset}$ 要用 $\text{pair}$ 通过第二关键字区分，下标从 $0$ 开始，$\text{kth}$ 是 $\text{*t.find\_by\_order(k-1)}$ ，求排名是 $\text{t.order\_of\_key(x)+1}$ ，合并是 $\text{a.join(b)}$ 且清空 $\text b$ ，要保证两树值域不交，分裂是 $\text{a.split(x,b)}$ 把 $\text b$ 清空再把 $>x$ 的元素分给 $\text b$ 。

拉格朗日插值

推法 1

1. $\because f(x)-f(y)=(a_0-a_0)+a_1(x-y)+a_2(x^2-y^2)+...+a_n(x^n-y^n)$

   $\therefore f(x)\equiv f(y)\pmod {x-y}$

2. 现在要对 $n$ 个点值 $(x_i,y_i)$ 进行插值，根据前面的证明可以转化得到线性同余方程组 $\left\{\begin{matrix}f(x)\equiv y_1\pmod {x-x_1})\\ f(x)\equiv y_2\pmod {x-x_2})\\ ...\end{matrix}\right.$

3. 用 $\text{CRT}$ 合并：$M=\prod (x-x_i),m_i=\frac M {x-x_i},m_i^{-1}=\prod_{j\ne i}x_i-x_j$

   $\Rightarrow f(x)\equiv \sum y_im_im_i^{-1}\equiv \sum y_i\prod_{j\ne i}\frac {x-x_j} {x_i-x_j}\pmod M$

   由于 $M$ 的次数更高所以直接略去，就得到了拉格朗日插值的式子。

推法 2

1. 有代数基本定理：$n$ 个不同点值能在 $n-1$ 次以内确定唯一的一个多项式。所以构造出一个满足这 $n$ 个点值的不超过 $n-1$ 的多项式那他就是唯一确定的。
2. 考虑对于每一个点值构造一个不超过 $n-1$ 次的多项式 $f_i$ 满足 $f_i(x_i)=y_i,f_i(x_{j[j\ne i]})=0$ ，那么 $f(x)=\sum f_i(x)$。
3. 根据 $f_i(x_{j[j\ne i]})=0$ 很容易构造出 $f_i(x)=(?)\prod_{j\ne i}(x-x_i)$ ，再代入 $f_i(x_i)=y_i$ 就可以解得 $f_i(x)=y_i\prod_{j\ne i}\frac {x-x_j} {x_i-x_j}$，求和就得到了拉格朗日插值的式子。

应用

1. 直接代入式子可以 $O(n^2)$ 插值。

   int F(int x)
   {
   	int sum=0;
   	for(rint i=1;i<=n;i++)
   	{
   		int res=Y[i],inv=1;
   		for(rint j=1;j<=n;j++)
   		if(j!=i) res=res*(x-X[j]+p)%p,inv=inv*(X[i]-X[j]+p)%p;
   		sum=(sum+res*qp(inv))%p;
   	}
   	return sum;
   }
   

2. 若插值使用的是连续一段整数的话，$\prod_{i\ne j}\frac{x-j}{i-j}=\frac {(x-1)^{\underline n}(-1)^{n-i}} {(x-i)(i-1)!(n-i)!}$，避免除 $0$ 维护前后缀积就可以 $O(n)$ 求值了。

   int F(int x)
   {
   	int sum=0;suf[n+1]=1;
   	for(rint i=n;i;i--) suf[i]=suf[i+1]*(x-i+p)%p;
   	for(rint i=1,pre=1;i<=n;i++)
   	{
   		int mul=Y[i]*pre%p*suf[i+1]%p,inv=fac[i-1]*fac[n-i]%p*((n-i)&1?p-1:1)%p;
   		sum=(sum+mul*qp(inv))%p,pre=pre*(x-i+p)%p;
   	}
   	return sum;
   }
   

3. 引理：若一个 $k$ 次多项式满足 $F(1,2,...,k)$ 都是整数，那么对于任意整数 $x$ ，$F(x)$ 都是整数。

   证明考虑代入拉插式子即可，所以如果模数非大质数的话是可以高精度的 ，当然也可以对模数分解质因数分别求解后 $\text{CRT}$ 合并。

原根

阶

1. 定义：满足 $a^n\equiv 1\pmod p$ 的最小正整数 $n$ 即为 $a$ 模 $p$ 的阶，记为 $\delta_p(a)$。
2. 存在：当 $(a,p)=1$ 时有 $a^{\varphi(p)}\equiv1 \pmod p$ ，所以 $\delta_p(a)\le \varphi(p)$。
3. 性质：
   1. $a,a^2,...,a^{\delta_p(a)}$ 模 $p$ 互不同余。
   2. 若 $a^n\equiv1\pmod p$，则 $\delta_p(a)|n$。
   3. 若 $(a,p)=(b,p)=1$，则此时 $\delta_p(ab)=\delta_p(a)\delta_p(b)\Leftrightarrow (\delta_p(a),\delta_p(b))=1$。
   4. 若 $(a,p)=1$，则 $\delta_p(a^k)=\frac {\delta_p(a)} {(\delta_p(a),k)}$。

原根

1. 定义：若 $(a,p)=1$ 且 $\delta_p(a)=\varphi(p)$，则称 $a$ 为模 $p$ 的原根。
2. 原根判定定理：若 $m\ge3$ 且 $(a,p)=1$，则 $[a\text{ 为原根}]\Leftrightarrow \forall \text{素因子 }P\in \varphi(p),a^{\frac {\varphi(p)} P}\not\equiv1\pmod p$。
3. 原根个数：若 $p$ 有原根，则原根数量为 $\varphi(\varphi(p))$，证明考虑任意原根 $=$ 最小原根$^k$ 且 $(k,\varphi(p))=1$。
4. 原根大小：若 $p$ 有原根，则最小原根 $\le\sqrt[4] p$ ，故暴力找原根的复杂度为 $O(\sqrt[4] p\log)$。
5. 原根存在定理：$p$ 有原根 $\Leftrightarrow$ $p=2,4,P^k,2P^k$，$P$ 为奇素数。

BSGS

应用

$O(\sqrt p)$ 求解满足 $a^x\equiv b\pmod p$ 或 $x^a\equiv b\pmod p$ 的最小 $x$ ，即求模意义下的对数或底数。

一般BSGS

1. $a\perp p$，即 $a\ p$ 要互质，保证有逆元。

2. 将 $x$ 表示为 $A\left \lfloor \sqrt p \right \rfloor -B\ \ (A,B<\sqrt p)\Rightarrow a^{A\left \lfloor \sqrt p \right \rfloor}\equiv ba^B$

3. 用哈希表映射 $ba^B\Rightarrow B$，$O(\sqrt p)$ 枚举 $A$，若能查到对应 $B$ 即得答案。

   gp_hash_table<int,int> mp;
   int bsgs(int x,int y)
   {
   	int sq=ceil(sqrt(p));mp.clear();
   	for(rint now=1,i=0;i<=sq;i++,now=now*x%p) mp[y*now%p]=i;
   	gp_hash_table<int,int>::point_iterator it;
   	for(rint i=0,now=1,res=qp(x,sq);i<=sq;i++,now=now*res%p) 
   	if((it=mp.find(now))!=mp.end()&&i*sq>=it->second) return i*sq-it->second;
   	return -1;
   }
   

exBSGS

1. $p$ 可为任意模数。

2. 先特判 $b=1$ 和 $p=1$ 的情况。

3. 利用模的分配率$\Rightarrow \frac {a^k} {\prod^k g_i} a^{x-k}\equiv \frac b {\prod^k g_i}\pmod {\frac p {\prod^k g_i}}$ 满足 $(a,\frac p {\prod^k g_i})=1$，若 $\prod^k g_i\nmid b$ 则无解，证明考虑 $(\frac a g)^xg^x+\frac p gg=b$ 中 $b$ 一定含有因子 $g$。

4. $\Rightarrow a^{x-k}\equiv \frac b {\frac {a^k} {\prod^k g_i}\prod^k g_i}\pmod {\frac p {\prod^kg_i}}$ ，此时满足互质，$\text{BSGS}$ 求出 $x-k$ 即可。

   int exbsgs(int x,int y)
   {
   	if(p==1||y==1) return 0;
   	int g=__gcd(x,p),k=0,sum=1;
   	while(g!=1)
   	{
   		if(y%g) return -1;
   		k++,y/=g,p/=g,sum=sum*(x/g)%p;
   		if(sum==y) return k;	//特判x==k
   		g=__gcd(x,p);
   	}
   	int ans=bsgs(x,y*inv(sum)%p);
   	if(~ans) return ans+k;
   	return -1;
   }
   

求底数

1. 求 $x^a\equiv b\pmod p$ 要满足 $p$ 为质数，保证 $p$ 有原根且能使用 $\text{BSGS}$。
2. 设 $g$ 为 $p$ 的原根，则 $x=g^y$，$(g^a)^y\equiv b\pmod p$，$\text{BSGS}$ 求解即可。

积性函数

定义

1. 数论函数：$f:Z^+\rightarrow C$，即定义域为正整数，值域为复数的函数。
2. 积性函数：满足 $f(1)=1$ 且 $f(p\times q)=f(p)\times f(q)\ \ (p,q)=1$ 的函数。
3. 完全积性函数：满足 $f(1)=1$ 且 $f(p\times q)=f(p)\times f(q)\ \ p,q\in Z^+$ 的函数。

常见完全积性函数

1. 元函数：$e(n)=[n=1]$
2. 恒等函数：$I(n)=1$
3. 单位函数：$id(n)=n$
4. 幂函数：$id^k(n)=n^k$

常见积性函数

1. 约数个数函数：$\tau(n)=d(n)=\sigma_0(n)=\sum_{d|n}1$

2. 约数和函数：$\sigma(n)=\sigma_1(n)=\sum_{d|n}d$

3. 除数函数：$\sigma_k(n)=\sum_{d|n}d^k$，即约数 $k$ 次幂和。

4. 欧拉函数：$\varphi(n)=\sum_{i=1}^n[(i,n)=1]$，即 $1\sim n$ 与 $n$ 互质的个数。

   1. $\varphi(p)=p-1,p\in prime$。
   2. $\sum^n_{(i,n)=1}i=\frac {n\varphi(n)+[n=1]} 2$。
   3. 若 $n>2$，则 $\varphi(n)$ 为偶数。

5. 莫比乌斯函数：$\mu(n)=\left\{\begin{matrix}0 &\exist \ c_i>1 \\(-1)^k & \forall \ c_i=1\end{matrix}\right.$ ，$n=\prod^kp_i^{c_i}$

狄利克雷卷积

定义

1. 数论函数 $f$ 与 $g$ 的狄利克雷卷积 $(f*g)(n)=\sum_{d|n}f(d)g(\frac n d)$。

性质

1. 满足交换律、结合律、分配律，若 $f,g$ 均积性，则 $f*g$ 也为积性。

2. 对于元函数：$f*e=f$，$e$ 即为单位元。

3. 对于积性函数 $f$：$f*I=\prod^k_{i=1}\sum_{j=0}^{c_i}f(p_i^j)$，考虑分解质因数得证。

4. 对于莫比乌斯函数：$\mu*I=\sum_{d|n}\mu(d)=\sum_{i=0}^k\binom k i(-1)^i=(1-1)^k=e$，考虑定义得证，发现 $f*I*\mu=f$，称为莫比乌斯反演。

5. 对于欧拉函数：$\varphi(n)=\sum_{i=1}^ne((i,n))=\sum_{i=1}^n\mu*I((i,n))=\sum_{i=1}^n\sum_{d|(i,n)}\mu(d)=$$\sum_{d=1}^n\mu(d)\sum_i[d|(i,n)]=\sum_{d=1}^n\mu(d)\left \lfloor \frac n d \right \rfloor=\mu*id$，$\varphi=\mu*id\Leftrightarrow\varphi*I=id$，称为欧拉反演，本质同莫反。

6. 对于约数函数：$\tau=I*I$，$\sigma=I*id$，$\sigma_k=I*id^k$，考虑定义得证。

   另外 $\tau(ij)=\sum_{x|i}\sum_{y|j}[(x,y)=1]$，证明考虑拆位，每种质因数的方案贡献一定是 $a+b+1$，保证 $\gcd=1$ 时的方案贡献也为 $a+b+1$，所以是等价的。

   还有其扩展，$\tau(ABC)=\sum_{x|A}\sum_{y|B}\sum_{z|C}[(x,y)=1][(x,z)=1][(y,z)=1]$

   $\sigma_k(AB)=\sum_{x|A}\sum_{y|B}[(x,\frac B y)=1](xy)^k$

   $\sigma_k(ABC)=\sum_{x|A}\sum_{y|B}\sum_{z|C}[(x,\frac B y)=1][(y,\frac C z)=1][(x,\frac C z)=1](xyz)^k$

   证明思路基本相同。

7. 对于约数和函数：$\sigma=id*I*e=id*I*I*\mu=\tau*\varphi$ 。

8. 对于 $\gcd$ ：$\sum_i^n\sum_j^n\gcd(i,j)=\sum^n_{d=1}d\sum_i^n\sum_j^n[(i,j)=d]=\sum^n_{d=1}d\sum_i^{n/d}\sum_j^{n/d}e((i,j))=$$\sum^n_{d=1}d\sum_i^{n/d}\sum_j^{n/d}\sum_{q|(i,j)}\mu(q)=\sum^n_{d=1}d\sum_{q=1}^{n/d}\mu(q)\left \lfloor \frac n {dq} \right \rfloor^2=\sum^n_{t=1}\left \lfloor \frac n t \right \rfloor^2\sum_{d|t}d\times\mu(\frac t d)$

9. 对于完全积性函数 $h$：$f(n)=\sum_{i=1}^nh(i)g(\lfloor\frac n i \rfloor)\Leftrightarrow g(n)=\sum_{i=1}^n\mu(i)h(i)f(\lfloor \frac n i \rfloor)$，$f,g$ 为数论函数，不会证。

方法

1. $val\Rightarrow bool\times val$，$bool\Rightarrow e$，$e\Rightarrow \mu$
2. 交换求和顺序。
3. 利用整除分块、积性筛法求解。

杜教筛

定义

1. 在亚线性时间复杂度求解部分数论函数前缀和，一般为 $O(n^{\frac 2 3})$，常见的判定法是若 $A*B=C$ 中 $A$ 可线筛 $B\ C$ 可杜教筛，则 $A$ 可杜教筛。
2. 要计算 $s(n)=\sum_{i=1}^nf(i)$，考虑任意数论函数 $g$ 满足 $\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^n\sum_{d|i}f(d)g(\frac i d)=\sum_{i=1}^ng(i)s(\lfloor \frac n i \rfloor)$，可以得到 $s(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)s(\lfloor \frac n i\rfloor)$，找到合适的 $g$ 能快速记忆化递归计算即可。

实例

1. $s(n)=\sum_{i=1}^n\mu(i)$：取 $g=I$，这样 $\mu*I=e$，$s(n)=1-\sum_{i=2}^ns(\lfloor \frac n i\rfloor)$，直接记忆化递归是 $O(\sum_{i=1}^{\sqrt n}\sqrt{\frac n i})=O(n^{\frac 3 4})$，线性筛预处理即为 $O(n^{\frac 2 3})$，注意记忆化不用 $map$，因为 $\lfloor \frac {\lfloor \frac n {d_1} \rfloor} {d_2} \rfloor=\lfloor \frac n {d_1d_2}\rfloor$，所以 $n^{\frac 1 3}$ 长的数组下标直接记录 $d$ 即可。

2. $s(n)=\sum_{i=1}^n\varphi(i)$：取 $g=I$，这样 $\varphi*I=id$，$s(n)=\frac {i*(i+1)} 2-\sum_{i=2}^ns(\lfloor \frac n i\rfloor)$， $O(n^{\frac 2 3})$ 。

3. $s(n)=\sum_{i=1}^n\varphi(i)*i^2$：取 $g=id^2$，这样 $(\varphi\ id^2)*(id^2)=id^3$，$s(n)=(\frac {n(n+1)} 2)^2-\sum_{i=2}^ni^2s(\lfloor \frac n i\rfloor)$，$O(n^{\frac 2 3})$ 。

4. $s(n)=\sum_{i=1}^n\sigma_k(i)$：因为 $\sigma_k=I*id^k\Rightarrow \sigma_k*\mu=id^k$，能判定可杜教筛，不过这里直接从定义解更简单也更优，$\sum_{i=1}^n\sigma_k(i)=\sum_{i=1}^n\sum_{d|i}d^k=\sum_{d=1}^nd^k\lfloor \frac n d\rfloor$，求自然数幂和即可 $O(k\sqrt n)$。

5. $s(n)=\sum_{i=1}^n(\mu^2*\mu id)(i)$，取 $g=id$，这样 $\mu^2*\mu id*id=\mu^2$，转化为了筛 $\mu^2$。

   从定义入手发现是求 $1\sim n$ 不含平方因子的数，考虑容斥枚举即得 $\sum_{i=1}^{\sqrt n}\mu(i)\lfloor\frac n {i^2}\rfloor$ 。

   也可以构造函数 $f(n)=[n为完全平方数]$，可得 $f*\mu^2=I$，按杜教筛可推得 $s(n)=n-\sum_{i=2}^nf(i)s(\lfloor\frac n i\rfloor)=n-\sum_{i=2}^{\sqrt n}s(\lfloor\frac n {i^2}\rfloor)$。

   还可以构造函数 $f(n)=\sqrt{n最大平方因子}$，可得 $s(n)=\sum_{i=1}^n[f(i)=1]=\sum^n_{i=1}\sum_{d|f(i)}\mu(d)$，而 $d|f(i)\Leftrightarrow d^2|i$，所以 $s(n)=\sum_{d=1}^{\sqrt n}\mu(d)\lfloor \frac n {d^2}\rfloor$，由此还可发现 $\mu^2(n)=\sum_{d^2|n}\mu(d)$。

Powerful Number 筛

Powerful Number

1. 定义：即不含幂次为 $1$ 的素因项的数。
2. 性质：
   1. 一定可以表示为 $a^2b^3$，分解质因数可证。
   2. 数量级为 $O(\sum \sqrt[3]{\frac {n} {i^2}})=O(\sqrt n)$，所以直接 $\text{dfs}$ 素因子指数求所有 $\text{PN}$ 复杂度为 $O(\sqrt n)$。

PN 筛

1. 定义：大致为杜教筛扩展，找到一个能求前缀和的积性函数 $g$ 满足 $g(p)=f(p)$ 就能求 $f$ 的前缀和，瓶颈在杜教筛。
2. 设 $h=f/g$，即逆狄利克雷卷积（仅作表示），满足积性函数则 $h$ 必定唯一存在且也为积性函数，由于 $g(p)=f(p)$，所以 $h(p)=0$，发现 $h$ 仅在 $PN$ 处有值。
3. $\sum^n_{i=1} f(i)=\sum_{i=1}^n \sum_{d|i} h(d)g(\frac i d)=\sum_{d=1}^nh(d)S_g(\lfloor \frac n d\rfloor)=\sum_{d\in PN}h(d)S_g(\lfloor \frac n d\rfloor)$，杜教筛筛出 $g$ 再暴力求出 $h$ 在 $\text{PN}$ 出的所有值即可。
4. 具体地，考虑 $h$ 是积性函数仅需考虑 $h(p^k)$ 的值，$f(p^k)=\sum_{i=0}^k h(p^i)g(p^{k-i})\Leftrightarrow h(p^k)=f(p^k)-\sum_{i=0}^{k-1}h(p^i)g(p^{k-i})$，暴力算就行，能 $O(1)$求值的话复杂度不超过 $O(\sqrt n)$。

网络流

定义

1. 流网络：带权有向图 $\text{G(V,E)}$，含源点 $\text s$ 汇点 $\text t$，边有容量 $\text{c(u,v)}$。

2. 可行流 $\text f$ ：$\begin{cases} ①\text{ 容量限制：} 0\le f(u,v)\le c(u,v) \text{ 流量不超过容量} \\ ②\text{ 反对称性：} f(u,v)=-f(v,u)\ 正着流出等于反着流进 \\ ③\text{ 流量守恒：}\forall_{x\in V/\{s,t\}} \sum f(u,x)=\sum f(x,v) \text{ 除源汇点外流入量=流出量}\end{cases}$

   流量：$|f|=\sum f(s,v)-\sum f(u,s)$ 源点流出量（减源点流入量），最大流即最大流量可行流。

3. 残量网络 $\text{G}_{\text f}$ ：由可行流 $f$ 决定，其中 $V_f=V,E_f=E+\overline E,c'(u,v)=\begin{cases} c(u,v)-f(u,v) & (u,v)\in E \\ f(u,v) & (u,v)\in \overline E\end{cases}$ ，$f'$ 表示 $G_f$ 的可行流，则 $f+f'$ 也是 $G$ 的可行流，$|f+f'|=|f|+|f'|$，$f$ 为最大流 $\Leftrightarrow$ $\forall |f'|=0$。

4. 增广路径：$G_f$ 中从 $\text s$ 到 $\text t$ 的一条简单路径，是一条可行流。

5. 割：将 $V$ 分为两个点集 $s\in S,t\in T$。

   1. 割的容量：$c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)$

   2. 割的流量：$f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-f(v,u)$

   3. $f(S,T)\le c(S,T)$，且 $f(S,T)=|f|$。

   4. 最大流最小割定理：$f$ 是最大流 $\Leftrightarrow$ $G_f$ 无增广路径 $\Leftrightarrow$ $\exist_{[S,T]}\ |f|=c(S,T)$，即最大流 $=$ 最小割。

      证明一下，首先最大流 $\le$ 最小割这个显然，然后考虑最大流上的瓶颈边一定是一个割否则仍有增广路径，所以最大流 $\ge$ 最小割，得到最大流 $=$ 最小割。

最大流

1. $\text{EK}$ 求最大流：不断 $\text{bfs}$ 找到一条增广路径累加进当前流并更新沿途的流量，找不到增广路径时即为最大流，复杂度 $O(nm^2)$，很松。

   int hh,tt,q[N];
   int pre[N],d[N];
   bool use[N];
   
   bool bfs()
   {
       hh=tt=0,memset(use,0,sizeof use);
       q[0]=s,use[s]=1,d[s]=p;
       while(hh<=tt)
       {
           int x=q[hh++];
           for(rint i=head[x];~i;i=nxt[i])
           {
               int y=to[i];
               if(!use[y]&&w[i])
               {
                   pre[y]=i,d[y]=min(d[x],w[i]);
                   if(y==t) return 1;
                   q[++tt]=y,use[y]=1;
               }
           }
       }
       return 0;
   }
   int ek()
   {
       int ans=0;
       while(bfs())
       {
           ans+=d[t];
           for(rint i=t;i!=s;i=to[pre[i]^1])
               w[pre[i]]-=d[t],w[pre[i]^1]+=d[t];
       }
       return ans;
   }
   

2. $\text{Dinic}$ 求最大流：不断 $\text{bfs}$ 标记层数，再 $\text{dfs}$ 层间多路增广路径，有剪枝优化，复杂度 $O(n^2m)$，很松。

   int cur[N],d[N];
   int q[N],hh,tt;
   
   bool bfs()
   {
   	for(rint i=1;i<=n;i++) cur[i]=head[i],d[i]=0;
   	q[hh=tt=0]=s,d[s]=1;
   	while(hh<=tt)
   	{
   		int x=q[hh++];
   		for(rint i=head[x];~i;i=nxt[i])
   		{
   			int y=to[i];
   			if(!d[y]&&w[i])
   			{
   				d[y]=d[x]+1;
   				if(y==t) return 1;
   				q[++tt]=y;
   			}
   		}
   	}
   	return 0;
   }
   int find(int x,int lim)
   {
   	if(x==t) return lim;
   	int sum=0;
   	for(rint i=cur[x];~i&&sum<lim;i=nxt[i])
   	{
   		int y=to[i];cur[x]=i;
   		if(d[y]==d[x]+1&&w[i])
   		{
   			int flow=find(y,min(w[i],lim-sum));
   			if(!flow) d[y]=0;
   			w[i]-=flow,w[i^1]+=flow,sum+=flow;
   		}
   	}
   	return sum;
   }
   int dinic()
   {
   	int ans=0,res;
   	while(bfs()) while(res=find(s,p)) ans+=res;
   	return ans;
   }
   

3. 二分图最大匹配：$s$ 向集合 $A$ 连容量为 $1$ 的边，集合 $B$ 向 $t$ 连容量为 $1$ 的边，可行匹配为对应的 $A$ 向 $B$ 连容量为 $1$ 或 $\text{inf}$ 的边，最大流为最大匹配，$Dinic$ 复杂度 $O(m\sqrt n)$，可以扩展到限制每个元素最多匹配几次。

4. 最小割方案：残量网络上找出连通块 $S$，剩下的即为 $T$，$S\rightarrow T$ 的边即为最小割方案。

5. 可行边与必须边：即所有最小割方案的并集和交集。考虑残量网络是若干连通块，必须边即为直接连接 $S,T$ 的边，可行边即为连接不同连通块的边，当然要保证最初的流网络连通。

6. 无源汇上下界可行流：将 $c_1(u,v)\le f(u,v)\le c_2(u,v)$ 转化为 $0\le f(u,v)-c_1(u,v)\le c_2(u,v)-c_1(u,v)$，对于每个点以 $\sum c_1(u,x)-\sum c_1(x,v)$ 正负来判断是否放流或需流，建虚源汇点根据需放流连接每个点，跑最大流当流量流满时即有解，每条边加上原来的 $c_1$ 即得方案。费用流和这个是一样的。

7. 上下界最大流：由 $t$ 向 $s$ 连一条容量 $inf$ 的边转为无源汇，求出无源汇上下界可行流，而由于现在虚源汇点必定满流所以在残量网络上与 $s,t$ 无关，记下 $t\rightarrow s$ 的流量再加上删去该边后残量网络的最大流即为答案。 费用流和这个是一样的。

8. 上下界最小流：同上下界最大流，最后跑残量网络的最大流时交换源汇点，用可行流减去逆最大流即可。

9. 最大权闭合子图：

   1. 定义：带点权有向图的一个点集，满足无出边指向点集外的点。
   2. 简单割：只割 $s$ 邻边和 $t$ 邻边的割。
   3. 考虑建立网络流模型使得闭合子图方案与割对应，通过最小割求解方案最值问题。
   4. 建立源汇点，原边容量为 $\text{inf}$​，新连边 $\begin{cases} s\rightarrow \forall 点权>0 \\ \forall 点权<0 \rightarrow t\end{cases}$，容量为点权绝对值。
   5. 原边为 $\text{inf} \Rightarrow$ 最小割为简单割，残量网络中的 $S$ 点集为闭合子图。
   6. 考虑割去了正权点的边他一定会属于 $T$ 点集，割去负权点的边他一定会属于 $S$ 点集，所以 $S$ 点集的权值和 $=$ 正权点和 $-$ 最小割。
   7. 故最大权闭合子图 $=$ 正权点和 $-$ 最小割。

10. 最大密度子图：

    1. 定义：无向图的一个点集，满足其 $\frac {\text{内部边数}} {\text{点数}}$ 最大。
    2. 考虑二分，边转为向两边连出有向边的点，点权为 $1$ ，原点点权为 $-mid$，用最大权闭合子图判定即可，可以扩展到点边带权。

11. 最小割树：

    1. 用于求解多组点对间最小割。不会证。
    2. 考虑先求解任意一个 $cut(u,v)$ ，然后连边 $[u,v,cut(u,v)]$，接着根据 $cut(u,v)$ 分成的两个点集往下递归建树，两点最小割即两点瓶颈路，复杂度 $O(n^3m+q)$，可以不用显式建树直接 $O(n^2)$ 暴力存 $dis$ 数组，注意求最小割时要用到所有点边。

12. 网络流技巧：

    1. 找出源汇点，以流或割对应题目的决策。
    2. 证明原题可行解与可行流对应，可以排除一定不优的解。
    3. 用 $\text{inf}$ 容量排除不参与割决策的边。
    4. 将点权转移到源汇边权上，利用简单最小割作最优化工具来决策点的取舍。

费用流

1. 定义：边除了容量还带单位费用，流的费用就是所有边的单位费用 $\times$ 经过的流量，费用流指最小费用最大流，即流量最大时的最小费用。

2. $\text{EK}$ 求费用流：不断 $\text{SPFA}$ 找费用最短路增广更新流量，复杂度能卡到 $O(Fnm)$，一般勉强看作 $O(nm^2)$。

   int d[N],pre[N],flow[N];
   bool use[N];
   queue<int> q;
   
   bool spfa()
   {
   	for(rint i=1;i<=n;i++) d[i]=p,flow[i]=0;
   	q.push(s),d[s]=0,flow[s]=p;
   	while(!q.empty())
   	{
   		int x=q.front();q.pop();
   		use[x]=0;
   		for(rint i=head[x];~i;i=nxt[i])
   		{
   			int y=to[i];
   			if(w[i]&&d[y]>d[x]+f[i])
   			{
   				d[y]=d[x]+f[i];
   				pre[y]=i,flow[y]=min(flow[x],w[i]);
   				if(!use[y]) q.push(y),use[y]=1;
   			}
   		}
   	}
   	return flow[t];
   }
   void ek()
   {
   	int ans=0,cost=0;
   	while(spfa())
   	{
   		ans+=flow[t],cost+=flow[t]*d[t];
   		for(rint i=t;i!=s;i=to[pre[i]^1])
   			w[pre[i]]-=flow[t],w[pre[i]^1]+=flow[t];
   	}
   	cout<<ans<<" "<<cost<<endl;
   }
   

3. 负环：由于反边等情况，在第一步最短路中可能会出现负环，要用到消圈算法，但是我不会，考虑不管。

4. 费用优先流：

   1. 最大费用任意流：考虑费用一直在减少，单次费用即将为负时停止即可。
   2. 费用为正的最大流：考虑费用一直在减少，总费用即将为负时停止即可。

二分图相关

二分图判定

1. 图为二分图 $\Leftrightarrow$ 没有奇环，$\text{dfs}$ 染色判定即可 。

二分图最大匹配

1. 匈牙利算法：

   1. 一个匹配为最大匹配 $\Leftrightarrow$ 没有增广路。增广路就是交替走非匹配边和匹配边奇数步的路径。证明考虑首先最大匹配显然没有增广路，然后不是最大匹配的一定存在两个点是新加入的，以其作为增广路的两端是一定可行的，所以一定有增广路。

   2. 匈牙利算法就是遍历左侧的所有点进行 $\text{dfs}$ 尝试为其寻找增广路，复杂度 $O(nm)$。

      bool dfs(int x,int now)
      {
      	if(use[x]==now) return 0;
      	use[x]=now;
      	for(auto &it:e[x])
      	if(!mch[it]||dfs(mch[it],now)) return mch[it]=x,1;
      	return 0;
      }
      

      具体来说右边的点只用到了 $\text{mch}$，是可以不显式存在的，在一些拆点场景可以减少码量。

2. 网络流 $\text{Dinic}$ ：$O(m\sqrt n)$。

Hall 定理

1. 二分图完美匹配：钦定 $|A|\le|B|$，匹配数 $=$ $|A|$ 的一组匹配。
2. $\text{Hall}$ 定理：二分图存在完美匹配 $\Leftrightarrow$ $\forall a\sube A$，设 $b$ 为 $a$ 能到达的右部点集的并，满足 $|a|\le|b|$。
3. $\text{exHall}$ 定理：二分图最大匹配 $=$ $|A|-\max (|a|-|b|)$。

二分图博弈

1. 即二分图上交替行走谁不能走谁输，问题等价于起点是否为最大匹配必经点，证明考虑必经点走两步一定会到必经点。

2. 判断二分图必经点可以用最小割必须边来判断。

   也可以用匈牙利判断。具体地，考虑判断非必经点，在每次增广新点增广路失败的时候，那他一定是非必经点，同时与之相邻的匹配也都可以被替换掉，也为非必经点递归标记下去就行。

   bool dfs(int x,int now)
   {
   	if(use[x]==now) return 0;
   	use[x]=now;
   	for(auto &it:e[x])
   	if(!mch[it]||dfs(mch[it],now)) return mch[it]=x,1;
   	return 0;
   }
   void dfs2(int x,int now)
   {
   	if(use[x]==now) return;
   	use[x]=now,ans[x]=1;
   	for(auto &it:e[x])
   	if(mch[it]) dfs2(mch[it],now);
   }
   for(rint i=1;i<=n;i++) if(!dfs(i,i)) dfs2(i,n+i);
   

二分图最小点覆盖

1. 二分图最小点覆盖 $=$ 最大匹配数，一般图是 $\text{NPC}$。
2. 证明考虑网络流，中间容量为 $\text{inf}$，发现最小割等价于最小点覆盖。据此也可以拓展到点带权。
3. 构造方案考虑我们得到了所有最大匹配的相关点，最小点覆盖一定在里面，枚举所有不相关点的相邻点是必选的，若剩下的都是相关点就任选一个继续做。
4. 最小边覆盖：考虑每一次选边只能新覆盖 $1$ 或 $2$ 个点，覆盖 $2$ 个点是一个匹配，故最小边覆盖 $=$ 点数 $-$ 最小点覆盖。

最大独立集

1. 独立集：一组点集其两两之间无边。
2. 团：一组点集其两两之间有边。最大独立集 $=$ 补图最小团。
3. 最大独立集的补集一定会将所有边覆盖，故最大独立集 $=$ 最小点覆盖，最大权独立集 $=$ 最小权点覆盖。

最小路径覆盖

1. 路径覆盖：$\text{DAG}$ 上一组覆盖所有点的点不交路径。也称链覆盖。
2. 考虑拆点，出点和入点形成二分图，发现一组路径覆盖对应到二分图的一组匹配，而路径数 $=$ 点数 $-$ 匹配数，转化为求最大匹配。
3. 最小可重路径覆盖：在传递闭包后的 $\text{DAG}$ 上做最小路径点覆盖即可，这里的传递闭包即两点连通 $\Rightarrow$ 两点连边，搜索 $O(nm)$ 不过 $\text{Floyd}$ 更好写。

Dilworth 定理

1. 定义：对于任意有限偏序集，其最长反链中元素的数目必等于最小链覆盖中链的数目。
2. 偏序集形成的图是 $\text{DAG}$，放到 $\text{DAG}$ 上来说的话其实就是最小可重路径覆盖 $=$ 最大不互达点集。
3. 证明的话考虑放到 $\text{DAG}$ 上，记一个最小可重路径覆盖方案的路径结尾点集 $\text E$，$\text E$ 每个点能走到不含自身的点集并为 $\text E'$，若 $\text E'$ 满足 \text E\and\text E'=\empty 即不互达则成立，否则对于 \text E\and\text E' 中的每个点往沿着路径返回直到不属于 $\text E'$ 得到方案，考虑路径上一定不会全部属于 $\text E'$ 否则一定能被这条可重路径延伸包含所以一定能得到方案。

李超线段树

1. 用途：支持 $O(\log^2)$ 插入线段 $O(\log)$ 查询单点最值。若全为直线则插入为 $O(\log)$，支持动态开点、持久化。
2. 实现：标记永久化线段树，大值域需要离散化或动态开点，实数需要离散化。
   1. v[N<<2] 维护覆盖区间 [l,r] 且是 mid 处最值的线段编号。
   2. 插入：递归到子区间，为空直接赋值返回，若中点值优于 v[now] 则与之交换，再考虑当前的线段是否比 v[now] 的左右端点优再往左右递归。由于两线段最多有一个交点，所以一次插入最多产生 $O(\log)$ 个交点操作，每次操作又是 $O(\log)$ 的，故为 $O(\log^2)$。
   3. 查询：计算递归到子区间沿途的所有线段取值最值即可。

struct tree{	//线段
	#define cal(i,x) (k[i]*x+b[i])
	int v[M<<2];
	void insert(int l,int r,int x,int nowl=1,int nowr=m,int now=1)
	{
		int mid=(nowl+nowr)>>1;
		if(l<=nowl&&nowr<=r)
		{
			bool lp=cal(x,nowl)>cal(v[now],nowl),
				 rp=cal(x,nowr)>cal(v[now],nowr),
				 mp=cal(x,mid)>cal(v[now],mid);
			if(!v[now]) lp=rp=mp=1;
			if(mp) swap(x,v[now]),lp^=1,rp^=1;
			if(nowl==nowr) return;
			if(lp) insert(l,r,x,nowl,mid,now<<1);
			if(rp) insert(l,r,x,mid+1,nowr,now<<1|1);
			return;
		}
		if(l<=mid) insert(l,r,x,nowl,mid,now<<1);
		if(r>mid) insert(l,r,x,mid+1,nowr,now<<1|1);
	}
	int ask(int x,int l=1,int r=m,int now=1)
	{
		if(l==r) return v[now];
		int mid=(l+r)>>1;
		int res=(x<=mid)?ask(x,l,mid,now<<1):ask(x,mid+1,r,now<<1|1);
		if(!v[now]||!res) return v[now]|res;
		double ll=cal(v[now],x),rr=cal(res,x);
		if(abs(ll-rr)<eps) return min(res,v[now]);
		return ll>rr?v[now]:res;
	}
}t;

struct tree{	//直线
	int v[N<<2];
	#define cal(i,x) (k[i]*x+b[i])
	void insert(int x,int l=1,int r=m,int now)
	{
		if(!v[now]) return v[now]=x,void();
		int mid=(l+r)>>1;
		if(cal(x,mid)<cal(v[now],mid)) swap(v[now],x);
		if(l==r) return;
		if(cal(x,l)<cal(v[now],l)) insert(x,l,mid,now<<1);
		if(cal(x,r)<cal(v[now],r)) insert(x,mid+1,r,now<<1|1);
	}
	int ask(int x,int l=1,int r=m,int now)
	{
		if(l==r) return v[now];
		int mid=(l+r)>>1,
		res=(x<=mid)?ask(x,l,mid,now<<1):ask(x,mid+1,r,now<<1|1);
		if(!res||!v[now]) return res|v[now];
		return cal(res,x)<cal(v[now],x)?res:v[now];
	}
}t;

ODT 颜色段均摊

1. 用途：维护单纯区间赋值或纯随机数据下支持遍历，复杂度 $O(n\log\log n)$。

2. 实现：把值相同的区间合并成一个节点，用 $\text{set}$ 维护。

   1. 对于 $\text{set}$ 中不参与比较的变量参数用 mutable 修饰可以支持修改，这里的区间值需要 mutable。
   2. 核心操作：auto split(int x) 将 $\text{[x}$ 处切断并返回 $\text x$ 处迭代器，注意实现细节，区间操作都通过 split 来取出区间暴力执行。

   struct node{
   	int l,r; mutable int v;
   	bool operator <(const node& x)const{return l<x.l;}
   };
   set<node> odt;
   
   auto split(int x)
   {
   	auto it=odt.lower_bound({x,0,0});
   	if(it!=odt.end()&&it->l==x) return it;
   	it--;
   	int l=it->l,r=it->r,v=it->v;
   	odt.erase(it),odt.insert({l,x-1,v});
   	return odt.insert({x,r,v}).first;
   }
   void assign(int l,int r,int v)
   {
   	auto itr=split(r+1),itl=split(l);
   	odt.erase(itl,itr),odt.insert({l,r,v});
   }
   void add(int l,int r,int v)	//随机操作和范围时支持遍历,不随机只能骗分
   {
   	auto itr=split(r+1),itl=split(l);
   	for(auto it=itl;it!=itr;it++) it->v+=v;
   }
   

K-D Tree

1. 用途：维护高维空间点集的检索，空间复杂度 $O(n)$。
2. 建树：类似于线段树的 $\text{Leafy}$ 结构，每个节点维护一个包含区间内所有点的超矩形，建树时交替维度选当前维度的中位数为 $\text{mid}$ 分治就能保证树高为 $O(\log)$，复杂度 $O(n\log)$。
3. 查询：对一个超矩形进行询问，在 $\text{KDT}$ 上最多涉及 $O(n^{1-\frac 1 k})$ 个节点，类似线段树往左右儿子递归询问即可，复杂度 $O(n^{1-\frac 1 k})$。
4. 插入：设阈值 $\text B$，插入的点数小于 $\text B$ 则在 $\text{KDT}$ 外暴力统计，大于阈值则重构 $\text{KDT}$，复杂度 $O(\frac n B n\log+n(n^{1-\frac 1 k}+B))$，取 $B=\sqrt{n\log}$ 得到 $O(n\sqrt{n\log}+n^{2-\frac 1 k})$。
5. 删除：能额外排除的话可以类似插入一样设阈值重构，否则只能递归到叶子消去贡献再类似替罪羊树做子树阈值重构，没有实现过。
6. 邻域查询：信息不能在超矩形上完全维护可能要往下递归查询时，复杂度 $O(n)$，可能能在 $\text{KDT}$ 上维护信息做启发式搜索乱搞。

struct node{
	int x,y,val;
}a[N];
bool cmpx(const node &A,const node &B){return  A.x<B.x;}
bool cmpy(const node &A,const node &B){return  A.y<B.y;}
struct data{
	int xl,xr,yl,yr,val;
	bool Apart(const data &A)const{return xl>A.xr||xr<A.xl||yl>A.yr||yr<A.yl;}
	bool inclu(const data &A)const
	{return xl<=A.xl&&A.xr<=xr && yl<=A.yl&&A.yr<=yr;}
	bool inclu(const node &A)const
	{return xl<=A.x&&A.x<=xr && yl<=A.y&&A.y<=yr;}
};
struct kdtree{
	data v[N<<2];
	void build(int l,int r,int now=1,bool how=0)
	{
		if(l==r) return v[now]={a[l].x,a[l].x,a[l].y,a[l].y,a[l].val},void();
		int mid=(l+r)>>1;
		nth_element(a+l,a+mid,a+r+1,how?cmpx:cmpy);
		build(l,mid,now<<1,!how),build(mid+1,r,now<<1|1,!how);
		int ls=now<<1,rs=now<<1|1;
		v[now]={min(v[ls].xl,v[rs].xl),max(v[ls].xr,v[rs].xr),
				min(v[ls].yl,v[rs].yl),max(v[ls].yr,v[rs].yr),
				v[ls].val+v[rs].val};
	}
	data aks;
	void ask(int l,int r,int now=1)
	{
		if(aks.Apart(v[now])) return;
		if(aks.inclu(v[now])) return aks.val+=v[now].val,void();
		int mid=(l+r)>>1;
		ask(l,mid,now<<1),ask(mid+1,r,now<<1|1);
	}
	void dfs(int l,int r,int now=1)	//乱搞
	{
		double d=aks.dis(v[now]);
		if(d>ans&&!aks.in(v[now])) return;
		if(l==r)
		{
			if(d==p)
			{
				if(!same) same=1;
				else ans=0;
			}else ans=d;
			return;
		}
		int mid=(l+r)>>1;
		if(aks.dis(v[now<<1])<aks.dis(v[now<<1|1])) dfs(l,mid,now<<1),dfs(mid+1,r,now<<1|1);
		else dfs(mid+1,r,now<<1|1),dfs(l,mid,now<<1);
	}
}t;
int nowl,nowr;
void insert()
{
	a[++nowr]={read(),read(),read()};
	if((nowr-nowl)*(nowr-nowl)>nowr*40) t.build(1,nowl=nowr);
	break;
}

莫队

普通莫队

1. 定义：对于序列上的区间询问问题，考虑每一个询问从上一个询问逐步拓展缩减区间得到答案，注意可能有 nowl>nowr 要先拓展，离线询问排序能做到 $O(m\sqrt n)$。
2. 实现：考虑分块，将询问按 <左端点块编号,右端点> 排序，设块长为 $\text B$，那么对于每个块中的询问，每个会将左端点移动 $O(B)$ 次，总体会将右端点移动 $O(n)$ 次，所以总共是 $O(mB+\frac {n^2} B)$ 次拓展缩减，$O(m)$ 次查询，假设操作 $O(1)$ 的话 $\text B$ 取 $\frac n {\sqrt m}$ 得到 $O(n\sqrt m)$，实际上 $\text B$ 取定值更简单有效。
3. 奇偶排序：上述排序在相邻块间转移时右端点会先移回左端再到右端，考虑在左端点为偶块时右端点降序排序就能有效减少冗余。

带修莫队

1. 修改相当于多了一维时间维度，修改操作可以看作是与当前的序列 $\text{swap}$，若在当前区间中则要进行维护，排序按 <左端点块编号,右端点块编号,时间> 排序，用类似的分析方法 $\text B$ 取 $O(\sqrt[3]{\frac {n^2t} m})$ 得到 $O(\sqrt[3]{n^2m^2t})$，同阶即为 $O(n^{\frac 5 3})$。

struct data{
	int l,r,id,t;
	bool operator <(const data &A)const
	{
		if(l/kuai!=A.l/kuai) return l<A.l;
		if(r/kuai!=A.r/kuai) return r<A.r;
		return t<A.t;
	}
}q[N];
struct change{int k,x;}ch[N];
int nowans,c[M];
void add(int x){if(!c[a[x]]++) nowans++;}
void del(int x){if(!--c[a[x]]) nowans--;}
void change(int x,int l,int r)
{
	int pos=ch[x].k;
	if(l<=pos&&pos<=r) del(pos),swap(ch[x].x,a[pos]),add(pos);
	else swap(ch[x].x,a[pos]);
}
void modui()
{
	sort(q+1,q+nq+1);
	int nowl=q[1].l,nowr=q[1].r,nowt=q[1].t;
	for(rint i=nowl;i<=nowr;i++) add(i);
	for(rint i=1;i<=nowt;i++) change(i,nowl,nowr);
	ans[q[1].id]=nowans;
	for(rint i=2;i<=nq;i++)
	{
		int l=q[i].l,r=q[i].r,t=q[i].t;
		while(nowl>l) add(--nowl);
		while(nowr<r) add(++nowr);
		while(nowl<l) del(nowl++);
		while(nowr>r) del(nowr--);
		while(nowt<t) change(++nowt,nowl,nowr);
		while(nowt>t) change(nowt--,nowl,nowr);
		ans[q[i].id]=nowans;
	}
}

回滚莫队

1. 定义：即只有拓展操作或只有缩减操作的莫队，复杂度 $O(n\sqrt m)$。
2. 实现：考虑只有拓展操作，询问按 <左端点块编号,右端点> 排序，如果当前询问换块了就推倒从块的右端点空区间开始，如果右端点在左端点块中就单独暴力扫，现在当前区间一定包含于询问区间，考虑先拓展右端点，然后备份，再拓展左端点回答询问，最后回退至备份，这样复杂度同样是 $O(n\sqrt m)$，共有 $O(m)$ 次备份操作，只缩减操作可以类似解决。

void add(int x){
	cnt[a[x]]++,nowans=max(nowans,cnt[a[x]]*b[a[x]]);
}
void modui()
{
	sort(q+1,q+1+m);
	for(rint i=1;i<=m;)
	{
		int nowkuai=q[i].l/kuai;
		while(i<=m&&q[i].r/kuai==nowkuai)
		{
			nowans=0;
			for(rint j=q[i].l;j<=q[i].r;j++) add(j);
			ans[q[i].id]=nowans;
			for(rint j=q[i].l;j<=q[i].r;j++) cnt[a[j]]--;
			i++;
		}
		nowans=0;
		int edge=min(n+1,(nowkuai+1)*kuai),l=edge,r=edge-1;
		while(i<=m&&q[i].l/kuai==nowkuai)
		{
			while(r<q[i].r) add(++r);
			int backup=nowans;
			while(l>q[i].l) add(--l);
			ans[q[i].id]=nowans;
			while(l<edge) cnt[a[l++]]--;
			nowans=backup;
			i++;
		}
		for(rint j=edge;j<=r;j++) cnt[a[j]]--;
	}
}

树上莫队

1. 定义：处理树上的路径询问问题，转化成 $\text{dfs}$ 序上的普通莫队，复杂度 $O(n\sqrt m)$。
2. 实现：$\text{dfs}$ 序列就是记录节点在 $\text{dfs}$ 进入和离开时的长为 $\text{2n}$ 的序列，考虑路径 $(x,y)$，先钦定 first[x]<first[y] ，这样当 $lca=x$ 时路径上的点就为 $[first[x],first[y]]$ 上出现一次的点，否则为 $[last[x],first[y]]$ 上出现一次的点加上 $lca$，容易用 $\text{bool}$ 记录出现次数实现决定点添加删除。

void add(int x)
{
	use[x]^=1;
	if(use[x]) nowans+=a[c[x]]*b[++cnt[c[x]]];
	else nowans-=a[c[x]]*b[cnt[c[x]]--];
}
void change(int x)
{
	if(use[ch[x].x]) add(ch[x].x),swap(ch[x].v,c[ch[x].x]),add(ch[x].x);
	else swap(ch[x].v,c[ch[x].x]);
}
void modui()
{
	sort(q+1,q+1+cntq);
	int nowl=q[1].l,nowr=nowl-1,nowt=0;
	for(rint i=1;i<=cntq;i++)
	{
		int l=q[i].l,r=q[i].r,t=q[i].t;
		while(nowl>l) add(o[--nowl]);
		while(nowr<r) add(o[++nowr]);
		while(nowl<l) add(o[nowl++]);
		while(nowr>r) add(o[nowr--]);
		if(q[i].fa) add(q[i].fa);
		while(nowt<t) change(++nowt);
		while(nowt>t) change(nowt--);
		ans[q[i].id]=nowans;
		if(q[i].fa) add(q[i].fa);
	}
}
signed main()
{
	for(rint i=1;i<=m;i++)
	if(read())
	{
		int x=read(),y=read(),fa=lca(x,y);
		if(first[x]>first[y]) swap(x,y);
		if(x==fa) q[++cntq]={first[x],first[y],0,cntc,cntq};
		else q[++cntq]={last[x],first[y],fa,cntc,cntq};
	}else ch[++cntc]={read(),read()};
	modui();
}

决策单调性

1. 区间包含单调性：$\forall a\le b\le c\le d$，$w(b,c)\le w(a,d)$

2. 四边形不等式：$\forall a\le b\le c\le d$，$w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，即交叉小于包含，若等号恒成立称为四边形恒等式。

3. 中点2D1D：$f_{l,r}=\min_{k=l}^{r-1}\{f_{l,k}+f_{k+1,r}\}+w(l,r)$

   1. 若 $w(l,r)$ 满足区间包含单调性和四边形不等式，则 $f_{l,r}$ 满足四边形不等式。

   2. 若 $f_{l,r}$ 满足四边形不等式，记 $m_{l,r}$ 表示最优决策点，则有 $m_{l,r-1}\le m_{l,r} \le m_{l+1,r}$，枚举量降为 $O(n^2)$。

      for(rint len=2;len<=n;len++)
      for(rint l=1,r=len;r<=n;l++,r++)
      {
          f[l][r]=p;
          for(rint k=m[l][r-1];k<=m[l+1][r];k++)
          if(f[l][r]>f[l][k]+f[k+1][r]+w(l,r))
              f[l][r]=f[l][k]+f[k+1][r]+w(l,r),m[l][r]=k;
      }
      

4. 分层2D1D：$f_{i,j}=\min_{k<j}\{f_{i-1,k}+w(k,j)\}$

   1. 若 $w(i,j)$ 满足四边形不等式，则 $f_{i,j}$ 满足四边形不等式，有 $m_{i-1,j}\le m_{i,j} \le m_{i,j+1}$，枚举量降为 $O((n+m)m)$，也可以将每一层间的转移看作指针1D1D，复杂度 $O(nm\log)$，这里分治时能使用类似莫队的方法求 $w(l,r)$，一次分治会移动 $O(m\log)$ 次。

   2. wqs 带权二分：若分 $k$ 层中每层的值是凸的则可以用带权二分去二分斜率切凸包上的点，二分每次划分的额外价值，check 划分1D1D分了几层即可，复杂度 $O(n\log)$，若值是整数那么斜率一定也是整数，为了处理共线要在每一次求得的切线在 $x=k$ 的值中取最优值，构造方案考虑扰动避免共线且保证凸性。

      int check(int mid)
      {
      	q[hh=tt=0]=0;
      	for(rint i=1;i<=n;i++)
      	{
      		while(hh<tt&&ti[hh+1]==i) hh++;
      		f[i]=f[q[hh]]+w(q[hh]+1,i)-mid,m[i]=m[q[hh]]+1;
      		while(hh<tt&&ti[tt]>=cal(q[tt],i)) tt--;
      		q[++tt]=i,ti[tt]=cal(q[tt-1],i);
      	}
      	ans=max(ans,f[n]+k*mid);
      	if(m[n]==k){cout<<ans<<endl;exit(0);}
      	return m[n];
      }
      signed main()
      {
      	int l=-p,r=1;
      	while(l+1<r)
      	{
      		int mid=(l+r)>>1;
      		if(check(mid)<k) l=mid;
      		else r=mid;
      	}
      	cout<<ans<<endl;
      }
      

5. 划分1D1D：$f_r=\min_{l=1}^{r-1}\{f_l+w(l,r)\}$

   1. 若 $w(l,r)$ 满足四边形不等式，则有 $m_l\le m_r$ 具有决策单调性。

   2. 若 $f_l+w(l,r)$ 满足单谷性且 $f$ 有决策单调性，双指针解决，复杂度 $O(n)$。

   3. 若 $w(l,r)$ 为凸函数，用凸函数二分栈/二分队列解决，复杂度 $O(n\log)$。

      凸函数二分队列：考虑 $w(l,r)$ 为下凸函数求最小值或上凸函数求最大值，后入队的元素衰减速度更快，元素入队时二分求出优于前面元素的时间，保证队列中迭代时间单调即可，复杂度 $O(n\log)$，若能 $O(1)$ 计算优于时间则为普通单调队列，本质上是简单维护凸壳。

      凸函数二分栈：考虑 $w(l,r)$ 为下凸函数求最大值或上凸函数求最小值，后入栈的元素增加速度更慢，元素入栈时二分求出优于前面元素的时间，保证队列中迭代时间单调即可，复杂度 $O(n\log)$，若能 $O(1)$ 计算优于时间则为普通单调栈，本质上是简单维护凸壳，与决策单调性无关。

   4. 若 $f$ 有决策单调性，可以 $\text{cdq}$ 分治套分治 $O(n\log^2)$ 或者二分队列 $O(n\log)$ 解决，$\text{cdq}$ 优势在于能类似莫队地维护 $w(l,r)$。

      void work(int l,int r,int kl,int kr)
      {
      	if(l>r||kl>kr) return;
      	int mid=(l+r)>>1,kmid=kl;
      	for(rint i=kl;i<=kr;i++)
      	{
      		int val=f[i]+w(i+1,mid)-cost;
      		if(val<f[mid]) f[mid]=val,m[mid]=m[i]+1,kmid=i;
      	}
      	work(l,mid-1,kl,kmid),work(mid+1,r,kmid,kr);
      }
      void cdq(int l,int r)
      {
      	if(l==r) return;
      	int mid=(l+r)>>1;
      	cdq(l,mid),work(mid+1,r,l,mid),cdq(mid+1,r);
      }
      

      二分队列：队列维护三元组 $(l,r,x)$ 表示 $m_{l\sim r}=x$，每次结算时更新队尾的一段 $m_{x\sim n}=i$ 插回队列即可。

      struct data{
      	int l,r,x;
      }q[N];
      int cal(int tt,int y)
      {
      	int l=max(q[tt].l,y),r=q[tt].r+1;
      	while(l+1<r)
      	{
      		int mid=(l+r)>>1;
      		if(f[q[tt].x]+w(q[tt].x+1,mid)<f[y]+w(y+1,mid)) r=mid;
      		else l=mid;
      	}
      	return r;
      }
      void work()
      {
      	q[hh=tt=0]={1,n,0};
      	for(rint i=1;i<=n;i++)
      	{
      		if(hh<=tt&&q[hh].r<i) hh++;
      		else q[hh].l=i;
      		f[i]=f[q[hh].x]+w(q[hh].x+1,i);
      		while(hh<=tt&&f[q[tt].x]+w(q[tt].x+1,q[tt].l)<=f[i]+w(i+1,q[tt].l)) tt--;
      		if(hh>tt) q[++tt]={i+1,n,i};
      		else
      		{
      			int x=cal(tt,i);
      			q[tt].r=x-1,q[++tt]={x,n,i};
      		}
      	}
      }
      

   5. 斜率优化：考虑 $w(l,r)=a(i)+b(j)+c(i)d(j)+C$，考虑变量 $b(j)+c(i)d(j)$ 是对若干直线在某点上取极值，需要维护插入直线维护极值，李超树能够 $O(n\log^2)$ 维护一般情况，不过通常会有性质 ① 插入斜率有序 ② 查询位置单调，①② 单调队列/单调栈就能维护，① 再在凸壳上二分位置就行。

6. 指针1D1D：$f_r=\min_{l=1}^{r-1}w(l,r)$

   1. 若 $w(l,r)$ 满足四边形不等式，则有 $m_l\le m_r$，定义分治过程 $(l,r,kl,kr)$ 求解 $f_{l\sim r}$ 且决策点在 $kl\sim kr$ 中，复杂度 $O(n\log)$。

      void work(int l,int r,int kl,int kr)
      {
      	if(l>r) return;
      	int mid=(l+r)>>1,kmid=kl;
      	for(rint i=kl;i<=min(kr,mid);i++)
      	{
      		int res=w(i,mid);
      		if(res>f[mid]) f[mid]=res,kmid=i;
      	}
      	work(l,mid-1,kl,kmid),work(mid+1,r,kmid,kr);
      }
      

7. 满足四边形不等式的性质：

   1. 若 $w_1(l,r),w_2(l,r)$ 满足四边形不等式（或区间包含单调性），则 $\forall c_1,c_2\ge0$，$c_1w_1(l,r)+c_2w_2(l,r)$ 也满足四边形不等式（或区间包含单调性）。
   2. 若存在 $f(x),g(x)$ 使得 $w(l,r)=f(r)-g(l)$，则 $w(l,r)$ 满足四边形恒等式。当 $f,g$ 单增时 $w(l,r)$ 还满足区间包含单调性。
   3. 若 $w(l,r)$ 满足四边形不等式和区间包含单调性，则对于单增下凸函数 $h(x)$ 有 $h(w(l,r))$ 满足四边形不等式和区间包含单调性，对于下凸函数 $h(x)$ 有 $h(w(l,r))$ 满足四边形不等式。

杂项

二维哈希

记一个矩阵 $a$ 的哈希值为

$$\sum_{i=1}^n\sum_{j=1}^ma_{i,j}p_1^{n-i}p_2^{m-j}$$

类似前缀和可以 $O(1)$ 求子矩阵哈希值，$H(x_2,y_2)-H(x_1-1,y_2)p_1^{x_2-x_1+1}-H(x_2,y_1-1)p_2^{y_2-y_1+1}+H(x_1-1,y_1-1)p_1^{x_2-x_1+1}p_2^{y_2-y_1+1}$。

枚举子矩形

暴力枚举端点是 $O(n^2m^2)$ 的，考虑先大力枚举行的两个端点，然后再利用前缀和的思想统计列，就是把左端贡献记在桶里，不断移右端查询并更新桶即可，可以做到 $O(n^2m)=O(S\sqrt S)$。

图三四元环计数

1. 无向图三元环计数：考虑将边定向，由度数小的连向度数大的，相同则按编号，考虑在形成的 DAG 直接枚举三元环的复杂度为 $\sum in_i\times out_i$ ，因为 $out_i\leq du_i$ 且 $du_{son\ of \ i}\geq du_i$ ，考虑 $out_i*out_i \leq \sum^{out_i}du_{son\ of \ i}\leq 2m$ ，所以 $out_i\leq \sqrt {2m}$ ，复杂度为 $O(m\sqrt m)$。

   for(rint i=1;i<=n;i++)
   {
       for(auto &it:e[i]) use[it]=1;
       for(auto &it:e[i]) for(auto &jt:e[it]) if(use[jt]) ans++;
       for(auto &it:e[i]) use[it]=0;
   }
   

2. 无向图四元环计数：同样定向并枚举，有向四元环有 $2+2$ 和 $3+1$ 两种形式，发现都可以被唯一表示为两侧无向边+有向边的形式，枚举四元环的一侧计数即可，复杂度为 $\sum du_i\times out_i$ 同理可得 $O(m\sqrt m)$。

   for(rint i=1;i<=n;i++)
   {
       for(auto it:ee[u]) for(auto jt:e[it]) if(rk[jt]>rk[i]) ans+=cnt[jt]++;
       for(auto it:ee[u]) for(auto jt:e[it]) cnt[jt]=0;
   }
   

3. 有向图三四元环计数：转无向图按无向图的做，在找到环的时候 check 一下是否合法即可。

树哈希

$O(n)$，有根树 $h[u]=\sum hash(h[v])$，无根树以重心为根即可，双重心就做两次。

mt19937_64 rd(19260817);
unordered_map<uint,uint> mp;

uint hsh(const uint x){return mp.find(x)==mp.end()?mp[x]=rd():mp[x];}
uint dfs(int x=1,int fa=1)
{
	uint ha=0;
	for(auto &it:e[x])
	if(it!=fa) ha+=hsh(dfs(it,x));
	return ha;
}

虚树

将关键点按 $\text{dfn}$ 排序，将相邻两点的 $\text{LCA}$ 加入后再次排序，单调栈求出连边关系。

void build()
{
    sort(a+1,a+num+1,cmp);
    for(rint i=2,nn=num;i<=nn;i++) a[++num]=lca(a[i-1],a[i]);
    sort(a+1,a+num+1,cmp),num=unique(a+1,a+num+1,Equal)-a-1;
    for(rint i=1;i<=num;i++) e[a[i]].clear();
    int top=0;
    for(rint i=1;i<=num;i++)
    {
        while(top&&dfn[stk[top]]+sz[stk[top]]-1<dfn[a[i]]) top--;
        if(top) e[stk[top]].push_back(a[i]),e[a[i]].push_back(stk[top]);
        stk[++top]=a[i];
    }
}

二项式反演

恰好和至少的转换：设 $f$ 表示恰好的方案数，$g$ 表示至少的方案数，则有：

$$g(i)=\sum_{j=i}^n\binom j i f(j)\Leftrightarrow f(i)=\sum_{j=i}^n(-1)^{j-i}\binom j i g(j)$$

恰好和至多的转换：设 $f$ 表示恰好的方案数，$g$ 表示至多的方案数，则有：

$$g(i)=\sum_{j=0}^i\binom i j f(j)\Leftrightarrow f(i)=\sum_{j=0}^i(-1)^{i-j}\binom i j g(j)$$

高维前缀和

$sum_i=\sum_{j \subseteq i} a_j$，暴力求是 $O(3^n)$ 的，考虑对于每一维分别做前缀和就可以做到 $O(n2^n)$，后缀和同理。

for(rint i=0;i<n;i++)
for(rint j=0;j<1<<n;j++)
if(j>>i&1) a[j]+=a[j^(1<<i)];

for(rint i=0;i<n;i++)	//后缀和
for(rint j=0;j<1<<n;j++)
if(!(j>>i&1)) a[j]+=a[j^(1<<i)];

线段树合并

考虑树上每个节点建一棵权值线段树维护子树信息，进行线段树合并时空复杂度都是 $O(n\log)$ 的，一般离线询问直接在原树上合并，需要在线询问则合并需要新开节点，空间带二倍常数，实际都是能开多大开多大。

int root[N],idx;
struct node{
	int ls,rs;data x;
}v[N*50];

int merge(int x,int y,int l=1,int r=n)
{
	if(!x||!y) return x|y;
	if(l==r) return v[x].x+=v[y].x,x;
	int mid=(l+r)>>1;
	v[x].ls=merge(v[x].ls,v[y].ls,l,mid),
	v[x].rs=merge(v[x].rs,v[y].rs,mid+1,r);
	v[x].x=v[x.ls].x+v[x.rs].x;
	return x;
}
void sel(int x=1,int fa=1)
{
	for(auto &it:e[x])
	if(it!=fa) sel(it,x),root[x]=merge(root[x],root[it]);
	ans[x]=ask(root[x]);
}

dsu on tree

也叫树上启发式合并或静态链分治，对于统计子树信息，考虑递归轻儿子并消除影响，再递归重儿子不消除影响，最后暴力加入所有轻儿子中的点的影响，这样启发式复杂度是 $O(n\log)$ 且空间为线性。

int sta[N],top,res,ans[N];
int f[1<<22];

void init(){
	res=0;
	while(top) f[sta[top--]]=-p;
}
void sel(int k,int x){
	res=max(res,f[k]+x);
	for(rint i=0;i<22;i++) res=max(res,f[k^1<<i]+x);
}
void add(int k,int x){
	sta[++top]=k,f[k]=max(f[k],x);
}
void selt(int x,int dep,int sum){
	sel(sum,dep);
	for(auto &it:e[x]) selt(it.to,dep+1,sum^1<<it.v);
}
void addt(int x,int dep,int sum){
	add(sum,dep);
	for(auto &it:e[x]) addt(it.to,dep+1,sum^1<<it.v);
}

void dfs(int x=1,int dep=1,int sum=0)
{
	for(auto &it:e[x])
	if(it.to!=son[x]) dfs(it.to,dep+1,sum^1<<it.v),init(),ans[x]=max(ans[x],ans[it.to]);;
	if(son[x]) dfs(son[x],dep+1,sum^1<<sone[x]),ans[x]=max(ans[x],ans[son[x]]),res=0;
	for(auto &it:e[x])
	if(it.to!=son[x]) selt(it.to,dep+1,sum^1<<it.v),addt(it.to,dep+1,sum^1<<it.v);
	add(sum,dep),sel(sum,dep),ans[x]=max(ans[x],res-2*dep);
}

猫树

1. 猫树：考虑对于线段树上的每个节点暴力记中点到左右端点的前缀和，那么对于一次询问只需要找到线段树上的 $\text{LCA}$ 进行一次合并，这样时间复杂度为 $O(n\log+q)$，空间复杂度为 $O(n\log)$，找 $\text{LCA}$ 需要将序列补为 $2^n$，$\text{LCA}$ 即为 $\text l,\text r$ 编号的 $\text{LCP}$，在猫树因为开空间的关系是每层节点共用一维空间，找到深度就行。

   struct tree{
   	int pos[N],v[21][N],suf[21][N];
   	void build(int l=1,int r=1<<(__lg(n)+1),int now=1,int d=1)
   	{
   		if(l==r) return pos[l]=now,void();
   		int mid=(l+r)>>1,sum,mxsum;
   		v[d][mid]=suf[d][mid]=mxsum=sum=a[mid];
   		for(rint i=mid-1;i>=l;i--)
   		{
   			sum+=a[i],mxsum=max(a[i],mxsum+a[i]);
   			v[d][i]=max(v[d][i+1],mxsum);
   			suf[d][i]=max(suf[d][i+1],sum);
   		}
   		v[d][mid+1]=suf[d][mid+1]=mxsum=sum=a[mid+1];
   		for(rint i=mid+2;i<=r;i++)
   		{
   			sum+=a[i],mxsum=max(a[i],mxsum+a[i]);
   			v[d][i]=max(v[d][i-1],mxsum);
   			suf[d][i]=max(suf[d][i-1],sum);
   		}
   		build(l,mid,now<<1,d+1),build(mid+1,r,now<<1|1,d+1);
   	}
   	int ask(int l,int r)
   	{
   		if(l==r) return a[l];
   		int d=__lg(pos[l])-__lg(pos[l]^pos[r]);
   		return max({v[d][l],v[d][r],suf[d][l]+suf[d][r]});
   	}
   }t;
   

2. 猫树分治：空间开不下时，可以离线询问然后分治解决，时间复杂度不变。

   struct tree{
   	int f[N][210];
   	void init(int l=1,int r=1<<(__lg(n)+1),int now=1)
   	{
   		if(l==r) return pos[l]=now,void();
   		int mid=(l+r)>>1;
   		init(l,mid,now<<1),init(mid+1,r,now<<1|1);
   	}
   	void work(int l=1,int r=1<<(__lg(n)+1),int now=1)
   	{
   		if(l==r) return;
   		int mid=(l+r)>>1,rr=min(r,n);
   		for(rint i=0;i<=200;i++) f[mid][i]=f[mid+1][i]=0;
   		
   		for(rint i=200;i>=w[mid];i--) f[mid][i]=v[mid];
   		for(rint i=mid-1;i>=l;i--)
   		{
   			for(rint j=0;j<=200;j++) f[i][j]=f[i+1][j];
   			for(rint j=200;j>=w[i];j--) f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
   		}
   		
   		for(rint i=200;i>=w[mid+1];i--) f[mid+1][i]=v[mid+1];
   		for(rint i=mid+2;i<=rr;i++)
   		{
   			for(rint j=0;j<=200;j++) f[i][j]=f[i-1][j];
   			for(rint j=200;j>=w[i];j--) f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
   		}
   		
   		for(auto &it:q[now])
   		for(rint i=0;i<=it.x;i++)
   			ans[it.id]=max(ans[it.id],f[it.l][i]+f[it.r][it.x-i]);
   		work(l,mid,now<<1),work(mid+1,r,now<<1|1);
   	}
   	void ask(int l,int r,int x,int i)
   	{
   		if(l==r) ans[i]=(w[l]<=x?v[l]:0);
   		else q[pos[l]>>(__lg(pos[l]^pos[r])+1)].push_back({l,r,x,i});
   	}
   }t;
   

带状高消

一个矩阵所有有值的位置距离主对角线 $\le d$ 称为带状矩阵，消元可以做到 $O(nd^2)$ 的复杂度。具体地，考虑高斯消元时内层消元时只考虑周围 $d^2$ 的有值的区域，在找主元系数为 $0$ 时交换列仍然不会破坏带状的性质，也可以交换行向量，这样横向的 $d$ 可能变为 $2d$，带 $2$ 倍常数。

void gauss()
{
	const int d=3;
	for(rint i=1;i<=m;i++)
	{
		if(!a[i][i])
		for(rint j=i+1;j<=min(i+d,m);j++)
		if(a[j][i])
		{
			for(rint k=i;k<=min(i+2*d,m);k++) swap(a[i][k],a[j][k]);
			swap(a[i][m+1],a[j][m+1]);
			break;
		}
		if(!a[i][i]) continue;
		for(rint j=i+1;j<=min(i+d,m);j++)
		{
			int res=a[j][i]*qp(a[i][i])%p;
			for(rint k=i;k<=min(i+2*d,m);k++)
				a[j][k]=(a[j][k]-a[i][k]*res%p+p)%p;
			a[j][m+1]=(a[j][m+1]-a[i][m+1]*res%p+p)%p;
		}
	}
	for(rint i=m;i;i--)
	{
		for(rint j=i+1;j<=min(i+2*d,m);j++)
			a[i][m+1]=(a[i][m+1]-a[i][j]*a[j][m+1]%p+p)%p,a[i][j]=0;
		a[i][m+1]=a[i][m+1]*qp(a[i][i])%p,a[i][i]=1;
	}
}

如果是一个带状矩阵加上一个三角矩阵，可以用类似的方法做到 $O(n^2d)$，此时就只能交换列不然会破坏性质。

void gauss()
{
	const int d=3;
	for(rint i=1;i<=n;i++) fr[i]=i;
	for(rint i=1;i<=n;i++)
	{
		if(!a[i][i])
		for(rint j=i+1;j<=min(n,i+d);j++)
		if(a[j][i])
		{
			for(rint k=1;k<=n;k++) swap(a[k][i],a[k][j]);
			swap(fr[i],fr[j]);
			break;
		}
		if(!a[i][i]) continue;
		int inv=qp(a[i][i]);
		for(rint j=i+1;j<=n;j++)
		{
			int res=inv*a[j][i]%p;
			for(rint k=i;k<=min(n,i+d);k++)
				a[j][k]=(a[j][k]-a[i][k]*res%p+p)%p;
			a[j][n+1]=(a[j][n+1]-a[i][n+1]*res%p+p)%p;
		}
	}
	for(rint i=n;i;i--)
	{
		for(rint j=i+1;j<=min(n,i+d);j++)
			a[i][n+1]=(a[i][n+1]-a[j][n+1]*a[i][j]%p+p)%p,a[i][j]=0;
		a[i][n+1]=a[i][n+1]*qp(a[i][i])%p,a[i][i]=1;
		ans[fr[i]]=a[i][n+1];
	}
}