【施工ing】模板合集

考前背板就看这里了

数据结构

传统数据结构

线段树

线段树动态开点/线段树合并

BZOJ2733

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Rot[maxn],len,tre[maxs],ls[maxs],rs[maxs];
inline void pushup(int x) {tre[x]=tre[ls[x]]+tre[rs[x]];}
inline int newnode(int _ls,int _rs,int _s) {ls[++len]=_ls,rs[len]=_rs,tre[len]=_s;return len;}
void ist(int &x,int l,int r,int k){
if (!x) x=newnode(0,0,0);
if (l==r) {tre[x]++;return;}
int mid=l+r>>1;
if (k<=mid) ist(ls[x],l,mid,k);
else ist(rs[x],mid+1,r,k);
pushup(x);
}
int merge(int x,int y){ //此处为节省空间,直接把合并后的信息储存在x节点了,合并其他信息要小心
if (!x||!y) return x+y;
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
tre[x]=tre[x]+tre[y];
return x;
}

可持久化线段树/主席树

POJ2104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Rot[maxn],tre[maxs],s[maxs][2],len;
inline void pushup(int x) {tre[x]=tre[s[x][0]]+tre[s[x][1]];}
int build(int l,int r){
int x=++len; tre[x]=0;
if (l==r) {s[x][0]=s[x][1]=0;return x;}
int mid=l+r>>1;
s[x][0]=build(l,mid); s[x][1]=build(mid+1,r);
return x;
}
int ist(int fa,int l,int r,int k){
int x=++len; tre[x]=tre[fa];s[x][0]=s[fa][0];s[x][1]=s[fa][1];
if (l==r) return tre[x]++,x;
int mid=l+r>>1;
if (k<=mid) s[x][0]=ist(s[fa][0],l,mid,k);
else s[x][1]=ist(s[fa][1],mid+1,r,k);
return pushup(x),x;
}
int qry(int x,int y,int l,int r,int k){
if (l==r) return l;
int mid=l+r>>1,tem;
if ((tem=tre[s[y][0]]-tre[s[x][0]])>=k) return qry(s[x][0],s[y][0],l,mid,k);
else return qry(s[x][1],s[y][1],mid+1,r,k-tem);
}

图相关数据结构

树链剖分

板子题:BZOJ1036

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int H_son[maxn],siz[maxn],fa[maxn],dep[maxn],in[maxn],out[maxn],top[maxn],times;
void getH(int x){
siz[x]=1;dep[x]=dep[fa[x]]+1;H_son[x]=0;
for (int j=lnk[x];j;j=nxt[j])
if (son[j]!=fa[x]){
id[j+1>>1]=son[j];fa[son[j]]=x; getH(son[j]); siz[x]+=siz[son[j]];
if (!H_son[x]||siz[H_son[x]]<siz[son[j]]) H_son[x]=son[j];
}
}
void dfs(int x,int lst){
top[x]=lst;in[x]=++times;
if (H_son[x]) dfs(H_son[x],lst);
for (int j=lnk[x];j;j=nxt[j])
if (son[j]!=fa[x]&&son[j]!=H_son[x]) dfs(son[j],son[j]);
out[x]=times;
}
void insert(int x,int y,int w){
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ist(1,1,N,in[top[x]],in[x],w); x=fa[top[x]];
}
if (in[x]>in[y]) swap(x,y);
ist(1,1,N,in[x],in[y],w);
//ist(1,1,N,in[x]+1,in[y],w); 维护边权
}
int query(int x,int y){
int res=0;
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
res=max(res,qry(1,1,N,in[top[x]],in[x])); x=fa[top[x]];
}
if (in[x]>in[y]) swap(x,y);
return max(res,qry(1,1,N,in[x],in[y]));
//return max(res,qry(1,1,N,in[x]+1,in[y])); 维护边权
}

LCT

板子题:BZOJ2631

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int s[maxn][2],fa[maxn];
bool flp[maxn];
#define isroot(x) (s[fa[x]][0]!=x&&s[fa[x]][1]!=x)
inline void addflip(int x) {swap(s[x][0],s[x][1]);flp[x]^=1;}
inline void pushup(int x) {/* do something */}
inline void pushdown(int x) {if (flp[x]) flp[x]^=1,addflip(s[x][0]),addflip(s[x][1]);}
inline void rotate(int x){
int f=fa[x],g=fa[f],d=s[f][0]==x;
if (!isroot(f)) s[g][s[g][1]==f]=x; fa[x]=g;
s[f][d^1]=s[x][d]; fa[s[x][d]]=f; pushup(f);
s[x][d]=f; fa[f]=x; pushup(x);
}
int top,stk[maxn];
inline void splay(int x){
stk[top=1]=x;
for (int i=x;!isroot(i);i=fa[i]) stk[++top]=fa[i];
while (top) pushdown(stk[top--]);
while (!isroot(x)){
int f=fa[x],g=fa[f],d=s[f][0]==x,dd=s[g][0]==f;
if (!isroot(f))
if (d==dd) rotate(f),rotate(x);else
rotate(x),rotate(x);
else rotate(x);
}
}
inline void access(int x) {for (int t=0;x;t=x,x=fa[x]) splay(x),s[x][1]=t,pushup(x);}
inline void mr(int x) {access(x),splay(x),addflip(x);}
inline void join(int x,int y) {mr(x);fa[x]=y;}
inline void cut(int x,int y) {mr(x),access(y),splay(y);if (s[y][0]==x) fa[x]=s[y][0]=0;}
inline int getrt(int x) {access(x),splay(x);while (s[x][0]) pushdown(x),x=s[x][0];splay(x);return x;} //!!!
//...
if (getrt(x)!=getrt(y)) join(x,y); //加边
cut(x,y); //删边
mr(x);access(x); //修改x的点权
mr(x);access(y);splay(x); //获取(x,y)路径的信息

图论

网络流

最大流

BZOJ1066

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int tot,son[maxe],nxt[maxe],pos[maxn],lnk[maxn],flw[maxe],cap[maxe];
inline void add(int x,int y,int z){
son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;flw[tot]=0;cap[tot]=z;
son[++tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;flw[tot]=0;cap[tot]=0;
}

int d[maxn],que[maxn];
bool bfs(){
cl(d,63);
int hed=0,til=1;
d[S]=0;que[1]=S;
while (hed!=til){
int x=que[++hed];
for (int j=lnk[x];j;j=nxt[j])
if (d[son[j]]==INF&&flw[j]<cap[j])
que[++til]=son[j],d[son[j]]=d[x]+1;
}
return d[T]!=INF;
}
int dfs(int x,int flow){
if (x==T||flow==0) return flow;
ll res=0,f;
for (int &j=pos[x];j;j=nxt[j])
if (d[son[j]]==d[x]+1&&(f=dfs(son[j],min(flow,cap[j]-flw[j])))>0){
flw[j]+=f; flw[j^1]-=f;
res+=f; flow-=f;
}
return res;
}
//.....
tot=1; add();
ans=0;
while (bfs()){
memcpy(pos,lnk,sizeof(lnk));
ans+=dfs(S,INF);
}

双联通分量

直接看这个

差分约束系统

直接看这个

BZOJ2330

虚树

BZOJ2286

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert(int x){
if (!top) {stk[++top]=x;return;}
int lca=LCA(x,stk[top]);
while (top>1&&dfn[stk[top-1]]>dfn[lca])
add(stk[top-1],stk[top],dst(stk[top-1],stk[top])),top--;
if (dfn[stk[top]]>dfn[lca]) add(lca,stk[top],dst(lca,stk[top])),top--;
if (!top||dfn[stk[top]]<dfn[lca]) stk[++top]=lca;
stk[++top]=x;
}
//......
sort(h+1,h+1+K,cmp); tot=top=0;
for (int i=1;i<=K;i++) insert(h[i]);
while (top>1) add(stk[top-1],stk[top],dst(stk[top-1],stk[top])),top--;

dsu on tree

Codeforces 600E

1
2
3
4
5
6
7
8
9
10
11
12
void change(int x,int w){
记录x的贡献
for (int j=lnk[x];j;j=nxt[j])
if (!xH[son[j]]) change(son[j],w);
}
void dsu(int x,bool keep){
for 每个轻儿子 dsu(son,0);
dsu(H_son[x],1); xH[H_son[x]]=1;
change(x,1); xH[H_son[x]]=0;
更新x的答案
if (!keep) change(x,-1);
}

字符串相关

后缀数组

板子题:UOJ#35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n,m,buc[maxn],sa[maxn],rk[maxn*2],t[maxn],ht[maxn];
char s[maxn];
void get_sa(){
cl(buc,0);
for (int i=1;i<=n;i++) buc[rk[t[i]]]++;
for (int i=1;i<=m;i++) buc[i]+=buc[i-1];
for (int i=n;i;i--) sa[buc[rk[t[i]]]--]=t[i];
}
void make_sa(){
m=128;
for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;
get_sa();
for (int k=1,p=0;k<n&&p<n;k<<=1,m=p){
p=0;
for (int i=n-k+1;i<=n;i++) t[++p]=i;
for (int i=1;i<=n;i++) if (sa[i]>k) t[++p]=sa[i]-k;
get_sa(); t[sa[1]]=p=1;
for (int i=2;i<=n;i++)
if (rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+k]==rk[sa[i-1]+k]) t[sa[i]]=p;else t[sa[i]]=++p;
memcpy(rk,t,sizeof(t));
}
for (int i=1,h=0;i<=n;i++){
if (h) h--;
int j=sa[rk[i]-1];
while (s[i+h]==s[j+h]) h++;
ht[rk[i]]=h;
}
}

数学相关

FFT

板子题:UOJ#34

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct comp{
double r,i;
comp (double _r=0,double _i=0):r(_r),i(_i) {}
comp operator+(const comp&b) {return comp(r+b.r,i+b.i);}
comp operator-(const comp&b) {return comp(r-b.r,i-b.i);}
comp operator*(const comp&b) {return comp(r*b.r-i*b.i,r*b.i+i*b.r);}
comp operator/(const double&b) {return comp(r/b,r/b);}
}a[maxn],b[maxn],c[maxn];
int rev[maxn];
inline void get_rev(int n){
rev[0]=0; int l=log2(n);
for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);
}
void FFT(comp *a,int n,int d){
for (int i=0;i<n;i++) if (rev[i]<i) swap(a[i],a[rev[i]]);
for (int l=2;l<=n;l<<=1){
comp wl(cos(2*PI/l),d*sin(2*PI/l));
for (int k=0;k<n;k+=l){
comp w(1,0),_t,_T;
for (int j=0,tj=l>>1;j<tj;j++,w=w*wl)
_t=a[k+j],_T=w*a[k+j+tj],a[k+j]=_t+_T,a[k+j+tj]=_t-_T;
}
}
if (d<0) for (int i=0;i<n;i++) a[i]=a[i]/n;
}