【施工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);
}

可并堆

随机堆太好用了

1
2
3
4
5
6
7
8
9
10
11
12
int merge(int a,int b){
	if (!a||!b) return a+b;
	if (key[a]>key[b]) swap(a,b);
	pushdown(a);
	if (rand()&1) ls[a]=merge(ls[a],b);else rs[a]=merge(rs[a],b);
	return a;
}
int del(int a){
	if (!a) return 0;
	pushdown(a);
	return merge(ls[a],rs[a]);
}

图相关数据结构

并查集

路径压缩：

1
inline int getfa(int x) {return x==fa[x]:x:fa[x]=getfa(fa[x]);}

按秩合并+撤销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int fa[maxn],rk[maxn],rkk[maxq],X[maxq],Y[maxq],len;
inline void init(){
	len=0;
	for (int i=1;i<=n;i++) fa[i]=i,rk[i]=1;
}
inline int getfa(int x) {return fa[x]==x?x:getfa(fa[x]);}
inline void merge(int x,int y){
	x=getfa(x);y=getfa(y);
	if (x==y) return;
	if (rk[x]<rk[y]) swap(x,y);
	++len;
	X[len]=x;Y[len]=y; rkk[len]=rk[x];
	rk[x]=max(rk[x],rk[y]+1); fa[y]=x;
}
inline void undo(){
	rk[X[len]]=rkk[len]; fa[Y[len]]=Y[len];
	len--;
}

树链剖分

板子题：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]){
		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;id[times]=x;
	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)路径的信息

图论

最短路

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dst[maxn],que[maxn];
int vis[maxn];
void spfa(){
	cl(dst,63);cl(vis,0);
	int hed=0,til=1;
	que[1]=1;dst[1]=0;vis[1]=1;
	while (hed!=til){
		int x=que[hed=(hed+1)%maxn];
		vis[x]=0;
		for (int j=lnk[x];j;j=nxt[j])
		 if (dst[son[j]]>dst[x]+w[j]){
		 	dst[son[j]]=dst[x]+w[j];
		 	if (!vis[son[j]])
		 	 vis[que[til=(til+1)%maxn]=son[j]]=1;
		 }
	}
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll dst[maxn]; bool vis[maxn];
struct data{
	ll d;int id;
	data () {}
	data (int _id,ll _d):id(_id),d(_d) {}
	bool operator<(const data&b)const {return d>b.d;}
};
priority_queue<data> H;
void DIJ(){
	cl(dst,63);
	dst[1]=0;H.push(data(1,0));
	while (!H.empty()){
		data k=H.top();H.pop(); if (vis[k.id]) continue;
		vis[k.id]=1;if (k.id==n) return;
		for (int j=lnk[k.id];j;j=nxt[j])
		 if (!vis[son[j]]&&dst[son[j]]>dst[k.id]+w[j])
		  dst[son[j]]=dst[k.id]+w[j],H.push(data(son[j],dst[son[j]]));
	}
}

网络流

最大流

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
37
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;
		if (flow==0) break;  //!!!!!!!
	 }
	return res;
}
//.....
tot=1; add();
ans=0;
while (bfs()){
	memcpy(pos,lnk,sizeof(lnk));
	ans+=dfs(S,INF);
}

最小费用最大流

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
int tot,son[maxe],nxt[maxe],lnk[maxn],flw[maxe],cap[maxe],w[maxe];
inline void add(int x,int y,int f,int z){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;flw[tot]=0;cap[tot]=f;w[tot]=z;
	son[++tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;flw[tot]=0;cap[tot]=0;w[tot]=-z;
}
int que[maxn],dst[maxn],ed[maxn];
bool vis[maxn];
bool spfa(){
	cl(vis,0);cl(dst,63);
	int hed=0,til=1;que[1]=S;dst[S]=0;fa[S]=0;
	while (hed!=til){
		int x=que[hed=(hed+1)%maxn];
		vis[x]=0;
		for (int j=lnk[x];j;j=nxt[j])
		 if (flw[j]<cap[j]&&dst[son[j]]>dst[x]+w[j]){
		 	dst[son[j]]=dst[x]+w[j];
		 	fa[son[j]]=x; ed[son[j]]=j;
		 	if (!vis[son[j]]) vis[que[til=(til+1)%maxn]=son[j]]=1;
		 }
	}
	return dst[T]!=INF;
}
//......
tot=1;  //!!!
//addedge......
int ans=0;
while (spfa()&&dst[T]>0){
	int Min=INF;
	for (int x=T;x!=S;x=fa[x]) Min=min(Min,cap[ed[x]]-flw[ed[x]]);
	for (int x=T;x!=S;x=fa[x]) flw[ed[x]]+=Min,flw[ed[x]^1]-=Min;
	ans+=Min*dst[T];
}

二分图

二分图最大匹配

Hungary算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int times,vis[maxn],con[maxn];
bool find(int x){
	if (vis[x]==times) return 0;
	vis[x]=times;
	for (int j=lnk[x];j;j=nxt[j]){
		int k=con[son[j]];con[son[j]]=x;
		if (!k||find(k)) return 1;
		con[son[j]]=k;
	}
	return 0;
}
//....
int ans=0;
for (int i=1;i<=N;i++)
 times++,ans+=find(i);

强连通分量

HDU1269

Tarjan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfn[maxn],low[maxn],stk[maxn],SCC[maxn],times;
bool instk[maxn];
void Tarjan(int x){
	dfn[x]=low[x]=++times;instk[stk[++stk[0]]=x]=1;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!dfn[son[j]])
	  Tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
	 else if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
	if (dfn[x]==low[x]){
		SCC[0]++;
		while (stk[stk[0]]!=x) instk[stk[stk[0]]]=0,SCC[stk[stk[0]--]]=SCC[0];
		instk[stk[stk[0]]]=0,SCC[stk[stk[0]--]]=SCC[0];
	}
}

双联通分量

直接看这个

差分约束系统

直接看这个

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);
}

字符串相关

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nxt[1]=0;
for (int i=2,j=0;i<=n;i++){
    while (j>0&&B[j+1]!=B[i]) j=nxt[j];
    if (B[j+1]==B[i]) j++;
    nxt[i]=j;
}
for (int i=1,j=0;i<=n;i++){
    while (j>0&&B[j+1]!=A[i]) j=nxt[j];
    if (B[j+1]==A[i]) j++;
    if (j==m){
        //do something……
        j=nxt[j];
    }
}

后缀数组

板子题：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;
}

其他

莫队算法

BZOJ2038

莫队一定要先移R指针！不然有可能会出现L>R，询问函数写得不好就炸了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void blocker(){
	int k=sqrt(n);
	for (int i=1;i<=n;i++) h[i]=(i-1)/k+1;
}
struct data{
	int l,r,id;
	bool operator<(const data&b)const{
		if (h[l]==h[b.l]) return r<b.r;
		return l<b.l;
	}
}a[maxn];
//......
blocker();
sort(a+1,a+1+q);
int L=1,R=0;
for (int i=1;i<=q;i++){
	while (R<a[i].r) insert(++R);
	while (R>a[i].r) del(R--);
	while (L>a[i].l) insert(--L)
	while (L<a[i].l) del(L++);
	ans[a[i].id]=now;
}

linkfqyA link to the past.

咸鱼一条