模板与重要性质（自用）
ACM 用的资料的前体。正巧要 CSP-S 了就突然发出来吧（列的多了大多数用处也不大，考 CSP-S 的学弟不必太在意）。太简单的就不写了。
字符串
AC 自动机
实质上是 trie 树 + fail 指针，建 AC 自动机时把不存在的 trie 树上的边指向了失配后到达的位置。
跳 fail 就是用后缀在匹配；fail 树可以干一些有意思的事情。
struct node{int fail,son[26];}t[maxn];
int adr;
inline int insert(char *s){
int len=strlen(s),u=0;
for(int i=0;i<len;++i){
int c=s[i]-'a';
if(!t[u].son[c])t[u].son[c]=++adr;
u=t[u].son[c];
}
return u;
}
inline void getfail(){
static int q[maxn];
int l=1,r=0;
for(int i=0;i<26;++i)
if(t[0].son[i])q[++r]=t[0].son[i];
while(l<=r){
int u=q[l++];
for(int i=0;i<26;++i){
int v=t[u].son[i];
if(v)t[v].fail=t[t[u].fail].son[i],q[++r]=v;
else t[u].son[i]=t[t[u].fail].son[i];
}
}
}
manacher
这里用特殊字符把所有回文串变成奇数长度了。其实我不喜欢这么搞，感觉不优雅，所以不怎么用 manacher。
R[i] 表示以 i 为中心的最大回文半径。
原理就是维护右端点最靠右的回文串，在回文串右边的信息可以通过回文性质在回文串左边查到，加朴素暴力，复杂度线性。
char t[maxn],s[maxn<<1];
int n,R[maxn<<1];
cin>>t,n=strlen(t);
for(reg i=0;i<n;++i)s[i<<1|1]='#',s[i+1<<1]=t[i];
s[0]='^',s[n=n<<1|1]='#';
for(reg i=1,j=0,r=0;i<=n;++i){
R[i]=r>i?min(R[(j<<1)-i],r-i):1;
while(i-R[i]>=0&&s[i-R[i]]==s[i+R[i]])R[i]++;
if(i+R[i]>r)j=i,r=i+R[i];
}
回文自动机（回文树）
一边是奇数长度的回文串，一边是偶数长度的。
这个代码里 1 号是奇数长度，0 号是偶数长度。
节点在 fail 树上的深度对应这个以位置结尾的回文子串数量。
struct Palindrome_Automaton{
struct{int len,son[26],fail,dep;}t[maxn];
int tot,lst;
Palindrome_Automaton(){t[t[0].fail=tot=1].len=-1;}
inline int getfail(int p,int i){
while(s[i-t[p].len-1]!=s[i])p=t[p].fail;
return p;
}
inline int extend(int i){
int q=getfail(lst,i),c=s[i];
if(!t[q].son[c]){
t[++tot].fail=t[getfail(t[q].fail,i)].son[c];
t[t[q].son[c]=tot].len=t[q].len+2,t[tot].dep=t[t[tot].fail].dep+1;
}
return lst=t[q].son[c];
}
}T;
后缀数组（SA）
sa[i]：排名为 i 的后缀；
rk[i]：后缀 i 的排名；
height[i]（此代码里的 h[0][i]）：lcp(sa[i],sa[i-1])，lcp 为最长公共前缀；
（求 height 用的引理）height[rk[i]]>=height[rk[i-1]]-1；
（用 height 求两个后缀的 lcp）lcp(sa[i],sa[j])=min{height[i+1,i+2,···,j]}，用 ST 表可以 O(nlogn) - O(1)求解；
（关于本质不同子串）sa数组上，除去 height 之外就是新增的子串，总的不同子串数目为\(\frac{n(n+1)}{2}-\sum_{i=2}^{n}{height[i]}\)；
由(1,n)开始，在 min height 处分裂区间来建笛卡尔树，每个结点代表区间都有公共前缀，先根遍历可得所有子串的字典序顺序 link
int sa[maxn],erk[maxn],id[maxn],cnt[maxn];
struct SA{
int rk[maxn],h[16][maxn];
inline void init(){
int m=127;memset(cnt+1,0,m*sizeof(int));
memset(rk,0,sizeof(rk)),memset(erk,0,sizeof(erk));
for(int i=1;i<=n;++i)++cnt[rk[i]=s[i]];
for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
for(int i=n;i;--i)sa[cnt[rk[i]]--]=i;
auto cmp=[](const int x,const int y,const int w){
return erk[x]==erk[y]&&erk[x+w]==erk[y+w];
};
for(int w=1,p,i;p!=n;w<<=1,m=p){
for(p=0,i=n-w+1;i<=n;++i)id[++p]=i;
for(i=1;i<=n;++i)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt+1,0,m*sizeof(int));
for(i=1;i<=n;++i)++cnt[rk[i]];
for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];
for(i=n;i;--i)sa[cnt[rk[id[i]]]--]=id[i];
memcpy(erk+1,rk+1,n*sizeof(int));
for(p=0,i=1;i<=n;++i)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(int i=1,k=0;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
h[0][rk[i]]=k;
}
for(int i=1;(1<<i)<=n;++i)
for(int j=1;j+(1<<i)-1<=n;++j)
h[i][j]=min(h[i-1][j],h[i-1][j+(1<<i-1)]);
}
inline int query(int i,int j){
if(i==j)return n-i+1;
i=rk[i],j=rk[j];
if(i>j)swap(i,j);
int t=__lg(j-(++i)+1);
return min(h[t][i],h[t][j-(1<<t)+1]);
}
};
SAM
SAM 是 DAG；任意从初始状态到一个状态的路径是原字符串的一个子串；SAM 上界最多 2n-1 个结点，3n-4 条转移边；
一个状态是一个 endpos 的等价类；一个状态对应的子串，都是状态中最长的子串的连续后缀，长度刚好取遍闭区间 \([minlen,len]\)；
不同的状态（节点）对应的 endpos 集合要么包含，要么不相交；
后缀链接 link 是此状态对应串的最长后缀匹配，link 边也代表了 endpos 集合的包含关系，link 树即是 endpos 包含关系对应的树；
link 树垂直上关于状态的 len 是单调的，所以把状态（节点）关于 len 计数排序就可以小常数 O(n) 完成类似自下而上树 dp 的操作。
struct node{int len,link,cnt,son[26];}t[maxn<<1];
int lst=1,adr=1;
inline void extend(int c){
int p=lst,cur=lst=++adr;
t[cur].len=t[p].len+(t[cur].cnt=1);
while(!t[p].son[c])t[p].son[c]=cur,p=t[p].link;
if(!p)t[cur].link=1;
else{
int q=t[p].son[c];
if(t[p].len+1==t[q].len)t[cur].link=q;
else{
int clone=++adr;t[clone]=t[q];
t[clone].len=t[p].len+1,t[clone].cnt=0;
t[q].link=t[cur].link=clone;
while(t[p].son[c]==q)t[p].son[c]=clone,p=t[p].link;
}
}
}
广义 SAM
广义 SAM 有很多故事，比如辰星凌的博客就从 19 年到 23 年还在修 bug...只能说下面这个大概是对的。
struct General_SAM{
struct{int len,link,son[26];}t[maxn];
int tot=1;
inline int extend(int lst,int c){
if(t[lst].son[c]){
int p=lst,q=t[p].son[c];
if(t[p].len+1==t[q].len)return q;
int clone=++tot;
memcpy(t[clone].son,t[q].son,sizeof(t[q].son));
t[clone].link=t[q].link,t[clone].len=t[p].len+1;
t[q].link=clone;
while(t[p].son[c]==q)t[p].son[c]=clone,p=t[p].link;
return clone;
}
int p=lst,cur=++tot;
t[cur].len=t[p].len+1;
while(!t[p].son[c])t[p].son[c]=cur,p=t[p].link;
if(!p)t[cur].link=1;
else{
int q=t[p].son[c];
if(t[q].len==t[p].len+1)t[cur].link=q;
else{
int clone=++tot;
memcpy(t[clone].son,t[q].son,sizeof(t[q].son));
t[clone].link=t[q].link,t[clone].len=t[p].len+1;
t[cur].link=t[q].link=clone;
while(t[p].son[c]==q)t[p].son[c]=clone,p=t[p].link;
}
}
return cur;
}
}SAM;
cin>>n;
for(reg i=1;i<=n;++i){
cin>>s;int len=strlen(s),lst=1;
for(reg j=0;j<len;++j)lst=SAM.extend(lst,s[j]-'a');
}
Z 函数（exkmp）
数据结构
扩展域并查集
判二分图用的，每个点 u 拆成两个点u,u`代表分到两个集合，如果 u,u` 分一块了就不是二分图。
李超线段树
维护一些线段，查询与 x=k 相交的交点的纵坐标最大的线段/纵坐标。
struct line{
int id;double k,b;
double operator ()(const int &x)const{return k*x+b;}
}t[mod+5<<2];
#define lt (k<<1)
#define rt (k<<1|1)
#define mid (l+r>>1)
void insert(int k,int l,int r,line x){
if(x(mid)>t[k](mid))swap(x,t[k]);
if(l==r)return;
x.k>t[k].k?insert(rt,mid+1,r,x):insert(lt,l,mid,x);
}
void modify(int k,int l,int r,int L,int R,line x){
if(L<=l&&r<=R)return insert(k,l,r,x);
if(L<=mid)modify(lt,l,mid,L,R,x);
if(R>mid)modify(rt,mid+1,r,L,R,x);
}
void query(int k,int l,int r,int x,int &ans,double v){
if(t[k](x)>v)ans=t[k].id,v=t[k](x);
else if(fabs(t[k](x)-v)<1e-9)ans=t[k].id<ans?t[k].id:ans;
if(l==r)return;
x<=mid?query(lt,l,mid,x,ans,v):query(rt,mid+1,r,x,ans,v);
}
#undef lt
#undef rt
#undef mid
线段树进阶
高维的：用树套树。
历史最值/历史和：好像不会。
势能线段树：比如区间取根号向下取整，维护区间最小值都是一就不用往下递归，其他暴力。
可持久化：挺简单的，不写了；有区间操作的可以尝试标记永久化。
线段树合并：动态开点然后直接合并就行了。合并后的可以开新节点也可以不开（不开新点的不能乱修改）
inline int merge(int p,int q,int l,int r){
if(!(p&&q))return p|q;
if(l==r)t[p].val+=t[q].val;
else{
int mid=(l+r)>>1;
t[p].lt=merge(t[p].lt,t[q].lt,l,mid);
t[p].rt=merge(t[p].rt,t[q].rt,mid+1,r);
pushup(p);
}
return p;
}
扫描线：有点忘了这是啥了。总之就是求矩形面积并，然后分成一个左边加一，一个右边减一离线做？
平衡树
treap：好像只有板子题用过这个
splay：只有 LCT 用这个
fhq-treap：能文艺能可持久化还好写，就是比较慢
替罪羊树：暴力美学。比 fhq-treap 码量大一点。能直接可持久化，是假的但一般不会被卡掉。
struct FHQ_Treap{int l,r,dat,val,size;}t[maxn];
int adr,root;
inline int New(int val){t[++adr].val=val,t[adr].dat=rand(),t[adr].size=1;return adr;}
inline void update(int p){t[p].size=t[t[p].l].size+t[t[p].r].size+1;}
inline void split(int p,int val,int &x,int &y){
if(!p){x=y=0;return;}
if(t[p].val<=val)x=p,split(t[x].r,val,t[x].r,y),update(x);
else y=p,split(t[y].l,val,x,t[y].l),update(y);
}
inline int merge(int x,int y){
if(!x||!y)return x|y;
if(t[x].dat<t[y].dat)return t[x].r=merge(t[x].r,y),update(x),x;
else return t[y].l=merge(x,t[y].l),update(y),y;
}
inline void Remove(int &root,int val){
int x=0,y=0,z=0;
split(root,val,x,z),split(x,val-1,x,y);
y=merge(t[y].l,t[y].r),root=merge(merge(x,y),z);
}
inline void insert(int &root,int val){
int x=0,y=0;
split(root,val,x,y);
int z=New(val);
root=merge(merge(x,z),y);
}
inline int getval(int p,int rank){
if(rank==t[t[p].l].size+1)return t[p].val;
if(rank<=t[t[p].l].size)return getval(t[p].l,rank);
else return getval(t[p].r,rank-t[t[p].l].size-1);
}
inline int getrank(int &root,int v){
int x=0,y=0;
split(root,v-1,x,y);
int rank=t[x].size+1;
root=merge(x,y);
return rank;
}
inline int getpre(int &root,int val){
int x,y,k,pre;
split(root,val-1,x,y);
if(!x)return -INF;
k=t[x].size;
pre=getval(x,k);
root=merge(x,y);
return pre;
}
inline int getnext(int &root,int val){
int x,y,next;
split(root,val,x,y);
if(!y)return -INF;
next=getval(y,1);
root=merge(x,y);
return next;
}
int adr,root,ldr[maxn],cnt;
struct Scapegoat_Tree{
int val,cnt,siz,sz,sd,l,r;
}t[maxn];
inline int New(int val){
t[++adr].val=val,t[adr].l=t[adr].r=0;
t[adr].cnt=t[adr].siz=t[adr].sz=t[adr].sd=1;
return adr;
}
inline void pushup(int k){
t[k].sz=t[t[k].l].sz+t[t[k].r].sz+1;
t[k].siz=t[t[k].l].siz+t[t[k].r].siz+t[k].cnt;
t[k].sd=t[t[k].l].sd+t[t[k].r].sd+(t[k].cnt>0);
}
inline bool isRbu(int k){
return t[k].cnt&&(max(t[t[k].l].sz,t[t[k].r].sz)*4>=t[k].siz*3||t[k].sd*4<=t[k].sz*3);
}
inline void Rbu_Flatten(int u){
if(!u)return;
Rbu_Flatten(t[u].l);
if(t[u].cnt)ldr[cnt++]=u;
Rbu_Flatten(t[u].r);
}
inline int Rbu_Build(int l,int r){
if(l>=r)return 0;
int mid=(l+r)>>1;
t[ldr[mid]].l=Rbu_Build(l,mid);
t[ldr[mid]].r=Rbu_Build(mid+1,r);
pushup(ldr[mid]);
return ldr[mid];
}
inline void Rebuild(int &k){
if(isRbu(k))cnt=0,Rbu_Flatten(k),k=Rbu_Build(0,cnt);
}
inline void insert(int &k,int val){
if(!k){k=New(val);if(!root)root=k;}
else{
Rebuild(k);
if(t[k].val==val)t[k].cnt++;
else insert(val<t[k].val?t[k].l:t[k].r,val);
pushup(k);
}
}
inline void erase(int &k,int val){
Rebuild(k);
if(t[k].val==val)t[k].cnt--;
else erase(val<t[k].val?t[k].l:t[k].r,val);
pushup(k);
}
inline int get_rank(int val){
int k=root,rk=1;
while(k)
if(val==t[k].val)return rk+t[t[k].l].siz;
else if(val<t[k].val)k=t[k].l;
else rk+=t[t[k].l].siz+t[k].cnt,k=t[k].r;
return rk;
}
inline int kth(int rk){
int k=root;
while(k)
if(t[t[k].l].siz>=rk)k=t[k].l;
else if(t[t[k].l].siz+t[k].cnt>=rk)return t[k].val;
else rk-=t[t[k].l].siz+t[k].cnt,k=t[k].r;
return INF;
}
inline int get_pre(int val){return kth(get_rank(val)-1);}
inline int get_next(int val){return kth(get_rank(val+1));}
树套树（分块）
不至于出这毒瘤吧？
线段树套treap：平凡
分块：需要离线离散化，空间大，但是我喜欢暴力数据结构。跑的比我树套树快，码量不比树套树大。
const int maxn=5e4+3,maxm=1e5+3,maxb=225,maxv=319,INF=0x7fffffff;
struct{int opt,l,r,k;}q[maxn];
int n,m,vale[maxm],V,raw[maxm],a[maxn];
int block1,btn1,inb1[maxn],bl1[maxn],block2,btn2,inb2[maxm],bl2[maxm],b[maxb][maxv],d[maxb][maxm];
inline void add(const int x){for(reg i=inb1[x];i<=btn1;++i)++b[i][inb2[a[x]]],++d[i][a[x]];}
inline void del(const int x){for(reg i=inb1[x];i<=btn1;++i)--b[i][inb2[a[x]]],--d[i][a[x]];}
inline int get_rank(const int l,const int r,const int k){
int L=inb1[l-1]+1,R=inb1[r+1]-1,ans=1;
if(L>R)for(reg i=l;i<=r;++i)a[i]<k&&++ans;
else{
for(reg i=l;i<bl1[L];++i)a[i]<k&&++ans;
for(reg i=bl1[R+1];i<=r;++i)a[i]<k&&++ans;
int p=inb2[k];
for(reg i=1;i<p;++i)ans+=b[R][i]-b[L-1][i];
for(reg i=bl2[inb2[k]];i<k;++i)ans+=d[R][i]-d[L-1][i];
}
return ans;
}
inline int kth(const int l,const int r,const int k){
int L=inb1[l-1]+1,R=inb1[r+1]-1,ans=114514;static int bin[maxm],bbi[maxv];
if(L>R){
for(reg i=l;i<=r;++i)++bin[a[i]],++bbi[inb2[a[i]]];
for(reg i=1,ret=0;i<=btn2;++i)
if((ret+=bbi[i])>=k){
ret-=bbi[i];
for(reg j=bl2[i];j<bl2[i+1];++j)
if((ret+=bin[j])>=k){ans=j;break;}
break;
}
for(reg i=l;i<=r;++i)bin[a[i]]=0,bbi[inb2[a[i]]]=0;
}
else{
for(reg i=l;i<bl1[L];++i)++bin[a[i]],++bbi[inb2[a[i]]];
for(reg i=bl1[R+1];i<=r;++i)++bin[a[i]],++bbi[inb2[a[i]]];
for(reg i=1,ret=0;i<=btn2;++i)
if((ret+=bbi[i]+b[R][i]-b[L-1][i])>=k){
ret-=bbi[i]+b[R][i]-b[L-1][i];
for(reg j=bl2[i];j<bl2[i+1];++j)
if((ret+=bin[j]+d[R][j]-d[L-1][j])>=k){ans=j;break;}
break;
}
for(reg i=l;i<bl1[L];++i)bin[a[i]]=0,bbi[inb2[a[i]]]=0;
for(reg i=bl1[R+1];i<=r;++i)bin[a[i]]=0,bbi[inb2[a[i]]]=0;
}
return ans;
}
inline int get_pre(const int l,const int r,const int k){
int L=inb1[l-1]+1,R=inb1[r+1]-1,ans=-INF;static int bin[maxm],bbi[maxv];
if(L>R)for(reg i=l;i<=r;++i)a[i]<k&&a[i]>ans&&(ans=a[i]);
else{
for(reg i=l;i<bl1[L];++i)bin[a[i]]=bbi[inb2[a[i]]]=1;
for(reg i=bl1[R+1];i<=r;++i)bin[a[i]]=bbi[inb2[a[i]]]=1;
int p=inb2[k];
for(reg i=k-1;i>=bl2[p];--i)if(bin[i]||d[R][i]-d[L-1][i]){ans=i;break;}
if(ans==-INF)for(reg i=p-1;i>=1;--i)if(bbi[i]||b[R][i]-b[L-1][i]){
for(reg j=bl2[i+1]-1;j>=bl2[i];--j)if(bin[j]||d[R][j]-d[L-1][j]){ans=j;break;}
break;
}
for(reg i=l;i<bl1[L];++i)bin[a[i]]=bbi[inb2[a[i]]]=0;
for(reg i=bl1[R+1];i<=r;++i)bin[a[i]]=bbi[inb2[a[i]]]=0;
}
return ans;
}
inline int get_nex(const int l,const int r,const int k){
int L=inb1[l-1]+1,R=inb1[r+1]-1,ans=INF;static int bin[maxm],bbi[maxv];
if(L>R)for(reg i=l;i<=r;++i)a[i]>k&&a[i]<ans&&(ans=a[i]);
else{
for(reg i=l;i<bl1[L];++i)bin[a[i]]=bbi[inb2[a[i]]]=1;
for(reg i=bl1[R+1];i<=r;++i)bin[a[i]]=bbi[inb2[a[i]]]=1;
int p=inb2[k];
for(reg i=k+1;i<bl2[p+1];++i)if(bin[i]||d[R][i]-d[L-1][i]){ans=i;break;}
if(ans==INF)for(reg i=p+1;i<=btn2;++i)if(bbi[i]||b[R][i]-b[L-1][i]){
for(reg j=bl2[i];j<bl2[i+1];++j)if(bin[j]||d[R][j]-d[L-1][j]){ans=j;break;}
break;
}
for(reg i=l;i<bl1[L];++i)bin[a[i]]=bbi[inb2[a[i]]]=0;
for(reg i=bl1[R+1];i<=r;++i)bin[a[i]]=bbi[inb2[a[i]]]=0;
}
return ans;
}
inline void MyDearMoments(){
n=V=read(),m=read(),block1=sqrt(n-1)+1;
for(reg i=1;i<=n;++i)a[i]=vale[i]=read(),(inb1[i]=(i-1)/block1+1)!=inb1[i-1]?bl1[inb1[i]]=i:0;
bl1[inb1[n+1]=(btn1=inb1[n])+1]=n+1;
for(reg i=1;i<=m;++i){
q[i].opt=read(),q[i].l=read(),q[i].r=read();
q[i].opt!=3?q[i].k=read(),q[i].opt!=2?vale[++V]=q[i].k:0:vale[++V]=q[i].r;
}
sort(vale+1,vale+V+1),V=unique(vale+1,vale+V+1)-vale-1;
for(reg i=1,tmp;i<=n;++i)raw[a[i]=lower_bound(vale+1,vale+V+1,tmp=a[i])-vale]=tmp;
for(reg i=1,tmp;i<=m;++i)
if(q[i].opt^3)q[i].opt!=2?raw[q[i].k=lower_bound(vale+1,vale+V+1,tmp=q[i].k)-vale]=tmp:0;
else raw[q[i].r=lower_bound(vale+1,vale+V+1,tmp=q[i].r)-vale]=tmp;
block2=sqrt(V-1)+1;
for(reg i=1;i<=V;++i)(inb2[i]=(i-1)/block2+1)!=inb2[i-1]?bl2[inb2[i]]=i:0;
bl2[inb2[V+1]=(btn2=inb2[V])+1]=V+1;
for(reg i=1;i<=n;++i)++b[inb1[i]][inb2[a[i]]],++d[inb1[i]][a[i]];
for(reg i=1;i<=btn1;++i){
for(reg j=1;j<=btn2;++j)b[i][j]+=b[i-1][j];
for(reg j=1;j<=V;++j)d[i][j]+=d[i-1][j];
}
for(reg i=1,tmp;i<=m;++i){
switch(q[i].opt){
case 1:printf("%d\n",get_rank(q[i].l,q[i].r,q[i].k));break;
case 2:printf("%d\n",raw[kth(q[i].l,q[i].r,q[i].k)]);break;
case 3:del(q[i].l),a[q[i].l]=q[i].r,add(q[i].l);break;
case 4:printf("%d\n",(tmp=get_pre(q[i].l,q[i].r,q[i].k))==-INF?-INF:raw[tmp]);break;
case 5:printf("%d\n",(tmp=get_nex(q[i].l,q[i].r,q[i].k))==INF?INF:raw[tmp]);break;
}
}
}
int main(){return MyDearMoments(),0;}
LCT
struct LinkCutTree{
struct{int ch[2],fa,val,xr;bool rev;}t[maxn];
inline void pushup(int k){t[k].xr=t[t[k].ch[0]].xr^t[t[k].ch[1]].xr^t[k].val;}
inline bool nroot(int k){return t[t[k].fa].ch[0]==k||t[t[k].fa].ch[1]==k;}
inline void reverse(int k){swap(t[k].ch[0],t[k].ch[1]),t[k].rev^=1;}
inline void pushdown(int k){if(t[k].rev)reverse(t[k].ch[0]),reverse(t[k].ch[1]),t[k].rev=0;}
inline bool getid(int k){return t[t[k].fa].ch[1]==k;}
inline void rotate(int k){
int f=t[k].fa,g=t[f].fa;bool id=getid(k);
nroot(f)?t[t[g].ch[getid(f)]=k].fa=g:t[k].fa=g;
pushup(t[t[f].ch[id]=t[k].ch[!id]].fa=f),pushup(t[t[k].ch[!id]=f].fa=k);
}
inline void splay(int k){
static int sta[maxn];int top=1,u=sta[1]=k;
while(nroot(u))sta[++top]=u=t[u].fa;
while(top)pushdown(sta[top--]);
while(nroot(k))
if(nroot(t[k].fa))
rotate(getid(k)==getid(t[k].fa)?t[k].fa:k),rotate(k);
else rotate(k);
}
inline void access(int x){for(int y=0;x;x=t[y=x].fa)splay(x),t[x].ch[1]=y,pushup(x);}
inline void makeroot(int k){access(k),splay(k),reverse(k);}
inline int findroot(int k){for(access(k),splay(k);;k=t[k].ch[0])if(!t[k].ch[0])return splay(k),k;}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int x,int y){makeroot(x);if(findroot(y)!=x)t[x].fa=y;}
inline void cut(int x,int y){split(x,y);if(t[x].fa==y&&!t[x].ch[1])t[x].fa=t[y].ch[0]=0;}
}lct;
K-D Tree
笛卡尔树
离线算法
莫队
cdq 分治
整体二分
线段树分治
猫叔分治
图论、树
二分图
最小生成树
最短路
差分约束
2-SAT
tarjan
树的直径、中心、重心
直径合并：维护直径端点，合并时六种情况比较
树的中心：直径中点
LCA
- 倍增。时空、预处理和查询都带 log，不好用。
- 树剖，常数小，好用。
- RMQ。忘掉欧拉序吧，来看看 dfs 序：\(u=v\) 特判，不妨令 \(dfn_u<dfn_v\)，lca 即为 \([dfn_u+1,dfn_v]\) 中深度最小结点的父亲。空间带 log，O(1) 查询好用。
树链剖分（重链剖分）
inline void dfs1(int u){
siz[u]=1,son[u]=0;
for(reg i=headt[u],v;i;i=e[i].next)
if((v=e[i].to)!=fa[u]){
fa[v]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline void dfs2(int u,int t){
top[u]=t,dfn[u]=++ti;
if(!son[u])return;
dfs2(son[u],t);
for(reg i=headt[u],v;i;i=e[i].next)
if((v=e[i].to)^fa[u]&&v^son[u])dfs2(v,v);
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
长链剖分
重链剖分改改，重儿子继承轻儿子暴力合并，对于只与深度有关的信息可以快速处理。暴力上跳 \(O(\sqrt n)\)，经过的重链长度单调增。
dsu on tree（树上启发式合并）
树剖然后重儿子继承，轻儿子暴力。下为伪代码。
inline void dfs(int u,int fa){
for(轻儿子v)dfs(v),clear(清空v的信息);
if(son[u])dfs(u);
for(轻儿子v)加入轻儿子信息;
加入u，获得u的答案;
}
虚树
记得各种初始化。
while(m--){
k=read();
for(reg i=1;i<=k;++i)siz[q[i]=read()]=1,rdn[q[i]]=0;
sort(q+1,q+k+1,cmp);
head[sta[top=1]=root=q[1]]=0;
for(reg i=2;i<=k;++i){
int lc=lca(sta[top],q[i]);
if(dfn[lc]<dfn[root])root=lc;
if(lc^sta[top]){
while(dfn[sta[top-1]]>dfn[lc])insert(sta[top-1],sta[top]),top--;
if(lc^sta[top-1])head[lc]=0,insert(lc,sta[top--]),sta[++top]=lc;
else insert(lc,sta[top--]);
}
head[q[i]]=0,sta[++top]=q[i];
}
for(reg i=1;i<top;++i)insert(sta[i],sta[i+1]);
dfs(root,0),rdn[root]=INF,rdx[root]=0,siz[root]=0;
}
点分治
点分树
三元环计数
斯坦纳树
支配树
网络流
Dinic 最大流
EK 费用流
数论
exgcd
逆元
crt
excrt
BSGS
exBSGS
Lucas
exLucas
数论分块
Miller-Rabin
二次剩余
原根、离散对数
莫比乌斯反演
杜教筛
min_25 筛
洲阁筛
线性代数（矩阵）
高斯消元
线性基
行列式
LGV 引理
矩阵树定理
多项式
FFT
NTT
FWT/FMT
多项式半家桶
MTT （任意模数多项式乘法）
LGV 引理
矩阵树定理
组合数学
特殊的组合问题
错排：
可重排列：
卡特兰数：
prufer：
斯特林数：
容斥原理
二项式反演
斯特林反演
计算几何
基本操作
凸包
半平面交
旋转卡壳
其他数学
复数
高精度
拉格朗日插值
概率
贝叶斯公式：
博弈论
Nim 游戏：
闵可夫斯基和
DP
状压 DP
for（int t=s;t;t=(t-1)&s）