模板合集
目录A - 基本算法。
快速幂
ll qpow(ll a,int b){
ll res=1ll;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;b>>=1;
}
return res;
}
B - 数据结构。
树状数组
单点加，区间查：
//BIT
ll c[N];
int tot;
void ins(int x,ll v){//x!=0
for(;x<=tot;x+=x&(-x)) c[x]+=v;
}
ll qry(int x){//x 可以 =0
ll res=0;
for(;x;x-=x&(-x)) res+=c[x];
return res;
}
求全局第 k 小：
int kth(int k){
int p=1<<_log;//_log=ceil(log n)
for(int i=_log-1;~i;i--){
int lc=p-(1<<i);
if(k<=c[lc]) p=lc;//走左子
else k-=c[lc];//左端点右移到 lc+1
}
}
线段树
标记永久化：
修改：
- 在途径的每个区间 sum 加上 w 会产生的贡献：w 与交集大小的乘积。
- 碰到被修改区间完全覆盖的区间时打上 add 标记，说明 w 作用于该区间每个位置。
查询：
-
被完全覆盖区间只贡献 sum。
-
沿路的非完全覆盖区间 add 都贡献给 当前区间与查询区间的交集。
用途：
- 动态开点线段树如果不想下放懒标记时把空儿子建出来。
//permanent tag
const int pd=N<<2;//4N
ll sum[pd],add[pd];
void cg(int s,int e,ll w,int k=1,int l=1,int r=n){
sum[k]+=(min(r,e)-max(l,s)+1)*w;
if(s<=l&&r<=e) return add[k]+=w,void();
if(s<=mid) cg(s,e,w,lc,l,mid);
if(e>mid) cg(s,e,w,rc,mid+1,r);
}
ll qry(int s,int e,int k=1,int l=1,int r=n){
if(s<=l&&r<=e) return sum[k];
ll cur=(min(r,e)-max(l,s)+1)*add[k];
if(s<=mid) cur+=qry(s,e,lc,l,mid);
if(e>mid) cur+=qry(s,e,rc,mid+1,r);
return cur;
}
动态开点线段树：
空间 2N。
//dynamic building SGT
#define mid ((l+r)>>1)
#define lc t[k].ls
#define rc t[k].rs
const int pd=N<<1;//2N
int nc,rt;
struct node{
int ls,rs;
ll sum,tag;
}t[pd];
void upd(int k){
t[k].sum=t[lc].sum+t[rc].sum;
}
void one(int &k,int l,int r,ll w){//下放时若儿子不存在要新建儿子
if(!k) k=++nc;
t[k].sum+=(r-l+1)*w;
t[k].tag+=w;
}
void dwn(int k,int l,int r){
if(t[k].tag){
ll &w=t[k].tag;
one(lc,l,mid,w);one(rc,mid+1,r,w);
w=0;
}
}
void cg(int s,int e,ll w,int &k,int l=1,int r=n){
if(!k) k=++nc;
if(s<=l&&r<=e) return one(k,l,r,w);
dwn(k,l,r);
if(s<=mid) cg(s,e,w,lc,l,mid);
if(e>mid) cg(s,e,w,rc,mid+1,r);
upd(k);
}
ll qry(int s,int e,int k,int l=1,int r=n){
if(!k) return 0;
if(s<=l&&r<=e) return t[k].sum;
dwn(k,l,r);
ll res=0;
if(s<=mid) res=qry(s,e,lc,l,mid);
if(e>mid) res+=qry(s,e,rc,mid+1,r);
return res;
}
线段树合并&分裂：
空间 2nlogN。n 为插入元素个数，N 为线段树范围。40倍左右。
分裂：
- 将 SGT 分为两个副本，x 中只保留 <=key 的树枝，y 中 >key。
- 副本树的左右子没有变，只是比原树少了一些枝。
- 原树 p 往左子走，x,y 就都往左子走。同方向。
- 除非 mid==val，否则若 mid 归 x ，就有
x=p。
//merge,split SGT
#define mid ((l+r)>>1)
#define lc(p) t[p].ls
#define rc(p) t[p].rs
const int pd=N*40;//
int nc;
struct node{
int ls,rs,ct;
}t[pd];
void upd(int k){
t[k].ct=t[lc(k)].ct+t[rc(k)].ct;
}
int merge(int p,int q){
if(!p||!q) return p^q;
t[p].ct+=t[q].ct;
lc(p)=merge(lc(p),lc(q));
rc(p)=merge(rc(p),rc(q));
upd(p);
}
/*可持久化
int merge(int p,int q){
if(!p||!q) return p^q;
int u=++nc;
t[u].ct=t[p].ct+t[q].ct;
lc(u)=merge(lc(p),lc(q));
rc(u)=merge(rc(p),rc(q));
upd(u);
}
*/
void spv(int val,int p,int l,int r,int &x,int &y){//split by val
if(!p) return x=y=0,void();//动态开点可能有空点
if(mid<val) x=p,y=++nc,spv(val,rc(p),mid+1,r,rc(x),rc(y));
else if(mid==val) x=++nc,y=++nc,lc(x)=lc(p),rc(y)=rc(q);
else y=p,x=++nc,spv(val,lc(p),l,mid,lc(x),lc(y));
upd(x),upd(y);
}
void spz(int sz,int p,int l,int r,int &x,int &y){//split by cnt
if(!p) return x=y=0,void();
int cnt=t[lc(p)].ct;
if(cnt<sz) x=p,y=++nc,spz(sz,rc(p),mid+1,r,rc(x),rc(y));
else if(cnt==sz) x=++nc,y=++nc,lc(x)=lc(p),rc(y)=rc(p);
else y=p,x=++nc,spz(sz,lc(p),l,mid,lc(x),lc(y));
upd(x),upd(y);
}
主席树（ 可持久化权值线段树 ）：
空间 N<<5。（单点加）
- 可作为线段树的前缀和使用。
- 可解决区间第 k 小。
- 和动态开点不同，每次都要新建点 p，不管 p 是否有值。
//主席树
#define mid ((l+r)>>1)
#define lc(p) t[p].ls
#define rc(p) t[p].rs
const int pd=N<<5;
int nc;
struct node{
int ls,rs,ct;
}t[pd];
void ins(int &p,int q,int x,int w,int l=1,int r=n){
p=++nc;//每次都要新建点
t[p]=t[q];t[p].ct+=w;
if(x<=mid) ins(lc(p),lc(q),x,w,l,mid);
else ins(rc(p),rc(q),x,w,mid+1,r);
}
//主席树区间修改，标记永久化
#define mid ((l+r)>>1)
#define lc(p) t[p].ls
#define rc(p) t[p].rs
const int pd=(N<<6)+10;
int nc;
struct node{
int ls,rs;
ll sum,add;
}t[pd];
void cg(int &p,int q,int s,int e,ll w,int l=1,int r=n){
p=++nc;t[p]=t[q];
t[p].sum+=(min(r,e)-max(l,s)+1)*w;
if(s<=l&&r<=e) return t[p].add+=w,void();
if(s<=mid) cg(lc(p),lc(q),s,e,w,l,mid);
if(e>mid) cg(rc(p),rc(q),s,e,w,mid+1,r);
}
ll qry(int p,int s,int e,int l=1,int r=n){
if(!p) return 0;
if(s<=l&&r<=e) return t[k].sum;
ll cur=(min(r,e)-max(l,s)+1)*t[k].add;
if(s<=mid) cur+=qry(lc(p),s,e,l,mid);
if(e>mid) cur+=qry(rc(p),s,e,mid+1,r);
return cur;
}
李超线段树：
//李超线段树
const int pd=N<<1;//动态开点，若无 merge
#define mid ((l+r)>>1)
#define lc(k) t[k].ls
#define rc(k) t[k].rs
struct func{
ll k,b;
func(){}
func(ll K,ll B):k(K),b(B){}
ll calc(ll x){
return k*x+b;
}
};
struct node{
int ls,rs;
func f;
}t[pd];
int nc,rt[N];
void ins(int &p,int l,int r,func g){
if(!p){
p=++nc;t[p].f=g;
return;
}
ll fl=t[p].f.calc(l),fr=t[p].f.calc(r),
gl=g.calc(l),gr=g.calc(r);
if(fl>=gl&&fr>=gr) return;
else if(gl>=fl&&gr>=fr) return t[p].f=g,void();
if(t[p].f.calc(mid)<g.calc(mid))
swap(t[p].f,g),swap(fl,gl);
if(gl>=fl) ins(lc(p),l,mid,g);
else ins(rc(p),mid+1,r,g);
}
void cg(int &p,int s,int e,func g,int l=1,int r=n){
if(!p) p=++nc;
if(s<=l&&r<=e) return ins(p,l,r,g);
if(s<=mid) cg(lc(p),s,e,g,l,mid);
if(e>mid) cg(rc(p),s,e,g,mid+1,r);
}
int merge(int p,int q,int l=1,int r=n){
if(!p||!q) return p^q;
lc(p)=merge(lc(p),lc(q),l,mid);
rc(p)=merge(rc(p),rc(q),mid+1,r);
ins(p,l,r,t[q].f);
return p;
}
ll qry(int x,int p,int l=1,int r=n){
if(!p) return -INF;
if(l==r) return t[p].f.calc(x);
if(x<=mid) return max(t[p].f.calc(x),qry(x,lc(p),l,mid));//标记永久化
else return max(t[p].f.calc(x),qry(x,rc(p),mid+1,r));//沿路 f 都作用于 x
}
楼房重建式线段树：
https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html
维护全局所有前缀最大值的信息。
mx[k]：区间最大值。ct[k]：只考虑该区间内所有数时，右子区间的答案（信息“和”）。叶子处无定义。calc(k,pre)：考虑在该区间前有个最大值 pre 的影响时，该区间内的答案。
平衡树
splay：
//splay
#define lc(p) t[p].son[0]
#define rc(p) t[p].son[1]
#define fa(p) t[p].fa
int nc,rt;
struct node{
int son[2],fa;
//lc:val<=t[x].val
//rc:val>t[x].val
int val,sz;
bool rev;
void mkrev(){
swap(lc,rc);rev^=1;
}
}t[N];
int nd(int p,int val){
int x=++nc;
fa(x)=p;
t[p].son[val>t[p].val]=x;
t[x].val=val;t[x].sz=1;
return x;
}
void upd(int x){
t[x].sz=t[lc(x)].sz+1+t[rc(x)].sz;
}
void dwn(int x){
if(t[x].rev){
if(lc(x)) t[lc(x)].mkrev();
if(rc(x)) t[rc(x)].mkrev();
t[x].rev=0;
}
}
int dir(int x){
return rc(fa(x))==x;
}
void rotate(int x){
int y=fa(x),z=fa(y),k=dir(x);
int b=t[x].son[k^1];
fa(x)=z;if(z) t[z].son[dir(y)]=x;
t[y].son[k]=b;fa(b)=y;
t[x].son[k^1]=y;fa(y)=x;
upd(y);upd(x);
}
void splay(int x,int tar){
int p;
while(p=t[x].fa,p!=tar){
if(fa(p)!=tar) rotate(dir(x)==dir(p)?p:x);
rotate(x);
}
if(!tar) rt=x;
}
int find(int val){
int x=rt;
while(x){
dwn(x);
if(t[x].val==val) return x;
x=t[x].son[val>t[x].val];
}
return 0;
}
int mx(int x){
while(dwn(x),rc(x)) x=rc(x);
return x;
}
void ins(int val){
int x=rt,p=0;
while(x){
dwn(x);p=x;
x=t[x].son[val>t[x].val];
}
x=nd(p,val);
splay(x,0);
}
void del(int val){
int x=find(val);
if(!x) return;
splay(x,0);
if(lc(x)){
int p=mx(lc(x));splay(p,x);
t[p].fa=0;rt=p;
rc(p)=rc(x);fa(rc(x))=p;
}
else rt=rc(x),fa(rc(x))=0;
}
int ask_rk(int val){
int x=rt,p=0,ct=0;
while(x){
dwn(x);p=x;
if(t[x].val<val){
ct+=t[lc(x)].sz+1;
x=rc(x);
}
else x=lc(x);
}
splay(p,0);
return ct+1;//+1
}
int ask_val(int k){
int x=rt,p=0,res=0;
while(x){
dwn(x);p=x;
if(t[lc(x)].sz+1==k){
res=t[x].val;break;
}
else if(k<=t[lc(x)].sz) x=lc(x);
else k-=t[lc(x)].sz+1,x=rc(x);
}
splay(p,0);
return res;
}
int prev(int val){
int x=rt,p=0,res=0;
while(x){
dwn(x);p=x;
if(t[x].val>=val) x=lc(x);
else{
res=max(res,t[x].val);
x=rc(x);
}
}
splay(p,0);
return res;
}
int sufv(int val){
int x=rt,p=0,res=INF;
while(x){
dwn(x);p=x;
if(t[x].val<=val) x=rc(x);
else{
res=min(res,t[x].val);
x=lc(x);
}
}
splay(p,0);
return res;
}
fhq_treap：
//fhq_treap
namespace BST {
int nClock, root;
struct node {
int lc, rc;
int val, key;
int sze;
bool rev;
void mk_rev() {
std::swap(lc, rc);
rev ^= 1;
}
} t[N];
int create(int val) {
int p = ++ nClock;
t[p].lc = t[p].rc = 0;
t[p].val = val, t[p].key = rand();
t[p].sze = 1;
t[p].rev = 0;
return p;
}
/* 可持久化平衡树
int copy(int q) {
int p = ++ nClock; t[p] = t[q];
return p;
}
*/
void upd(int p) {
t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1;
}
void spread(int p) {
if (t[p].rev) {
if (t[p].lc) t[t[p].lc].mk_rev();
if (t[p].rc) t[t[p].rc].mk_rev();
t[p].rev ^= 1;
}
}
/* 可持久化平衡树
void spread(int p) {
if (t[p].rev) {
if (t[p].lc) t[p].lc = copy(t[p].lc), t[t[p].lc].mk_rev();
if (t[p].rc) t[p].rc = copy(t[p].rc), t[t[p].rc].mk_rev();
t[p].rev = 0;
}
}
*/
void split_v(int p, int val, int &x, int &y) {//拆成两棵并集为p，交集为空的树
if (!p)
x = y = 0;
else {
spread(p);
if (t[p].val <= val)
x = p, split_v(t[p].rc, val, t[x].rc, y);
else
y = p, split_v(t[p].lc, val, x, t[y].lc);
upd(p);//p
}
}
void split_s(int p, int sze, int &x, int &y) {
if (!p)
x = y = 0;
else {
spread(p);
if (t[t[p].lc].sze < sze)
x = p, split_s(t[p].rc, sze - t[t[p].lc].sze - 1, t[x].rc, y);
else
y = p, split_s(t[p].lc, sze, x, t[y].lc);
upd(p);
}
}
/* 可持久化平衡树
void split_v(int p, int val, int &x, int &y) {
if (!p)
x = y = 0;
else {
p = copy(p), spread(p);
if (t[p].val <= val)
x = p, split_v(t[p].rc, val, t[x].rc, y);
else
y = p, split_v(t[p].lc, val, x, t[y].lc);
upd(p);
}
}
void split_s(int p, int sze, int &x, int &y) {
if (!p)
x = y = 0;
else {
p = copy(p), spread(p);
if (t[t[p].lc].sze < sze)
x = p, split_s(t[p].rc, sze - t[t[p].lc].sze - 1, t[x].rc, y);
else
y = p, split_s(t[p].lc, sze, x, t[y].lc);
upd(p);
}
}
*/
int merge(int p, int q) {//val[p]<val[q]
if (!p || !q) return p ^ q;
if (t[p].key > t[q].key) {
spread(p);
t[p].rc = merge(t[p].rc, q), upd(p);
return p;
} else {
spread(q);
t[q].lc = merge(p, t[q].lc), upd(q);
return q;
}
}
/* 可持久化平衡树
int merge(int p, int q) {
if (!p || !q) return p ^ q;
if (rand() % (t[p].sze + t[q].sze) < t[p].sze) {
spread(p);
t[p].rc = merge(t[p].rc, q), upd(p);
return p;
} else {
spread(q);
t[q].lc = merge(p, t[q].lc), upd(q);
return q;
}
}
*/
}
笛卡尔树
//笛卡尔树
//key:BST
//val:heap
#define lc(k) t[k].ls
#define rc(k) t[k].rs
struct node{
int ls,rs;
}t[N];
int rt;
void build(){
static int tp,stk[N];
//sort by key
F(i,1,n){
int k=tp;
while(k&&a[stk[k]]<a[i]) k--;
if(k) rc(stk[k])=i;//注意是 stk 中第 k 个，stk[k] 而非 k
if(k<tp) lc(i)=stk[k+1];
stk[tp=k+1]=i;
}
rt=stk[1];
}
分块
B=sqrt(n);
int t=0;
for(int i=B;i<=n;i+=B) ++t,bl[t]=i-B+1,br[t]=i;
if(br[t]<n) t++,bl[t]=br[t-1]+1,br[t]=n;
F(i,1,n) be[i]=(i-1)/B+1;
莫队
普通莫队：
int n,m,a[N];
int B,be[N];
struct qry{
int l,r,id;
void sc(int i){
id=i;l=rd();r=rd();
}
bool operator <(const qry &o)const{
return be[l]^be[o.l]?be[l]<be[o.l]:(be[l]&1?r<o.r:r>o.r);
}
}q[M];
int main(){
F(i,1,n) be[i]=(i-1)/B+1;
F(i,1,m) q[i].sc(i);
sort(q+1,q+1+m);
int l=1,r=0;
F(i,1,m){
while(r<q[i].r) ins(++r);
while(l>q[i].l) ins(--l);
while(r>q[i].r) del(r--);
while(l<q[i].l) del(l++);
ans[q[i].id]=...;
}
}
带修莫队：
- 普通莫队是不支持修改的。
- 可以给每个询问附加一个时间戳 t，来表示回答该次询问时已经经过了多少次修改。转化为三维莫队。
- 把询问操作 前两维按块编号，第三维按 t 排序。
- 当 n,m 同阶时，分块大小 $O(n^{\frac 2 3})$，时间复杂度 $O(n^{\frac 5 3})$。
- 当 n,m 不同阶时，分块大小$O(nm^{-\frac 1 3})$，时间复杂度 $O(nm^{\frac 2 3})$。
int n,m,mc,mq,a[N];
int B,be[N];
struct cg{
int x,v;
}c[M];
struct qry{
int l,r,t,id;
bool operator <(const qry &o)const{
if(be[l]^be[o.l]) return be[l]<be[o.l];
if(be[r]^be[o.r]) return be[r]<be[o.r];
return t<o.t;
}
}q[M];
int ans[M];
int main(){
F(i,1,n) be[i]=(i-1)/B+1;
F(i,1,m){
if(op[0]=='C'){
mc++;
cin>>c[mc].x>>c[mc].v;
}
else{
mq++;
cin>>q[mq].l>>q[mq].r;
q[mq].id=mq;q[mq].t=mc;
}
}
sort(q+1,q+1+mq);
int l=1,r=0,t=0;
F(i,1,mq){
while(r<q[i].r) ins(a[++r]);
while(l>q[i].l) ins(a[--l]);
while(r>q[i].r) del(a[r--]);
while(l<q[i].l) del(a[l++]);
while(t<q[i].t){
t++;
int x=c[t].x;
if(q[i].l<=x&&x<=q[i].r) dec(a[x]),add(c[t].v);
swap(a[x],c[t].v);//不管是否对当前答案有影响，时间到了这个操作就要做进去
//把 a 原先值存进 c 里，回溯时把 c 的值还原给 a 即可
}
while(t>q[i].t){
int x=c[t].x;
if(q[i].l<=x&&x<=q[i].r) dec(a[x]),add(c[t].v);//操作和上面一样
swap(a[x],c[t].v);
t--;
}
ans[q[i].id]=...;
}
}
回滚莫队：
#include<bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(int i=l;i<=r;i++)
int rd(){
#define gc getchar
int x=0,f=1;char c=gc();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return x*f;
}
const int N=1e5+10,M=1e6+10,S=35;
int n,m,Q,B,bl[N],fa[N],s[N],xov[N],z[N][S],lim[N],*stk[M],val[M],tp,ans[N];
struct edge{
int u,v,w;
void sc(){
u=rd();v=rd();w=rd();
}
}e[N];
struct ask{
int l,r,a,b,id;
void sc(int i){
id=i;l=rd();r=rd();a=rd();b=rd();
}
bool operator <(const ask &rhs)const{
return bl[l]^bl[rhs.l]?bl[l]<bl[rhs.l]:r<rhs.r;
}
}q[N];
void cge(int *it,int v){
stk[++tp]=it;val[tp]=*it;*it=v;
}
void back(int t){
while(tp>t) *stk[tp]=val[tp],tp--;
}
void basIns(int x,int v){
for(int i,j=lim[x];v&&(i=std::__lg(v))>=j;){
if(!z[x][i]){
cge(z[x]+i,v);
if(lim[x]==i)
while(lim[x]<=30&&z[x][lim[x]]) cge(lim+x,lim[x]+1);
return;
}
v^=z[x][i];
}
}
void ins(int id){
int x=e[id].u,y=e[id].v,w=e[id].w;
for(;x^fa[x];x=fa[x]) w^=xov[x];
for(;y^fa[y];y=fa[y]) w^=xov[y];
if(x==y) return basIns(x,w);
if(s[x]<s[y]) std::swap(x,y);
cge(fa+y,x);
cge(s+x,s[x]+s[y]);
cge(xov+y,w);
for(int i=30;~i;--i)if(z[y][i]) basIns(x,z[y][i]);
}
int qry(int a,int b){
int res=0;
for(;a^fa[a];a=fa[a]) res^=xov[a];
for(;b^fa[b];b=fa[b]) res^=xov[b];
if(a!=b) return -1;
for(int i=30;~i;--i)
res=std::max(res,res^z[a][i]);
return res;
}
int main(){
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
n=rd();m=rd();Q=rd();
B=sqrt(m);
F(i,1,m) e[i].sc(),bl[i]=(i-1)/B+1;
F(i,1,n) fa[i]=i,s[i]=1;
F(i,1,Q) q[i].sc(i);
std::sort(q+1,q+1+Q);
for(int b=1,i=1;b<=bl[m]&&i<=Q;back(0),b++)
for(int p=b*B,t;i<=Q&&bl[q[i].l]==b;++i){
if(bl[q[i].r]==b){
F(j,q[i].l,q[i].r) ins(j);
ans[q[i].id]=qry(q[i].a,q[i].b);
back(0);continue;
}
while(p<q[i].r) ins(++p);
t=tp;
F(j,q[i].l,b*B) ins(j);
ans[q[i].id]=qry(q[i].a,q[i].b);
back(t);
}
F(i,1,Q) std::cout<<ans[i]<<"\n";
return 0;
}
树上莫队：
- 欧拉序：进入该节点时记作
in，从该结点离开时记作out。 - 对于路径 x->y，令 $in_x<in_y$：
- 若 lca(x,y)=x，则 $[in_x,in_y]$ 中只出现过一次的点为路径上点。
- 否则，$[out_x,in_y]$ 中只出现过一次的点和 lca 为路径上点。
int n, m;
int a[N];
int tot, head[N], ver[N * 2], Next[N * 2];
void add_edge(int u, int v) {
ver[++ tot] = v; Next[tot] = head[u]; head[u] = tot;
}
int dep[N];
int anc[logN + 1][N];
int In[N], Out[N];
int eul_len, eul[N * 2];
int Bn;
int belong[N * 2];
void dfs(int u, int fu) {
dep[u] = dep[fu] + 1;
anc[0][u] = fu;
for (int i = 1; i <= logN; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
eul[++ eul_len] = u, In[u] = eul_len;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (v == fu) continue;
dfs(v, u);
}
eul[++ eul_len] = u, Out[u] = eul_len;
}
int lca(int x, int y) {
if (dep[x] > dep[y]) std::swap(x, y);
for (int i = logN; i >= 0; i --)
if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
if (x == y) return x;
for (int i = logN; i >= 0; i --)
if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
return anc[0][x];
}
struct ask {
int l, r, z, id;
bool operator < (const qry &rhs) const {
if (belong[l] ^ belong[rhs.l]) return l < rhs.l;
return belong[l] & 1 ? r < rhs.r : r > rhs.r;
}
} q[M];
int ans[M];
bool state[N];
void attend(int p) {
state[p] ^= 1;//路径中出现2次的点会被抵消
state[p] ? add(a[p]) : dec(a[p]);
}
int main() {
dfs(1, 0);
for (int i = 1, x, y, z; i <= m; i ++) {
std::cin >> x >> y, z = lca(x, y);
if (In[x] > In[y]) std::swap(x, y);
if (z == x)
q[i].l = In[x], q[i].r = In[y], q[i].z = 0, q[i].id = i;
else
q[i].l = Out[x], q[i].r = In[y], q[i].z = z, q[i].id = i;
}
for (int i = 1; i <= eul_len; i ++) belong[i] = (i - 1) / Bn + 1;
sort(q + 1, q + 1 + m, cmp);
int l = 1, r = 0;
for (int i = 1; i <= m; i ++) {
while (r < q[i].r) attend(eul[++ r]);
while (l > q[i].l) attend(eul[-- l]);
while (r > q[i].r) attend(eul[r --]);
while (l < q[i].l) attend(eul[l ++]);
if (q[i].z)
// Calculate ans[q[i].id] with q[i].z
else
// Calculate ans[q[i].id]
}
}
LCA
倍增：
void dfs(int u,int fth){
anc[0][u]=fth;
dep[u]=dep[fth]+1;
F(j,1,S-1)if(anc[j-1][u])
anc[j][u]=anc[j-1][anc[j-1][u]];
else break;
for(int v:ver[u])if(v^fth)
dfs(v,u);
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int j=S-1;j>=0;j--)
if(dep[anc[j][x]]>=dep[y])
x=anc[j][x];
if(x==y) return x;
for(int j=S-1;j>=0;j--)
if(anc[j][x]^anc[j][y])
x=anc[j][x],y=anc[j][y];
return anc[0][x];
}
重链剖分：
int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
欧拉序 & ST 表：
- 欧拉序1：第一次访问到该点记为 $fir_x$，以后每次回溯到 x 都把 x 加入欧拉序列。
- 假设 $fir_x<fir_y$，$[fir_x,fir_y]$ 中深度最小的点即为 lca。
const int M=N<<1;
int eu[M],z[S][M];
void dfs(int u,int fth){
dep[u]=dep[fth]+1;
eu[++len]=u;fir[u]=len;
for(int v:ver[u])if(v^fth){
dfs(v,u);
eu[++len]=u;
}
}
int bet(int x,int y){
return dep[x]<dep[y]?x:y;
}
int lca(int x,int y){
x=fir[x];y=fir[y];
if(x>y) swap(x,y);
int k=Log[y-x+1];
return bet(z[k][x],z[k][y-(1<<k)+1]);
}
int main(){
dfs(1,0);
Log[0]=-1;
F(i,1,len) z[0][i]=eu[i],Log[i]=Log[i>>1]+1;
F(j,1,S-1) F(i,1,n-(1<<j)+1)
z[j][i]=bet(z[j-1][i],z[j-1][i+1<<(j-1)]);
}
LCT
namespace LCT {
struct node {
int son[2], Fa;
int sze;
int vir;
bool rev;
#define lc son[0]
#define rc son[1]
void init() {
lc = rc = 0, Fa = 0;
sze = 1;
vir = 0;
rev = 0;
}
void mk_rev() {
std::swap(lc, rc);
rev ^= 1;
}
} t[N];
void upd(int p) {
t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1 + t[p].vir;
}
void spread(int p) {
if (t[p].rev) {
if (t[p].lc) t[t[p].lc].mk_rev();
if (t[p].rc) t[t[p].rc].mk_rev();
t[p].rev = 0;
}
}
int dir(int x) {
return t[t[x].Fa].rc == x;
}
bool is_top(int x) {
return t[t[x].Fa].lc != x && t[t[x].Fa].rc != x;
}
void rotate(int x) {
int y = t[x].Fa, z = t[y].Fa, k = dir(x);
t[x].Fa = z; if (!is_top(y)) t[z].son[t[z].rc == y] = x;
t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
t[x].son[k ^ 1] = y, t[y].Fa = x;
upd(y), upd(x);
}
void splay(int x) {
static int top, stk[N], p;
stk[top = 1] = x;
for (p = x; !is_top(p); p = t[p].Fa) stk[++ top] = t[p].Fa;
while (top) spread(stk[top --]);
while (p = t[x].Fa, !is_top(x)) {
if (!is_top(p)) rotate(dir(x) == dir(p) ? p : x);
rotate(x);
}
}
void access(int x) {
for (int y = 0; x; y = x, x = t[x].Fa) {
splay(x);
t[x].vir += t[t[x].rc].sze - t[y].sze;
t[x].rc = y;
upd(x);
}
}
void make_root(int x) {
access(x), splay(x), t[x].mk_rev();
}
void link(int x, int y) {
if (find_root(x) == find_root(y)) return;
make_root(x), make_root(y);
t[x].Fa = y, t[y].vir += t[x].sze, t[y].sze += t[x].sze;
}
void cut(int x, int y) {
make_root(x), access(y), splay(y);
if (t[y].lc != x || t[x].rc) return;
t[y].lc = t[x].Fa = 0, upd(y);
}
}
点分治：
int get(int u,int fth){
sz[u]=1;mx[u]=0;
for(int v:ver[u]){
if(ban[v]||v==fth) continue;
get(v,u);
sz[u]+=sz[v];
if(sz[v]>mx[u]) mx[u]=sz[v];
}
mx[u]=max(mx[u],asz-mx[u]);
if(!art||mx[u]<mx[art]) art=u;
}
int solve(int u){
ban[u]=1;
//calc path through u
for(int v:ver[u])if(!ban[v]){
asz=sz[v];art=0;
get(v,u);solve(v);
}
}
int main(){
asz=n;art=0;
get(1,0),solve(art);
}
点分树：
- 点分树中任意两点 u,v 的 LCA 一定在原树中 u,v 的简单路径上。
namespace PDT{
int rt,fa[N];
vector<int>ver[N];
void lk(int u,int v){
ver[u].pb(v);fa[v]=u;
}
}
int get(int u,int fth){
sz[u]=1;mx[u]=0;
for(int v:ver[u]){
if(ban[v]||v==fth) continue;
get(v,u);
sz[u]+=sz[v];
if(sz[v]>mx[u]) mx[u]=sz[v];
}
mx[u]=max(mx[u],asz-mx[u]);
if(!art||mx[u]<mx[art]) art=u;
}
int solve(int u){
ban[u]=1;
for(int v:ver[u])if(!ban[v]){
asz=sz[v];art=0;
get(v,u);PDT::lk(u,art);
solve(v);
}
}
void build(){
asz=n;art=0;
get(1,0);PDT::rt=art;
solve(art);
}
虚树
bool cmp(int x,int y){
return dfn[x]<dfn[y];
}
int rt;
void build(){
sort(h+1,h+1+m,cmp);//所有关键点
int len=m;
F(i,1,m) a[i]=h[i];
F(i,1,m-1) a[++len]=lca(h[i],h[i+1]);
sort(a+1,a+1+len,cmp);//所有虚树上的点
len=unique(a+1,a+1+len)-a-1;
rt=a[1];
F(i,1,len-1) lk(lca(a[i],a[i+1]),a[i+1]);
}
DSU on tree
- dfs 轻儿子的子树，计算它们的答案，要回退影响。
- dfs 重儿子的子树，计算它的答案，不回退。
- 加入所有轻儿子子树和 u 自身的影响，计算 u 的答案。
- 可能要回退 u 子树内所有点的影响。
每个点被遍历到的次数为到根路径上轻边数+1。$O(n\log n)$。
void dfs(int u, int fu) {
dfsClock ++;
dfn[u] = dfsClock, idx[dfsClock] = u;
sze[u] = 1;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (v == fu) continue;
dfs(v, u);
sze[u] += sze[v];
if (sze[v] > sze[son[u]]) son[u] = v;
}
}
void solve(int u, int fu, bool rem) {
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (v == fu || v == son[u]) continue;
solve(v, u, 0);
}
if (son[u]) solve(son[u], u, 1);
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (v == fu || v == son[u]) continue;
int nl = dfn[v], nr = dfn[v] + sze[v] - 1;
for (int ni = nl; ni <= nr; ni ++) {
int x = idx[ni];
add(x);
}
}
add(u);
// ans[u] = ...
if (!rem) {
int nl = dfn[u], nr = dfn[u] + sze[u] - 1;
for (int ni = nl; ni <= nr; ni ++) {
int x = idx[ni];
dec(x);
}
}
}
C - 图论
kruskal 重构树
void build() {
std::sort(e + 1, e + 1 + m);
nClock = n;//最初就有 n 个点
for (int i = 1; i <= n; i ++) fa[i] = i;
for (int i = 1; i <= m; i ++) {
int u = e[i].u, v = e[i].v, w = e[i].w;
int p = get(u), q = get(v);
if (p == q) continue;
int x = ++ nClock;
t[x].val = w, t[x].lc = p, t[x].rc = q;
fa[p] = fa[q] = fa[x] = x;//fa[x]=x
}
}
- 大根堆，二叉树
- 两点间 LCA 权值即为原图中 x->y 路径上最大边权的最小值。
SPFA
$O(nm)$。
$vis_u$ 表示 u 是否在队列中。
void SPFA() {
for (int i = 1; i <= n; i ++) dist[i] = inf;
for (int i = 1; i <= n; i ++) vis[i] = 0;
std::queue<int> q;
q.push(1), dist[1] = 0;
while (q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i], w = edge[i];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
判断负环：
- $cnt_x$ 为起点到 x 最短路经过的边数。
- $cnt_x\geq n$。
圆方树
const int SZ=N*2;
vector<int>ver[N],out[SZ];
int v_dcc;
void tarjan(int u){
dfn[u]=low[u]=++dfc;
stk[++tp]=u;
for(int v:ver[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){
v_dcc++;int p=n+v_dcc,x;
do{
x=stk[tp--];
out[p].pb(x);out[x].pb(p);
}while(x!=v);
out[p].pb(u);out[u].pb(p);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main(){
F(i,1,n)if(!dfn[i])
tp=0,tarjan(i);//栈清空
}
二分图
判定：
无奇环。染色。若无冲突即可。
bool dfs(int u, int color) {//color:1 or 2
col[u] = color;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (col[u] == col[v])
return 0;
else if (!col[v] && !dfs(v, 3 - color))
return 0;
}
return 1;
}
二分图最大匹配
匈牙利算法：
$O(nm)$。
bool dfs(int u) {
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (vis[v]) continue;
vis[v] = 1;
if (!match[v] || dfs(match[v])) {//若右部有未匹配的 y
match[v] = u;//或者 y 匹配的 x' 能另找到一个能与它匹配的 y'
return 1;//就把 y 配给 x
}
}
return 0;
}
int main() {
int ans = 0;
for (int i = 1; i <= nl; i ++) {//遍历每个左部点
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans ++;
}
}
字典序最小匹配：
- 左部点不断挤掉右部点匹配的左部点的过程。
- 左部点由大到小排，左部点的出边由小到大排。
最大流算法：
- 只能判定可行性：
mf=nl即可。 - $O(m\sqrt n )$。
二分图最大带权匹配：最大费用最大流。
二分图最大多重匹配：
连边：
- $(src,l_i,kl_i)$
- $(l_i,r_j,1)$
- $(r_j,des,kr_j)$
跑最大流。
网络流
最大流：$O(n^2m)$。
int et=1;
void add(int u,int v,int f){
nxt[++et]=head[u];head[u]=et;
ver[et]=v;cap[et]=f;
}
void lk(int u,int v,int f){
add(u,v,f);add(v,u,0);
}
bool BFS(){
F(i,1,nc) cur[i]=head[i],dis[i]=INF,lev[i]=-1;
while(!q.empty()) q.pop();//注意清空队列
dis[src]=lev[src]=0;
q.push(src);
while(!q.empty()){
int u=q.front();q.pop();
for(int e=head[u],v;e;e=nxt[e]){
v=ver[e];
if(cap[e]>0&&lev[v]==-1){//>0
lev[v]=lev[u]+1;
q.push(v);
if(v==des) return 1;
}
}
}
return lev[des]!=-1;
}
int dinic(int u,int flow){
if(u==des) return flow;
int res=0,ad;
for(int &e=cur[u];e;e=nxt[e]){
int v=ver[e];
if(cap[e]>0&&lev[v]==lev[u]+1){
ad=dinic(v,min(flow-res,cap[e]));
if(ad){
res+=ad;cap[e]-=ad;cap[e^1]+=ad;
if(flow==res) break;
}
}
}
if(res!=flow) lev[u]=-1;
return res;
}
void mxf(){
while(BFS()) mf+=dinic(src,INF);
}
费用流：
int et=1;
void add(int u,int v,int f,int c){
nxt[++et]=head[u];head[u]=et;
ver[et]=v;cap[et]=f;len[et]=c;
}
void lk(int u,int v,int f,int c){
add(u,v,f,c);add(v,u,0,-c);
}
bool SPFA(){
F(i,1,nc) cur[i]=head[i],dis[i]=INF,vis[i]=in[i]=0;
dis[src]=0;q.push(src);in[src]=1;
while(!q.empty()){
int u=q.front();q.pop();in[u]=0;
for(int e=head[u];e;e=nxt[e]){
int v=ver[e];
if(cap[e]>0&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
if(!in[v]) q.push(v),in[v]=1;
}
}
}
return dis[des]<INF;
}
int dinic(int u,int flow){
if(u==des) return mc+=dis[des]*flow,flow;
vis[u]=1;
int res=0,ad,v;
for(int &e=cur[e];e;e=nxt[e])
if(cap[e]>0&&!vis[v=ver[e]]&&dis[v]==dis[u]+len[e]){
ad=dinic(v,min(flow-res,cap[e]));
if(ad){
res+=ad;cap[e]-=ad;cap[e^1]+=ad;
if(res==flow) break;
}
}
if(res==flow) vis[u]=0;//vis=0 还可访问这个点
return res;
}
void mcmf(){
while(SPFA()) mf+=dinic(src,INF);
}