模板库(持续更新)

整理一下我学过的部分算法模板。

AC自动机

HDU2222

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int trie[maxn][26];//trie树 每个节点对应一个数字
int cntword[maxn];//统计每个节点为单词终点的个数
int fail[maxn];//fail指针
char s[maxn];
int cnt;
void init(){
memset(trie,0,sizeof(trie));
memset(cntword,0,sizeof(cntword));
memset(fail,0,sizeof(fail));
cnt=0;
}
void insert(char* s){
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++){
if(!trie[root][s[i]-'a']) trie[root][s[i]-'a']=++cnt;
root=trie[root][s[i]-'a'];
}
cntword[root]++;
}
void getfail(){
queue<int>que;
for(int i=0;i<26;i++){
if(trie[0][i]) que.push(trie[0][i]);
}
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=0;i<26;i++){
if(trie[now][i]){
fail[trie[now][i]]=trie[fail[now]][i];
que.push(trie[now][i]);
}
else{
trie[now][i]=trie[fail[now]][i];
}
}
}
}
int query(char *s){
int len=strlen(s);
int res=0,now=0;
for(int i=0;i<len;i++){
now=trie[now][s[i]-'a'];
for(int j=now;j && cntword[j]!=-1;j=fail[j]){
res+=cntword[j];
cntword[j]=-1;
}
}
return res;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",s);
insert(s);
}
cnt=0;
getfail();
scanf("%s",s);
printf("%d\n",query(s));
}
return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
void init(){
for(int i=1;i<=n;i++) pre[i]=i;
}
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(x<y) pre[y]=x;
else pre[x]=y;
}

FFT

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
void init(int lim,int bit_len){
memset(r,0,sizeof(r));
for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(bit_len-1));
}
void fft(cpx* a,int lim,int flag){
for(int i=0;i<lim;i++){
if(i<r[i]){
swap(a[i],a[r[i]]);
}
}
for(int i=1;i<lim;i<<=1){
cpx part{cos(pi/i),flag*sin(pi/i)};
int R=i<<1;
for(int j=0;j<lim;j+=R){
cpx w{1,0};
for(int k=0;k<i;k++,w=w*part){
cpx x=a[j+k];
cpx y=w*a[j+i+k];
a[j+k]=x+y;
a[j+i+k]=x-y;
}
}
}
if(flag==-1){
for(int i=0;i<lim;i++) a[i].x/=lim;
}
}

GCD

1
2
3
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}

康托展开

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
void cantor(){
ll sum=1,fac=1;
for(int i=n-1;i>0;i--){
fac*=(n-i);
for(int j=i+1;j<=n;j++){
if(a[i]>a[j]) sum+=fac;
}
}
printf("%lld\n",sum);
}
void inverse_cantor(){
ll fac=1,num;
k--;
memset(vis,0,sizeof(vis));
for(int i=1;i<n;i++) fac*=i;
for(int i=1;i<=n;i++){
num=k/fac;
k%=fac;
if(n-i) fac/=(n-i);
for(int j=1;j<=n;j++){
if(num==0 && !vis[j]){
printf("%d ",j);
vis[j]=1;
break;
}
if(!vis[j]) num--;
}
}
printf("\n");
}

KM

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int love[maxn][maxn];
int exgirl[maxn],exboy[maxn];
bool visgirl[maxn],visboy[maxn];
int match[maxn],slack[maxn];
int n,m;
bool dfs(int x){
visgirl[x]=true;
for(int i=0;i<n;i++){
if(!visboy[i]){
int gap=exgirl[x]+exboy[i]-love[x][i];
if(gap==0){
visboy[i]=true;
if(match[i]==-1 || dfs(match[i])){
match[i]=x;
return true;
}
}
else{
slack[i]=min(slack[i],gap);
}
}
}
return false;
}
int km(){
memset(match,-1,sizeof(match));
memset(exboy,0,sizeof(exboy));
for(int i=0;i<n;i++){
exgirl[i]=love[i][0];
for(int j=1;j<n;j++){
exgirl[i]=max(exgirl[i],love[i][j]);
}
}
for(int i=0;i<n;i++){
fill(slack,slack+n,INF);
while(true){
memset(visgirl,false,sizeof(visgirl));
memset(visboy,false,sizeof(visboy));
if(dfs(i)) break;

int d=INF;
for(int i=0;i<n;i++){
if(!visboy[i]) d=min(d,slack[i]);
}
for(int i=0;i<n;i++){
if(visgirl[i]) exgirl[i]-=d;
if(visboy[i]) exboy[i]+=d;
else slack[i]-=d;
}
}
}
int res=0;
for(int i=0;i<n;i++){
res+=love[match[i]][i];
}
return res;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_nxt(){
int i=1,next[1]=0,j=0;
int len=strlen(str);
while(i<len){
if(j==0 || str[i]==str[j]){
i++;
j++;
next[i]=j;
}
else
j=next[i];
}
}

Tarjan

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
38
int n,m,tt,cnt,sig;
int vis[maxn],low[maxn],dfn[maxn];
int color[maxn],st[maxn];
vector<int>vec[maxn];
void init(){
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(color,0,sizeof(color));
memset(st,0,sizeof(st));
for(int i=1;i<=n;i++) vec[i].clear();
}
void tarjan(int x){
vis[x]=1;
dfn[x]=low[x]=cnt++;
st[++tt]=x;
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
if(vis[y]==0) tarjan(y);
if(vis[y]==1) low[x]=min(low[x],low[y]);
}
if(low[x]==dfn[x]){
sig++;
do{
color[st[tt]]=sig;
vis[st[tt]]=-1;
}while(st[tt--]!=x);
}
}
void solve(){
tt=-1;cnt=1;sig=0;
for(int i=1;i<=n;i++){
if(vis[i]==0) tarjan(i);
}
/*
此处添加其他操作
*/
}

凸包

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
struct node{
int x,y;
int pos;
}p[maxn],q[maxn];
int n,l;
node getmag(node a,node b){
node s;
s.x=b.x-a.x;
s.y=b.y-a.y;
return s;
}
int multiX(node a,node b){
return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b){
return multiX(getmag(p[1],a),getmag(p[1],b))>0;
}
void graham(){
int id=1;
for(int i=2;i<=n;i++){
if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) id=i;
}
if(id!=1) swap(p[id],p[1]);

sort(p+2,p+n+1,cmp);
q[++l]=p[1];
for(int i=2;i<=n;i++){

while(l>=2 && multiX(getmag(q[l-1],p[i]),getmag(q[l-1],q[l]))>=0) l--;
q[++l]=p[i];
}
}

网络流

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct edge{
int to,dis,nxt;
}G[maxn];
int head[maxn],d[maxn],cur[maxn];
void add(int from,int to,int dis){
G[cnt].to=to;
G[cnt].dis=dis;
G[cnt].nxt=head[from];
head[from]=cnt++;
}
int dfs(int u,int flow){
if(u==t) return flow;
int x=0;
for(int& i=cur[u];i!=-1;i=G[i].nxt){
// cur[u]=G[i].nxt;
int v=G[i].to;
if(d[v]==d[u]+1 && G[i].dis>0){
int res = dfs(v,min(flow,G[i].dis));
flow -= res;
x += res;
G[i].dis -= res;
G[i^1].dis += res;
if(flow == 0) break;
}
}
if(!x) d[u]=-1;
return x;
}
void bfs(){
memset(d,-1,sizeof(d));
queue<int>que;
que.push(s);
d[s]=0;
while(!que.empty()){
int u=que.front();que.pop();
for(int i=head[u];i!=-1;i=G[i].nxt){
int v=G[i].to;
if(d[v]==-1 && G[i].dis>0){
d[v]=d[u]+1;
que.push(v);
}
}
}
}
void dinic(){
ll max_flow=0;
while(true){
bfs();
if(d[t]==-1) break;
for(int i=1;i<=n;i++) cur[i]=head[i];
max_flow+=dfs(s,INF);
}
printf("%lld\n",max_flow);
}

线段树

线段树单点更新+查询区间最大值

HDU1754

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000;
int dat[maxn],n;
int m,a,b;
char op;
void init(int x){
n=1;
while(n<x) n*=2;
for(int i=0;i<n*2-1;i++){
dat[i]=0;
}
}
void update(int k,int a){
k+=n-1;
dat[k]=a;
while(k>0){
k=(k-1)/2;
dat[k]=max(dat[k*2+1],dat[k*2+2]);
}
}
int query(int a,int b,int k,int l,int r){
if(r<a || b<l) return 0;
if(a<=l && r<=b) return dat[k];
else{
int vl=query(a,b,k*2+1,l,(l+r)/2);
int vr=query(a,b,k*2+2,(l+r)/2+1,r);
return max(vl,vr);
}
}
int main()
{
int n_;
while(~scanf("%d %d",&n,&m)){
n_=n;
init(n);
for(int i=0;i<n_;i++){
scanf("%d",&dat[i+n-1]);
update(i,dat[i+n-1]);
}
getchar();
while(m--){
scanf("%c %d %d",&op,&a,&b);
getchar();
if(op=='Q') printf("%d\n",query(a-1,b-1,0,0,n-1));
else if(op=='U') update(a-1,b);
}
}

return 0;
}

线段树区间更新

FZU1608

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
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000;
int n,m,dat[maxn];
void init(int x){
n=1;
while(n<x) n*=2;
for(int i=0;i<n*2-1;i++){
dat[i]=0;
}
}
void update(int a,int b,int x,int k,int l,int r){
if(b<l || r<a) return ;
if(a<=l && r<=b) dat[k]=max(x,dat[k]);
else{
update(a,b,x,k*2+1,l,(l+r)/2);
update(a,b,x,k*2+2,(l+r)/2+1,r);
}
}
int query(int l,int r,int k,int mmax){
if(l==r) return max(mmax,dat[k]);
dat[k]=max(mmax,dat[k]);
int vl=query(l,(l+r)/2,k*2+1,dat[k]);
int vr=query((l+r)/2+1,r,k*2+2,dat[k]);
return vl+vr;
}
int main()
{
int a,b,x;
while(~scanf("%d %d",&n,&m)){
init(n);
for(int i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&x);
update(a,b-1,x,0,0,n-1);
}
printf("%d\n",query(0,n-1,0,0));
}
return 0;
}

线段树区间更新+区间求和

POJ3468

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
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
const ll maxn=1000000;
ll dat[maxn],sum[maxn],n,m;
void update(ll a,ll b,ll x,ll k,ll l,ll r){
if(a<=l && r<=b){
dat[k]+=x;
}
else if(l<=b && a<=r){
sum[k]+=(min(b,r)-max(a,l)+1)*x;
update(a,b,x,k*2+1,l,(l+r)/2);
update(a,b,x,k*2+2,(l+r)/2+1,r);
}
}
ll query(ll a,ll b,ll k,ll l,ll r){
if(b<l || r<a) return 0;
else if(a<=l && r<=b) return dat[k]*(r-l+1)+sum[k];
else{
ll res=(min(b,r)-max(a,l)+1)*dat[k];
res+=query(a,b,k*2+1,l,(l+r)/2);
res+=query(a,b,k*2+2,(l+r)/2+1,r);
return res;
}
}
int main()
{
ll a,b,x;
char op;
scanf("%lld %lld",&n,&m);
for(int i=0;i<n;i++){
scanf("%lld",&x);
update(i,i,x,0,0,n-1);
}
getchar();
while(m--){
scanf("%c",&op);
if(op=='Q'){
scanf("%lld %lld",&a,&b);
printf("%lld\n",query(a-1,b-1,0,0,n-1));
}
else{
scanf("%lld %lld %lld",&a,&b,&x);
update(a-1,b-1,x,0,0,n-1);
}
getchar();
}
return 0;
}

线性基求交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LinearBase(int v1,int v2,int res){
int a[35],b[35];
for(int i=0;i<32;i++) a[i]=b[i]=tree[v1][i];
for(int i=0;i<32;i++){
int q=tree[v2][i],t=0;
if(!q) continue;
int j=i;
for(;j>=0;j--){
if(q>>j){
if(!a[j]) break;
q^=a[j];
t^=b[j];
}
}
if(!q) tree[res][i]=t;
else a[j]=q,b[j]=t;
}
}

主席树

静态主席树

//查询区间第k小

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# include<bits/stdc++.h>

using namespace std;
const int maxn=1000000+10;
int rt[maxn],ls[maxn*2],rs[maxn*2],sum[maxn*2];
int a[maxn],b[maxn];
int tot,N,n,q;
void build(int& o,int l,int r){
o=++tot;
sum[o]=0;
if(l==r) return ;
int m=(l+r)/2;
build(ls[o],l,m);
build(rs[o],m+1,r);
}
void update(int& o,int l,int r,int last,int k){
o=++tot;
ls[o]=ls[last];
rs[o]=rs[last];
sum[o]=sum[last]+1;
if(l==r) return ;
int m=(l+r)/2;
if(k<=m) update(ls[o],l,m,ls[last],k);
else update(rs[o],m+1,r,rs[last],k);
}
int query(int s,int e,int l,int r,int k){
if(l==r) return l;
int cnt=sum[ls[e]]-sum[ls[s]];
int m=(l+r)/2;
if(k<=cnt) return query(ls[s],ls[e],l,m,k);
else return query(rs[s],rs[e],m+1,r,k-cnt);
}
int main()
{
int t;
int l,r,k;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
tot=0;
sort(b+1,b+n+1);
N=unique(b+1,b+n+1)-(b+1);
build(rt[0],1,N);
for(int i=1;i<=n;i++) update(rt[i],1,N,rt[i-1],lower_bound(b+1,b+N+1,a[i])-b);
while(q--){
scanf("%d %d %d",&l,&r,&k);
int ans=query(rt[l-1],rt[r],1,N,k);
printf("%d\n",b[ans]);
}
}
return 0;
}

动态主席树

//修改单点+查询区间

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# include<bits/stdc++.h>

using namespace std;
const int maxn=60000+10;
int a[maxn],hash[maxn];
int rt[maxn],RT[maxn],ls[maxn*32],rs[maxn*32],sum[maxn*32];
int ul[maxn],ur[maxn];
int tot,n,q,N;
struct node{
int l,r,k;
bool flag;
}op[maxn];
int lowbit(int x){
return x&(-x);
}
void build(int& o,int l,int r){
o=++tot;
sum[o]=0;
if(l==r) return;
int m=(l+r)/2;
build(ls[o],l,m);
build(rs[o],m+1,r);
}
void update(int& o,int l,int r,int last,int p,int val){
o=++tot;
ls[o]=ls[last];
rs[o]=rs[last];
sum[o]=sum[last]+val;
if(l==r) return ;
int m=(l+r)/2;
if(p<=m) update(ls[o],l,m,ls[last],p,val);
else update(rs[o],m+1,r,rs[last],p,val);
}
void add(int x,int val){
int res=lower_bound(hash+1,hash+N+1,a[x])-hash;
while(x<=n){
update(RT[x],1,N,RT[x],res,val);
x+=lowbit(x);
}
}

int Sum(int x,bool flag){
int res=0;
while(x){
if(flag) res+=sum[ls[ur[x]]];
else res+=sum[ls[ul[x]]];
x-=lowbit(x);
}
return res;
}

int query(int s,int e,int ts,int te,int l,int r,int k){
if(l==r) return l;
int m=(l+r)/2;
int cnt=Sum(e,true)-Sum(s,false)+sum[ls[te]]-sum[ls[ts]];
if(k<=cnt){
for(int i=e;i;i-=lowbit(i)) ur[i]=ls[ur[i]];
for(int i=s;i;i-=lowbit(i)) ul[i]=ls[ul[i]];
return query(s,e,ls[ts],ls[te],l,m,k);
}
else{
for(int i=e;i;i-=lowbit(i)) ur[i]=rs[ur[i]];
for(int i=s;i;i-=lowbit(i)) ul[i]=rs[ul[i]];
return query(s,e,rs[ts],rs[te],m+1,r,k-cnt);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
hash[i]=a[i];
}
char str[2];
N=n;
for(int i=1;i<=q;i++){
scanf("%s",str);
if(str[0]=='Q'){
scanf("%d %d %d",&op[i].l,&op[i].r,&op[i].k);
op[i].flag=true;
}
else{
scanf("%d %d",&op[i].r,&op[i].k);
op[i].flag=false;
hash[++N]=op[i].k;
}
}
sort(hash+1,hash+N+1);
N=unique(hash+1,hash+N+1)-(hash+1);
tot=0;
build(rt[0],1,N);
for(int i=1;i<=n;i++) update(rt[i],1,N,rt[i-1],lower_bound(hash+1,hash+N+1,a[i])-hash,1);
for(int i=1;i<=n;i++) RT[i]=rt[0];
for(int i=1;i<=q;i++){
int l=op[i].l,r=op[i].r,k=op[i].k;
if(op[i].flag){
for(int j=r;j;j-=lowbit(j)) ur[j]=RT[j];
for(int j=l-1;j;j-=lowbit(j)) ul[j]=RT[j];
int res=query(l-1,r,rt[l-1],rt[r],1,N,k);
printf("%d\n",hash[res]);
}
else{
add(r,-1);
a[r]=k;
add(r,1);
}
}
}
return 0;
}

__int128输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
__int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}