数据结构

K-D Tree

「洛谷」P4357

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
#include <bits/stdc++.h>
using namespace std;

const int K=2;
const int maxn=1e5+5;
#define ll long long
const ll INF=1e18;
int D;

struct KDTree
{
struct Node
{
int d[K];
bool operator < (const Node &B) const
{
return d[D]<B.d[D];
}
}a[maxn];

int Root;
int d[maxn][K],son[maxn][2],x[maxn][2],y[maxn][2];
priority_queue<ll,vector<ll>,greater<ll>>Q;

#define ls son[rt][0]
#define rs son[rt][1]

void update(int u,int v)
{
x[u][0]=min(x[u][0],x[v][0]);x[u][1]=max(x[u][1],x[v][1]);
y[u][0]=min(y[u][0],y[v][0]);y[u][1]=max(y[u][1],y[v][1]);
}

int build(int l,int r,int op)
{
D=op;int rt=(l+r)>>1;
nth_element(a+l,a+rt,a+r+1);
d[rt][0]=x[rt][0]=x[rt][1]=a[rt].d[0];
d[rt][1]=y[rt][0]=y[rt][1]=a[rt].d[1];
if(l<rt) ls=build(l,rt-1,op^1),update(rt,ls);
if(r>rt) rs=build(rt+1,r,op^1),update(rt,rs);
return rt;
}

inline ll sqr(ll x){return x*x;}

inline ll h(int rt,Node p)
{
ll res=max(sqr(p.d[0]-x[rt][0]),sqr(p.d[0]-x[rt][1]));
res+=max(sqr(p.d[1]-y[rt][0]),sqr(p.d[1]-y[rt][1]));
return res;
}

void query(int rt,Node p)
{
ll dis[2];
ll res=sqr(d[rt][0]-p.d[0])+sqr(d[rt][1]-p.d[1]);
dis[0]=ls?h(ls,p):-INF;
dis[1]=rs?h(rs,p):-INF;
if(Q.top()<res) Q.pop(),Q.push(res);
int op=(dis[0]<=dis[1]);
if(Q.top()<dis[op]) query(son[rt][op],p);
if(Q.top()<dis[op^1]) query(son[rt][op^1],p);
}

ll deal(int n,int k)
{
for(int i=1;i<=n;i++) cin>>a[i].d[0]>>a[i].d[1];
Root=build(1,n,0);
for(int i=1;i<=(k<<1);i++) Q.push(0);
for(int i=1;i<=n;i++) query(Root,a[i]);
return Q.top();
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,k;
cin>>n>>k;
cout<<T.deal(n,k);
return 0;
}

LCT

「洛谷」P3690

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct LCT
{
int f[maxn],c[maxn][2],v[maxn],s[maxn];
bool r[maxn];
#define lc c[x][0]
#define rc c[x][1]

bool nroot(int x){return c[f[x]][0]==x || c[f[x]][1]==x;}
void pushup(int x){s[x]=s[lc]^s[rc]^v[x];}
void pushr(int x){swap(lc,rc);r[x]^=1;}
void pushdown(int x)
{
if(!r[x]) return;
if(lc) pushr(lc);
if(rc) pushr(rc);
r[x]=0;
}

void rotate(int x)
{
int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y)) c[z][c[z][1]==y]=x;
c[x][!k]=y;c[y][k]=w;
if(w) f[w]=y;
f[y]=x;f[x]=z;
pushup(y);
}

void pushall(int x)
{
if(nroot(x)) pushall(f[x]);
pushdown(x);
}

void splay(int x)
{
pushall(x);
while(nroot(x))
{
int y=f[x],z=f[y];
if(nroot(y)) rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}

void access(int x){for(int y=0;x;x=f[y=x]) splay(x),rc=y,pushup(x);}
void makeroot(int x){access(x);splay(x);pushr(x);}

int findroot(int x)
{
access(x);splay(x);
while(lc) pushdown(x),x=lc;
splay(x);
return x;
}

void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);if(findroot(y)!=x) f[x]=y;}

void cut(int x,int y)
{
makeroot(x);
if(findroot(y)==x && f[y]==x && !c[y][0]) f[y]=rc=0,pushup(x);
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>T.v[i];
for(int Case=1;Case<=m;Case++)
{
int op,x,y;
cin>>op>>x>>y;
if(op==0) T.split(x,y),cout<<T.s[y]<<'\n';
if(op==1) T.link(x,y);
if(op==2) T.cut(x,y);
if(op==3) T.splay(x),T.v[x]=y;
}
return 0;
}

笛卡尔树

「HDU」P1506

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
#define ll long long

struct Tree
{
struct Node
{
int idx,val,par,son[2];
void init(int _idx,int _val,int _par)
{
idx=_idx;val=_val;par=_par;
son[0]=son[1]=0;
}
}t[maxn];

int build(int n)
{
for(int i=1;i<=n;i++)
{
int k=i-1;
while(t[k].val>t[i].val) k=t[k].par;
t[i].son[0]=t[k].son[1];
t[k].son[1]=i;
t[i].par=k;
t[t[i].son[0]].par=i;
}
return t[0].son[1];
}

int dfs(int u,ll &ans)
{
if(!u) return 0;
int sum=dfs(t[u].son[0],ans)+dfs(t[u].son[1],ans);
ans=max(ans,(ll)(sum+1)*t[u].val);
return sum+1;
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;
while(cin>>n && n)
{
T.t[0].init(0,0,0);
for(int i=1;i<=n;i++)
{
int val;cin>>val;
T.t[i].init(i,val,0);
}
int root=T.build(n);
ll ans=0;
T.dfs(root,ans);
cout<<ans<<'\n';
}
return 0;
}

珂朵莉树

「洛谷」P2787

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
#include <bits/stdc++.h>
using namespace std;

struct Node
{
mutable int l,r,val;
bool operator < (const Node &B) const{return l<B.l;}
};

inline int get(char c)
{
if(c>='a' && c<='z') return c-'a';
return c-'A';
}

struct ODT
{
int n,cnt[26];
set<Node>odt;

set<Node>::iterator split(int x)
{
if(x>n) return odt.end();
auto it=--odt.upper_bound((Node){x,0,0});
if(it->l==x) return it;
int l=it->l,r=it->r,val=it->val;
odt.erase(it);
odt.insert((Node){l,x-1,val});
return odt.insert((Node){x,r,val}).first;
}

int query(int l,int r,int val)
{
int res=0;
auto itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++) if(itl->val==val) res+=itl->r-itl->l+1;
return res;
}

void assign(int l,int r,int val)
{
auto itr=split(r+1),itl=split(l);
odt.erase(itl,itr);
odt.insert((Node){l,r,val});
}

void change(int l,int r)
{
memset(cnt,0,sizeof cnt);
auto itr=split(r+1),itl=split(l);
while(itl!=itr) cnt[itl->val]+=itl->r-itl->l+1,itl=odt.erase(itl);
for(int i=0;i<26;i++) if(cnt[i])
{
odt.insert((Node){l,l+cnt[i]-1,i});
l+=cnt[i];
}
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
T.n=n;
for(int i=1;i<=n;i++)
{
char c;cin>>c;
T.odt.insert((Node){i,i,get(c)});
}
int op,a,b;char c;
for(int Case=1;Case<=m;Case++)
{
cin>>op>>a>>b;
if(op==1)
{
cin>>c;
cout<<T.query(a,b,get(c))<<'\n';
}
if(op==2) cin>>c,T.assign(a,b,get(c));
if(op==3) T.change(a,b);
}
return 0;
}

可持久化数组

「洛谷」P3919

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

int a[maxn];

struct CTree
{
struct Node
{
int ls,rs;
int val;
}N[maxn<<5];

int RT[maxn],Ncnt;

void build(int &rt,int l,int r)
{
rt=++Ncnt;
if(l==r)
{
N[rt].val=a[l];
return;
}
int mid=(l+r)>>1;
build(N[rt].ls,l,mid);
build(N[rt].rs,mid+1,r);
}

int update(int rt,int p,int val,int l,int r)
{
int nrt=++Ncnt;
N[nrt]=N[rt];
if(l==r)
{
N[nrt].val=val;
return nrt;
}
int mid=(l+r)>>1;
if(p<=mid) N[nrt].ls=update(N[nrt].ls,p,val,l,mid);
else N[nrt].rs=update(N[nrt].rs,p,val,mid+1,r);
return nrt;
}

int query(int rt,int p,int l,int r)
{
if(l==r) return N[rt].val;
int mid=(l+r)>>1;
if(p<=mid) return query(N[rt].ls,p,l,mid);
else return query(N[rt].rs,p,mid+1,r);
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
T.build(T.RT[0],1,n);

for(int i=1;i<=m;i++)
{
int v,op,p,val;
cin>>v>>op;
if(op==1)
{
cin>>p>>val;
T.RT[i]=T.update(T.RT[v],p,val,1,n);
}
if(op==2)
{
cin>>p;
T.RT[i]=T.RT[v];
cout<<T.query(T.RT[i],p,1,n)<<'\n';
}
}
return 0;
}

划分树

「洛谷」P3834

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;

struct Tree
{
int sorted[maxn];
int tree[20][maxn],tol[20][maxn];

void build(int rt,int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
int isame=mid-l+1;
for(int i=l;i<=r;i++) if(tree[rt][i]<sorted[mid]) isame--;
int subl=l,subr=mid+1;
for(int i=l;i<=r;i++)
{
if(i==l) tol[rt][i]=0;
else tol[rt][i]=tol[rt][i-1];
if(tree[rt][i]<sorted[mid] || (tree[rt][i]==sorted[mid] && isame))
{
tree[rt+1][subl++]=tree[rt][i];
tol[rt][i]++;
if(tree[rt][i]==sorted[mid]) isame--;
}
else tree[rt+1][subr++]=tree[rt][i];
}
build(rt+1,l,mid);build(rt+1,mid+1,r);
}

int query(int rt,int l,int r,int ql,int qr,int k)
{
int mid=(l+r)>>1;
if(ql==qr) return tree[rt][ql];
int toll=0,tolsum=0;
if(ql==l) toll=0,tolsum=tol[rt][qr];
else toll=tol[rt][ql-1],tolsum=tol[rt][qr]-toll;

if(k<=tolsum)
{
int nl=l+toll;
int nr=l+toll+tolsum-1;
return query(rt+1,l,mid,nl,nr,k);
}
else
{
int nl=mid+1+ql-l-toll;
int nr=mid+1+qr-l-toll-tolsum;
return query(rt+1,mid+1,r,nl,nr,k-tolsum);
}
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>T.sorted[i],T.tree[0][i]=T.sorted[i];
sort(T.sorted+1,T.sorted+n+1);
T.build(0,1,n);
for(int i=1;i<=m;i++)
{
int l,r,k;
cin>>l>>r>>k;
cout<<T.query(0,1,n,l,r,k)<<'\n';
}
return 0;
}

主席树

「洛谷」P3834

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;

struct CTree
{
struct Node
{
int ls,rs;
int sum;
}N[maxn<<5];

int RT[maxn<<5],Ncnt;

void build(int &rt,int l,int r)
{
rt=++Ncnt;
if(l==r) return;
int mid=(l+r)>>1;
build(N[rt].ls,l,mid);
build(N[rt].rs,mid+1,r);
}

int update(int rt,int l,int r,int p)
{
int nrt=++Ncnt;
N[nrt].ls=N[rt].ls,N[nrt].rs=N[rt].rs,N[nrt].sum=N[rt].sum+1;
if(l==r) return nrt;
int mid=(l+r)>>1;
if(p<=mid) N[nrt].ls=update(N[nrt].ls,l,mid,p);
else N[nrt].rs=update(N[nrt].rs,mid+1,r,p);
return nrt;
}

int query(int u,int v,int l,int r,int k)
{
int mid=(l+r)>>1,x=N[N[v].ls].sum-N[N[u].ls].sum;
if(l==r) return l;
if(x>=k) return query(N[u].ls,N[v].ls,l,mid,k);
else return query(N[u].rs,N[v].rs,mid+1,r,k-x);
}
}T;

int a[maxn],b[maxn];

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;

T.build(T.RT[0],1,len);
for(int i=1;i<=n;i++)
{
int p=lower_bound(b+1,b+len+1,a[i])-b;
T.RT[i]=T.update(T.RT[i-1],1,len,p);
}
for(int i=1;i<=m;i++)
{
int l,r,k;
cin>>l>>r>>k;
int p=T.query(T.RT[l-1],T.RT[r],1,len,k);
cout<<b[p]<<'\n';
}
return 0;
}

带修主席树

「洛谷」P2617

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

int a[maxn],b[maxn<<1],len;

struct ques
{
char C;
int a,b,c;
}Q[maxn];

struct Tree
{
struct Node
{
int ls,rs;
int sum;
}N[maxn<<7];

int RT[maxn],Ncnt;
int L[maxn],R[maxn],Lcnt,Rcnt;

int n,len;
inline int lowbit(int x){return x&(-x);}

void update(int &rt,int l,int r,int x,int v)
{
if(!rt) rt=++Ncnt;
N[rt].sum+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) update(N[rt].ls,l,mid,x,v);
else update(N[rt].rs,mid+1,r,x,v);
}

inline void add(int x,int v)
{
int pos=lower_bound(b+1,b+len+1,a[x])-b;
for(int i=x;i<=n;i+=lowbit(i)) update(RT[i],1,len,pos,v);
}

int query(int l,int r,int k)
{
if(l==r) return l;
int val=0,mid=(l+r)>>1;
for(int i=1;i<=Lcnt;i++) val-=N[N[L[i]].ls].sum;
for(int i=1;i<=Rcnt;i++) val+=N[N[R[i]].ls].sum;
if(k<=val)
{
for(int i=1;i<=Lcnt;i++) L[i]=N[L[i]].ls;
for(int i=1;i<=Rcnt;i++) R[i]=N[R[i]].ls;
return query(l,mid,k);
}
else
{
for(int i=1;i<=Lcnt;i++) L[i]=N[L[i]].rs;
for(int i=1;i<=Rcnt;i++) R[i]=N[R[i]].rs;
return query(mid+1,r,k-val);
}
}

int ask(int l,int r,int k)
{
Lcnt=Rcnt=0;
for(int i=l-1;i;i-=lowbit(i)) L[++Lcnt]=RT[i];
for(int i=r;i;i-=lowbit(i)) R[++Rcnt]=RT[i];
return query(1,len,k);
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],b[++len]=a[i];
for(int i=1;i<=m;i++)
{
cin>>Q[i].C;
if(Q[i].C=='Q') cin>>Q[i].a>>Q[i].b>>Q[i].c;
else cin>>Q[i].a>>Q[i].b,b[++len]=Q[i].b;
}
sort(b+1,b+len+1);
len=unique(b+1,b+len+1)-b-1;
T.n=n;T.len=len;
for(int i=1;i<=n;i++) T.add(i,1);

for(int i=1;i<=m;i++)
{
if(Q[i].C=='Q')
{
int pos=T.ask(Q[i].a,Q[i].b,Q[i].c);
cout<<b[pos]<<'\n';
}
else
{
T.add(Q[i].a,-1);
a[Q[i].a]=Q[i].b;
T.add(Q[i].a,1);
}
}
return 0;
}

左偏树

「洛谷」P3377

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
const int INF=1e9;

struct LTree
{
struct Node
{
int val,ls,rs,dis,fa;
}t[maxn];
int cnt;

int merge(int x,int y)
{
if(!x || !y) return x+y;
if(t[x].val>t[y].val || (t[x].val==t[y].val && x>y)) swap(x,y);
t[x].rs=merge(t[x].rs,y);
t[t[x].rs].fa=x;
if(t[t[x].rs].dis>t[t[x].ls].dis) swap(t[x].ls,t[x].rs);
if(t[x].rs==0) t[x].dis=0;
else t[x].dis=t[t[x].rs].dis+1;
return x;
}

int find(int x)
{
if(x==t[x].fa) return x;
return t[x].fa=find(t[x].fa);
}

void del(int x)
{
int ls=t[x].ls,rs=t[x].rs;
t[x].fa=t[x].ls=t[x].rs=t[x].dis=0;
t[x].val=-INF;
t[ls].fa=ls;t[rs].fa=rs;
t[x].fa=merge(ls,rs);
}

int build(int n)
{
queue<int>q;
for(int i=1;i<=n;i++) q.push(i);
while(!q.empty())
{
if(q.size()==1) break;
int a=q.front();q.pop();
int b=q.front();q.pop();
q.push(merge(a,b));
}
return q.front();
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>T.t[i].val;
T.t[i].fa=i;
}

int op,a,b;
for(int i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>a>>b;
if(T.t[a].val==-INF || T.t[b].val==-INF) continue;
int pa=T.find(a),pb=T.find(b);
if(pa==pb) continue;
T.merge(pa,pb);
}
if(op==2)
{
cin>>a;
if(T.t[a].val==-INF) cout<<-1<<'\n';
else
{
int pa=T.find(a);
cout<<T.t[pa].val<<'\n';
T.del(pa);
}
}
}
return 0;
}

轻重链剖分

「洛谷」P3384

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
#define ll long long
#define ls rt<<1
#define rs rt<<1|1

int a[maxn],pdfn[maxn];

struct Link
{
struct Edge
{
int u,v,next;
}E[maxn<<1];
int Ecnt;

struct Node
{
int head,top;
int fa,maxson;
int size,dfn,dep;
bool vis;
}N[maxn];

void add(int u,int v)
{
E[++Ecnt]=(Edge){u,v,N[u].head};N[u].head=Ecnt;
E[++Ecnt]=(Edge){v,u,N[v].head};N[v].head=Ecnt;
}

void dfs1(int u)
{
N[u].vis=true;
N[u].size=1;
for(int i=N[u].head;i;i=E[i].next)
{
int v=E[i].v;
if(N[v].vis) continue;
N[v].fa=u;
N[v].dep=N[u].dep+1;
dfs1(v);
N[u].size+=N[v].size;
if(!N[u].maxson || N[v].size>N[N[u].maxson].size) N[u].maxson=v;
}
}

void dfs2(int u)
{
static int ts=0;
N[u].dfn=++ts;
pdfn[ts]=u;

if(!N[u].fa || u!=N[N[u].fa].maxson) N[u].top=u;
else N[u].top=N[N[u].fa].top;

if(N[u].maxson) dfs2(N[u].maxson);
for(int i=N[u].head;i;i=E[i].next)
{
int v=E[i].v;
if(N[v].fa==u && v!=N[u].maxson) dfs2(v);
}
}

void split(int u)
{
N[u].dep=1;
dfs1(u);
dfs2(u);
}

struct SegT
{
struct node
{
int l,r;
int len;
ll sum,lazy;
}t[maxn<<2];

void pushup(int rt){t[rt].sum=t[ls].sum+t[rs].sum;}

void pushdown(int rt)
{
if(!t[rt].lazy) return;
t[ls].sum+=t[ls].len*t[rt].lazy;t[ls].lazy+=t[rt].lazy;
t[rs].sum+=t[rs].len*t[rt].lazy;t[rs].lazy+=t[rt].lazy;
t[rt].lazy=0;
}

void build(int rt,int l,int r)
{
t[rt].len=r-l+1;
t[rt].l=l;t[rt].r=r;
t[rt].sum=t[rt].lazy=0;
if(l==r)
{
t[rt].sum=a[pdfn[l]];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}

void add(int rt,int l,int r,ll val)
{
if(t[rt].l==l && t[rt].r==r)
{
t[rt].sum+=val*t[rt].len;
t[rt].lazy+=val;
return;
}
pushdown(rt);
int mid=(t[rt].l+t[rt].r)>>1;
if(r<=mid) add(ls,l,r,val);
else if(l>=mid+1) add(rs,l,r,val);
else add(ls,l,mid,val),add(rs,mid+1,r,val);
pushup(rt);
}

ll querysum(int rt,int l,int r)
{
if(t[rt].l==l && t[rt].r==r) return t[rt].sum;
pushdown(rt);
int mid=(t[rt].l+t[rt].r)>>1;
if(r<=mid) return querysum(ls,l,r);
if(l>=mid+1) return querysum(rs,l,r);
return querysum(ls,l,mid)+querysum(rs,mid+1,r);
}

}tree;

void Build(int n){tree.build(1,1,n);}

ll Querysum(int u,int v)
{
ll ans=0;
while(N[u].top!=N[v].top)
{
if(N[N[u].top].dep<N[N[v].top].dep) swap(u,v);
ans+=tree.querysum(1,N[N[u].top].dfn,N[u].dfn);
u=N[N[u].top].fa;
}
if(N[u].dep>N[v].dep) swap(u,v);
ans+=tree.querysum(1,N[u].dfn,N[v].dfn);
return ans;
}

void Add(int u,int v,ll val)
{
while(N[u].top!=N[v].top)
{
if(N[N[u].top].dep<N[N[v].top].dep) swap(u,v);
tree.add(1,N[N[u].top].dfn,N[u].dfn,val);
u=N[N[u].top].fa;
}
if(N[u].dep>N[v].dep) swap(u,v);
tree.add(1,N[u].dfn,N[v].dfn,val);
}
}Tree;

int main()
{
ios::sync_with_stdio(false);
int n,m,r,p;
cin>>n>>m>>r>>p;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
Tree.add(u,v);
}
Tree.split(r);
Tree.Build(n);
int a,u,v,val;
for(int i=1;i<=m;i++)
{
cin>>a;
if(a==1)
{
cin>>u>>v>>val;
Tree.Add(u,v,val);
}
if(a==2)
{
cin>>u>>v;
ll ans=Tree.Querysum(u,v);
cout<<ans%p<<'\n';
}
if(a==3)
{
cin>>u>>val;
Tree.tree.add(1,Tree.N[u].dfn,Tree.N[u].dfn+Tree.N[u].size-1,val);
}
if(a==4)
{
cin>>u;
ll ans=Tree.tree.querysum(1,Tree.N[u].dfn,Tree.N[u].dfn+Tree.N[u].size-1);
cout<<ans%p<<'\n';
}
}
return 0;
}

Splay区间更新

「HihoCoder」P1333

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
const int INF=1e9;
#define ll long long

struct Splay
{
int son[maxn][2],fa[maxn],key[maxn],siz[maxn],root,cnt;
ll val[maxn],lazy[maxn],sum[maxn];
#define ls(rt) son[rt][0]
#define rs(rt) son[rt][1]

void pushup(int rt)
{
siz[rt]=1,sum[rt]=val[rt];
if(ls(rt)) siz[rt]+=siz[ls(rt)],sum[rt]+=sum[ls(rt)];
if(rs(rt)) siz[rt]+=siz[rs(rt)],sum[rt]+=sum[rs(rt)];
}

void pushdown(int rt)
{
if(!lazy[rt]) return;
if(ls(rt)) lazy[ls(rt)]+=lazy[rt],sum[ls(rt)]+=siz[ls(rt)]*lazy[rt],val[ls(rt)]+=lazy[rt];
if(rs(rt)) lazy[rs(rt)]+=lazy[rt],sum[rs(rt)]+=siz[rs(rt)]*lazy[rt],val[rs(rt)]+=lazy[rt];
lazy[rt]=0;
}

int newnode(int f,int k,int v)
{
cnt++;ls(cnt)=rs(cnt)=0;
fa[cnt]=f;siz[cnt]=1;key[cnt]=k;
val[cnt]=v;sum[cnt]=v;lazy[cnt]=0;
return cnt;
}

void init()
{
cnt=0;root=newnode(0,-INF,0);
rs(root)=newnode(root,INF,0);
pushup(root);
}

void rotate(int x,int c)
{
int f=fa[x],pref=fa[f];
pushdown(f),pushdown(x);
if(pref!=0) son[pref][ls(pref)!=f]=x;
fa[x]=pref;
son[f][c]=son[x][!c];
fa[son[x][!c]]=f;
son[x][!c]=f;
fa[f]=x;
pushup(f);
}

void splay(int x,int y)
{
pushdown(x);
while(fa[x]!=y)
{
int f=fa[x];
int c1=(ls(fa[f])==f),c2=(ls(f)==x);
if(fa[f]==y) rotate(x,!c2);
else
{
if(c1^c2) rotate(x,!c2),rotate(x,c2);
else rotate(f,!c1),rotate(x,!c1);
}
}
pushup(x);
if(!y) root=x;
}

int insert(int x,int val)
{
int now=root,f=0;
while(now)
{
pushdown(now);
siz[now]++;
sum[now]+=val;
f=now;
now=son[now][x>=key[now]];
}
int id=newnode(f,x,val);
son[f][x>=key[f]]=id;
splay(id,0);
return id;
}

int findpre(int x)
{
int now=root,ans=0;
while(now)
{
pushdown(now);
if(key[now]<x) ans=now,now=rs(now);
else now=ls(now);
}
return ans;
}

int findnxt(int x)
{
int now=root,ans=0;
while(now)
{
pushdown(now);
if(key[now]>x) ans=now,now=ls(now);
else now=rs(now);
}
return ans;
}

void cut(int l,int r)
{
int x=findpre(l);
int y=findnxt(r);
splay(x,0);splay(y,x);
ls(y)=0;
pushup(y);pushup(x);
}

ll query(int l,int r)
{
int x=findpre(l);
int y=findnxt(r);
splay(x,0);splay(y,x);
return sum[ls(y)];
}

void update(int l,int r,int v)
{

int x=findpre(l);
int y=findnxt(r);
splay(x,0);splay(y,x);
sum[ls(y)]+=(ll)siz[ls(y)]*v;
val[ls(y)]+=v;lazy[ls(y)]+=v;
pushup(y);pushup(x);
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;cin>>n;
T.init();
for(int i=1;i<=n;i++)
{
char s;cin>>s;
int a,b,c;
if(s=='I') cin>>a>>b,T.insert(a,b);
if(s=='Q') cin>>a>>b,cout<<T.query(a,b)<<'\n';
if(s=='D') cin>>a>>b,T.cut(a,b);
if(s=='M') cin>>a>>b>>c,T.update(a,b,c);
}
return 0;
}

文艺平衡树

「洛谷」P3391

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
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct Splay
{
struct Node
{
int fa,val;
int son[2];
int size,tag;
}N[maxn];

int n;
int Ncnt,rt;
int Q[maxn],top;

void update(int x)
{
N[x].size=1;
if(N[x].son[0]) N[x].size+=N[N[x].son[0]].size;
if(N[x].son[1]) N[x].size+=N[N[x].son[1]].size;
}

inline int get(int x){return N[N[x].fa].son[1]==x;}

void pushdown(int x)
{
if(!N[x].tag) return;
N[x].tag=0;
N[N[x].son[0]].tag^=1;
N[N[x].son[1]].tag^=1;
swap(N[x].son[0],N[x].son[1]);
}

inline void add(int x,int y,int z){N[x].fa=y;N[y].son[z]=x;}

void rotate(int x)
{
int fa=N[x].fa,ffa=N[fa].fa,a=get(x),b=get(fa);
add(x,ffa,b);
add(N[x].son[a^1],fa,a);
add(fa,x,a^1);
update(fa);update(x);
}

void splay(int x,int goal)
{
top=0;
for(int i=x;i;i=N[i].fa) Q[++top]=i;
for(int i=top;i;i--) pushdown(Q[i]);
while(N[x].fa!=goal)
{
int fa=N[x].fa;
if(N[fa].fa!=goal) rotate(get(x)==get(fa)?fa:x);
rotate(x);
}
if(!goal) rt=x;
}

void insert(int x)
{
int now=rt,fa=0;
while(now) fa=now,now=N[now].son[x>N[now].val];
now=++Ncnt;
N[now].val=x;N[now].fa=fa;
if(fa) N[fa].son[x>N[fa].val]=now;
N[now].size=1;
N[now].son[0]=N[now].son[1]=0;
splay(now,0);
}

int kth(int x)
{
int now=rt;
while(1)
{
pushdown(now);
if(N[N[now].son[0]].size>=x) now=N[now].son[0];
else
{
x-=N[N[now].son[0]].size;
if(x==1) return now;
x--;now=N[now].son[1];
}
}
}

void change(int l,int r)
{
l=kth(l),r=kth(r+2);
splay(l,0);splay(r,l);
N[N[r].son[0]].tag^=1;
}

void write(int x)
{
pushdown(x);
if(N[x].son[0]) write(N[x].son[0]);
if(N[x].val>=2 && N[x].val<=n+1) cout<<N[x].val-1<<' ';
if(N[x].son[1]) write(N[x].son[1]);
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
T.n=n;
for(int i=1;i<=n+2;i++) T.insert(i);
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
T.change(l,r);
}
T.write(T.rt);
return 0;
}

可持久化平衡树

「洛谷」P3835

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;
const int INF=2147483647;

struct Treap
{
struct Node
{
int ls,rs;
int size,val;
int rnd;
}N[maxn<<6];

int RT[maxn],Ncnt;

inline int Rand()
{
static int seed=233;
return seed=(int)seed*482711LL%2147483647;
}

void pushup(int rt){N[rt].size=N[N[rt].ls].size+N[N[rt].rs].size+1;}

void newnode(int &rt,int val)
{
rt=++Ncnt;
N[rt].val=val;N[rt].size=1;N[rt].rnd=Rand();
}

int merge(int x,int y)
{
if(!x || !y) return x+y;
int rt=++Ncnt;
if(N[x].rnd>N[y].rnd)
{
N[rt]=N[x];
N[rt].rs=merge(N[rt].rs,y);
pushup(rt);
}
else
{
N[rt]=N[y];
N[rt].ls=merge(x,N[rt].ls);
pushup(rt);
}
return rt;
}

void split(int rt,int val,int &x,int &y)
{
if(!rt)
{
x=y=0;
return;
}
if(N[rt].val<=val)
{
x=++Ncnt;N[x]=N[rt];
split(N[x].rs,val,N[x].rs,y);
pushup(x);
}
else
{
y=++Ncnt;N[y]=N[rt];
split(N[y].ls,val,x,N[y].ls);
pushup(y);
}
}

void Delete(int &rt,int val)
{
int x=0,y=0,z=0;
split(rt,val,x,z);
split(x,val-1,x,y);
y=merge(N[y].ls,N[y].rs);
rt=merge(merge(x,y),z);
}

void Insert(int &rt,int val)
{
int x=0,y=0,z=0;
split(rt,val,x,y);
newnode(z,val);
rt=merge(merge(x,z),y);
}

int getval(int rt,int k)
{
if(k==N[N[rt].ls].size+1) return N[rt].val;
if(k<=N[N[rt].ls].size) return getval(N[rt].ls,k);
return getval(N[rt].rs,k-N[N[rt].ls].size-1);
}

int getkth(int &rt,int val)
{
int x=0,y=0;
split(rt,val-1,x,y);
int ans=N[x].size+1;
rt=merge(x,y);
return ans;
}

int getpre(int &rt,int val)
{
int x=0,y=0;
split(rt,val-1,x,y);
if(!x) return -INF;
int ans=getval(x,N[x].size);
rt=merge(x,y);
return ans;
}

int getnex(int &rt,int val)
{
int x=0,y=0;
split(rt,val,x,y);
if(!y) return INF;
int ans=getval(y,1);
rt=merge(x,y);
return ans;
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int v,op,val;
cin>>v>>op>>val;
T.RT[i]=T.RT[v];
if(op==1) T.Insert(T.RT[i],val);
if(op==2) T.Delete(T.RT[i],val);
if(op==3) cout<<T.getkth(T.RT[i],val)<<'\n';
if(op==4) cout<<T.getval(T.RT[i],val)<<'\n';
if(op==5) cout<<T.getpre(T.RT[i],val)<<'\n';
if(op==6) cout<<T.getnex(T.RT[i],val)<<'\n';
}
return 0;
}

可持久化文艺平衡树

「洛谷」P5055

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
#define ll long long

struct Treap
{
struct Node
{
int rnd,size,tag;
ll sum,val;
int ls,rs;
}N[maxn<<6];

int RT[maxn],Ncnt;

inline int Rand()
{
static int seed=233;
return seed=(int)seed*482711LL%2147483647;
}

inline int newnode(ll val=0)
{
++Ncnt;
N[Ncnt].val=val;N[Ncnt].sum=val;
N[Ncnt].rnd=Rand();N[Ncnt].size=1;
return Ncnt;
}

inline int copynode(int rt)
{
int now=newnode();
N[now]=N[rt];
return now;
}

inline void pushup(int rt)
{
N[rt].size=N[N[rt].ls].size+N[N[rt].rs].size+1;
N[rt].sum=N[N[rt].ls].sum+N[N[rt].rs].sum+N[rt].val;
}

void pushdown(int rt)
{
if(!N[rt].tag) return;
if(N[rt].ls) N[rt].ls=copynode(N[rt].ls);
if(N[rt].rs) N[rt].rs=copynode(N[rt].rs);
swap(N[rt].ls,N[rt].rs);
if(N[rt].ls) N[N[rt].ls].tag^=1;
if(N[rt].rs) N[N[rt].rs].tag^=1;
N[rt].tag=0;
}

void split(int rt,int k,int &x,int &y)
{
if(!rt){x=y=0;return;}
pushdown(rt);
if(N[N[rt].ls].size<k)
{
x=copynode(rt);
split(N[x].rs,k-N[N[rt].ls].size-1,N[x].rs,y);
pushup(x);
}
else
{
y=copynode(rt);
split(N[y].ls,k,x,N[y].ls);
pushup(y);
}
}

int merge(int x,int y)
{
if(!x || !y) return x+y;
pushdown(x);pushdown(y);
if(N[x].rnd<N[y].rnd)
{
N[x].rs=merge(N[x].rs,y);
pushup(x);
return x;
}
else
{
N[y].ls=merge(x,N[y].ls);
pushup(y);
return y;
}
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n;cin>>n;
int v,op;
ll a,b;int x,y,z;
ll lastans=0;
for(int i=1;i<=n;i++)
{
cin>>v>>op;
if(op==1)
{
cin>>a>>b;
a^=lastans;b^=lastans;
T.split(T.RT[v],a,x,y);
T.RT[i]=T.merge(T.merge(x,T.newnode(b)),y);
}
if(op==2)
{
cin>>a;
a^=lastans;
T.split(T.RT[v],a,x,z);
T.split(x,a-1,x,y);
T.RT[i]=T.merge(x,z);
}
if(op==3)
{
cin>>a>>b;
a^=lastans;b^=lastans;
T.split(T.RT[v],b,x,z);
T.split(x,a-1,x,y);
T.N[y].tag^=1;
T.RT[i]=T.merge(T.merge(x,y),z);
}
if(op==4)
{
cin>>a>>b;
a^=lastans;b^=lastans;
T.split(T.RT[v],b,x,z);
T.split(x,a-1,x,y);
cout<<T.N[y].sum<<'\n';
lastans=T.N[y].sum;
T.RT[i]=T.merge(T.merge(x,y),z);
}
}
return 0;
}

可持久化并查集

「洛谷」P3402

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
114
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct CTree
{
struct Node
{
int ls,rs;
int val,dep;
}N[maxn<<5];

int RT[maxn<<1],Ncnt;

void build(int &rt,int l,int r)
{
rt=++Ncnt;
if(l==r)
{
N[rt].val=l;
return;
}
int mid=(l+r)>>1;
build(N[rt].ls,l,mid);
build(N[rt].rs,mid+1,r);
}

int update(int rt,int p,int val,int l,int r)
{
int nrt=++Ncnt;
N[nrt]=N[rt];
if(l==r)
{
N[nrt].val=val;
return nrt;
}
int mid=(l+r)>>1;
if(p<=mid) N[nrt].ls=update(N[nrt].ls,p,val,l,mid);
else N[nrt].rs=update(N[nrt].rs,p,val,mid+1,r);
return nrt;
}

int query(int rt,int p,int l,int r)
{
if(l==r) return rt;
int mid=(l+r)>>1;
if(p<=mid) return query(N[rt].ls,p,l,mid);
else return query(N[rt].rs,p,mid+1,r);
}

void add(int rt,int pos,int l,int r)
{
if(l==r)
{
N[rt].dep++;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) add(N[rt].ls,pos,l,mid);
else add(N[rt].rs,pos,mid+1,r);
}
}T;

int find(int rt,int x,int n)
{
int rx=T.query(rt,x,1,n);
if(x==T.N[rx].val) return rx;
return find(rt,T.N[rx].val,n);
}

void deal(int &rt,int a,int b,int n)
{
int ra=find(rt,a,n);
int rb=find(rt,b,n);
if(T.N[ra].val==T.N[rb].val) return;
if(T.N[ra].dep>T.N[rb].dep) swap(ra,rb);
rt=T.update(rt,T.N[ra].val,T.N[rb].val,1,n);
if(T.N[ra].dep==T.N[rb].dep) T.add(rt,T.N[rb].val,1,n);
}

int judge(int rt,int a,int b,int n)
{
int ra=find(rt,a,n);
int rb=find(rt,b,n);
if(T.N[ra].val==T.N[rb].val) return 1;
return 0;
}

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
T.build(T.RT[0],1,n);
for(int i=1;i<=m;i++)
{
int num,a,b;
T.RT[i]=T.RT[i-1];
cin>>num;
if(num==1)
{
cin>>a>>b;
deal(T.RT[i],a,b,n);
}
if(num==2) cin>>a,T.RT[i]=T.RT[a];
if(num==3)
{
cin>>a>>b;
cout<<judge(T.RT[i],a,b,n)<<'\n';
}
}
return 0;
}

二维线段树

区间求和

「Vijos」P1512

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1050;
#define ll long long
#define ls rt<<1
#define rs rt<<1|1

struct Tree
{
struct Node
{
ll sum[maxn<<2],tag[maxn<<2];

void add(int rt,int L,int R,ll val,int l,int r)
{
sum[rt]+=val*(R-L+1);
if(L==l && R==r)
{
tag[rt]+=val;
return;
}
int mid=(l+r)>>1;
if(R<=mid) add(ls,L,R,val,l,mid);
else if(L>=mid+1) add(rs,L,R,val,mid+1,r);
else add(ls,L,mid,val,l,mid),add(rs,mid+1,R,val,mid+1,r);
}

ll ask(int rt,int L,int R,ll res,int l,int r)
{
if(L==l && R==r) return sum[rt]+res*(R-L+1);
res+=tag[rt];
int mid=(l+r)>>1;
if(R<=mid) return ask(ls,L,R,res,l,mid);
else if(L>=mid+1) return ask(rs,L,R,res,mid+1,r);
else return ask(ls,L,mid,res,l,mid)+ask(rs,mid+1,R,res,mid+1,r);
}
}sum[maxn<<2],tag[maxn<<2];

int n,m;

void add(int rt,int x1,int y1,int x2,int y2,ll val,int l,int r)
{
sum[rt].add(1,y1,y2,val*(x2-x1+1),1,m);
if(x1==l && x2==r)
{
tag[rt].add(1,y1,y2,val,1,m);
return;
}
int mid=(l+r)>>1;
if(x2<=mid) add(ls,x1,y1,x2,y2,val,l,mid);
else if(x1>=mid+1) add(rs,x1,y1,x2,y2,val,mid+1,r);
else add(ls,x1,y1,mid,y2,val,l,mid),add(rs,mid+1,y1,x2,y2,val,mid+1,r);
}

ll ask(int rt,int x1,int y1,int x2,int y2,ll res,int l,int r)
{
if(x1==l && x2==r) return sum[rt].ask(1,y1,y2,0,1,m)+res*(r-l+1);
res+=tag[rt].ask(1,y1,y2,0,1,m);
int mid=(l+r)>>1;
if(x2<=mid) return ask(ls,x1,y1,x2,y2,res,l,mid);
else if(x1>=mid+1) return ask(rs,x1,y1,x2,y2,res,mid+1,r);
else return ask(ls,x1,y1,mid,y2,res,l,mid)+ask(rs,mid+1,y1,x2,y2,res,mid+1,r);
}
}T;

int main()
{
ios::sync_with_stdio(false);
int n;cin>>n;
T.n=n;T.m=n;
int m;
while(cin>>m)
{
int x1,y1,x2,y2;
ll val;
if(m==1)
{
cin>>x1>>y1>>val;
x1++;y1++;
T.add(1,x1,y1,x1,y1,val,1,n);
}
if(m==2)
{
cin>>x1>>y1>>x2>>y2;
x1++;y1++;x2++;y2++;
cout<<T.ask(1,x1,y1,x2,y2,0,1,n)<<'\n';
}
if(m==3) break;
}
return 0;
}

区间最值

「洛谷」P3437

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e3+5;
#define ls rt<<1
#define rs rt<<1|1

struct Tree
{
struct Node
{
int t[maxn<<2],lz[maxn<<2];

void update(int L,int R,int x,int l,int r,int rt)
{
t[rt]=max(t[rt],x);
if(l==L && r==R)
{
lz[rt]=max(lz[rt],x);
return;
}
int mid=(l+r)>>1;
if(R<=mid) update(L,R,x,l,mid,ls);
else if(L>mid) update(L,R,x,mid+1,r,rs);
else update(L,mid,x,l,mid,ls),update(mid+1,R,x,mid+1,r,rs);
}

int query(int L,int R,int l,int r,int rt)
{
if(l==L && r==R) return t[rt];
int mid=(l+r)>>1,ret=lz[rt];
if(R<=mid) ret=max(ret,query(L,R,l,mid,ls));
else if(L>mid) ret=max(ret,query(L,R,mid+1,r,rs));
else ret=max(ret,max(query(L,mid,l,mid,ls),query(mid+1,R,mid+1,r,rs)));
return ret;
}
}t[maxn<<2],lz[maxn<<2];

int n,m;

void merge(Node &p,Node &p1,Node &p2,int l,int r,int rt)
{
p.t[rt]=max(p1.t[rt],p2.t[rt]);
if(l==r) return;
int mid=(l+r)>>1;
merge(p,p1,p2,l,mid,ls);
merge(p,p1,p2,mid+1,r,rs);
}

void update(int x,int y,int xx,int yy,int v,int l,int r,int rt)
{
t[rt].update(y,yy,v,1,m,1);
if(l==x && r==xx)
{
lz[rt].update(y,yy,v,1,m,1);
return;
}
int mid=(l+r)>>1;
if(mid>=xx) update(x,y,xx,yy,v,l,mid,ls);
else if(x>mid) update(x,y,xx,yy,v,mid+1,r,rs);
else update(x,y,mid,yy,v,l,mid,ls),update(mid+1,y,xx,yy,v,mid+1,r,rs);
}

int query(int x,int y,int xx,int yy,int l,int r,int rt)
{
if(l==x && r==xx) return t[rt].query(y,yy,1,m,1);
int mid=(l+r)>>1,ret=lz[rt].query(y,yy,1,m,1);
if(mid>=xx) ret=max(ret,query(x,y,xx,yy,l,mid,ls));
else if(x>mid) ret=max(ret,query(x,y,xx,yy,mid+1,r,rs));
else ret=max(ret,max(query(x,y,mid,yy,l,mid,ls),query(mid+1,y,xx,yy,mid+1,r,rs)));
return ret;
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int d,s,n;
cin>>d>>s>>n;
T.n=d;T.m=s;
for(int i=1;i<=n;i++)
{
int w,x,y;
cin>>d>>s>>w>>x>>y;
x++;y++;
w+=T.query(x,y,x+d-1,y+s-1,1,T.n,1);
T.update(x,y,x+d-1,y+s-1,w,1,T.n,1);
}
cout<<T.query(1,1,T.n,T.m,1,T.n,1);
return 0;
}

图论

最小费用最大流

「洛谷」P3381

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int INF=1e9;

struct Node
{
int u,v,next;
int cap,cost;
}E[maxn];
int head[maxn],Ecnt;

void add(int u,int v,int cap,int cost)
{
E[++Ecnt]=(Node){u,v,head[u],cap,cost};head[u]=Ecnt;
E[++Ecnt]=(Node){v,u,head[v],0,-cost};head[v]=Ecnt;
}

bool vis[maxn];
int pre[maxn],dis[maxn];

bool spfa(int s,int t,int n)
{
queue<int>q;
memset(vis,0,sizeof vis);
memset(pre,0,sizeof pre);
for(int i=1;i<=n;i++) dis[i]=INF;

vis[s]=1;dis[s]=0;q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap && dis[v]>dis[u]+E[i].cost)
{
dis[v]=dis[u]+E[i].cost;pre[v]=i;
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
return dis[t]!=INF;
}

void MCMF(int s,int t,int n,int &flow,int &mincost)
{
flow=mincost=0;
while(spfa(s,t,n))
{
int minflow=INF;
for(int i=pre[t];i;i=pre[E[i].u]) minflow=min(minflow,E[i].cap);
flow+=minflow;
for(int i=pre[t];i;i=pre[E[i].u])
{
E[i].cap-=minflow;
E[((i-1)^1)+1].cap+=minflow;
}
mincost+=dis[t]*minflow;
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int u,v,cap,cost;
cin>>u>>v>>cap>>cost;
add(u,v,cap,cost);
}
int flow,mincost;
MCMF(s,t,n,flow,mincost);
cout<<flow<<' '<<mincost;
return 0;
}

二分图匹配

匈牙利算法

「洛谷」P3386

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=500+5;

vector<int>vec[maxn];
bool vis[maxn];
int match[maxn];

bool dfs(int u)
{
for(auto v:vec[u]) if(!vis[v])
{
vis[v]=true;
if(!match[v] || dfs(match[v]))
{
match[v]=u;
return true;
}
}
return false;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m,e;
cin>>n>>m>>e;
for(int i=1;i<=e;i++)
{
int u,v;
cin>>u>>v;
vec[u].push_back(v);
}

int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}

Hopcroft-Karp

「HDU」P6808

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int INF=1e9;

int a[maxn],A[maxn],lena;
int b[maxn],B[maxn],lenb;
vector<int>vec[maxn];

int mx[maxn],my[maxn];
int dx[maxn],dy[maxn];
bool used[maxn];
int dis;

bool BFS()
{
queue<int>Q;dis=INF;
memset(dx,0,sizeof dx);
memset(dy,0,sizeof dy);
for(int i=1;i<=lena;i++) if(!mx[i])
{
Q.push(i);
dx[i]=1;
}
while(!Q.empty())
{
int u=Q.front();Q.pop();
if(dx[u]>dis) break;
for(auto v:vec[u]) if(!dy[v])
{
dy[v]=dx[u]+1;
if(!my[v]) dis=dy[v];
else dx[my[v]]=dy[v]+1,Q.push(my[v]);
}
}
return dis!=INF;
}

bool DFS(int u)
{
for(auto v:vec[u]) if(!used[v] && dy[v]==dx[u]+1)
{
used[v]=true;
if(my[v] && dy[v]==dis) continue;
if(!my[v] || DFS(my[v]))
{
my[v]=u;
mx[u]=v;
return true;
}
}
return false;
}

int maxmatch()
{
int ans=0;
memset(mx,0,sizeof mx);
memset(my,0,sizeof my);
while(BFS())
{
memset(used,0,sizeof used);
for(int i=1;i<=lena;i++) if(!mx[i] && DFS(i)) ans++;
}
return ans;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int Case;cin>>Case;
while(Case--)
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int u,v;
cin>>u>>v;
a[i]=A[i]=u-v;
b[i]=B[i]=u+v;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
lena=unique(a+1,a+n+1)-a-1;
lenb=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=lena;i++) vec[i].clear();
for(int i=1;i<=n;i++)
{
int u=lower_bound(a+1,a+lena+1,A[i])-a;
int v=lower_bound(b+1,b+lenb+1,B[i])-b;
vec[u].push_back(v);
}
cout<<maxmatch()<<'\n';
}
return 0;
}

字符串

KMP

「洛谷」P3375

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

int nxt[maxn];
char a[maxn],b[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>a+1>>b+1;
int lena=strlen(a+1);
int lenb=strlen(b+1);

for(int i=2,j=0;i<=lenb;i++)
{
while(j && b[i]!=b[j+1]) j=nxt[j];
if(b[j+1]==b[i]) j++;
nxt[i]=j;
}

for(int i=1,j=0;i<=lena;i++)
{
while(j && b[j+1]!=a[i]) j=nxt[j];
if(b[j+1]==a[i]) j++;
if(j==lenb) cout<<i-lenb+1<<'\n',j=nxt[j];
}

for(int i=1;i<=lenb;i++) cout<<nxt[i]<<' ';
return 0;
}

扩展KMP

「洛谷」P5410

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e7+5;
#define ll long long

char a[maxn],b[maxn];
int nxt[maxn],ext[maxn];

void getnxt(char s[],int n)
{
for(int i=1;i<=n;i++) nxt[i]=0;
nxt[1]=n;
for(int i=2,l=0,r=0;i<=n;i++)
{
if(i<=r) nxt[i]=min(nxt[i-l+1],r-i+1);
while(i+nxt[i]<=n && s[i+nxt[i]]==s[nxt[i]+1]) nxt[i]++;
if(i+nxt[i]-1>r) l=i,r=i+nxt[i]-1;
}
}

void exkmp(char s[],int n,char t[],int m)
{
for(int i=1;i<=n;i++) ext[i]=0;
for(int i=1,l=0,r=0;i<=n;i++)
{
if(i<=r) ext[i]=min(nxt[i-l+1],r-i+1);
while(i+ext[i]<=n && s[i+ext[i]]==t[ext[i]+1]) ext[i]++;
if(i+ext[i]-1>r) l=i,r=i+ext[i]-1;
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>a+1>>b+1;
int n=strlen(a+1);
int m=strlen(b+1);

getnxt(b,m);
exkmp(a,n,b,m);
ll ans=0;
for(int i=1;i<=m;i++) ans^=(ll)i*(nxt[i]+1);
cout<<ans<<'\n';
ans=0;
for(int i=1;i<=n;i++) ans^=(ll)i*(ext[i]+1);
cout<<ans<<'\n';
return 0;
}

后缀数组

「洛谷」P3809

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

struct SufArray
{
int a[maxn],sa[maxn],rk[maxn],oldrk[maxn],id[maxn],px[maxn],ht[maxn],cnt[maxn];
bool cmp(int x,int y,int w){return oldrk[x]==oldrk[y] && oldrk[x+w]==oldrk[y+w];}

void build(int n,int m)
{
for(int i=1;i<=n;i++) ++cnt[rk[i]=a[i]];
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;

for(int p,i,w=1;w<n;w<<=1,m=p)
{
for(p=0,i=n;i>n-w;--i) id[++p]=i;
for(i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w;
memset(cnt,0,sizeof cnt);
for(i=1;i<=n;i++) ++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(i=n;i>=1;i--) sa[cnt[px[i]]--]=id[i];
memcpy(oldrk,rk,sizeof rk);
for(p=0,i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}

for(int i=1,j=0;i<=n;i++)
{
if(j) j--;
while(a[i+j]==a[sa[rk[i]-1]+j]) j++;
ht[rk[i]]=j;
}
}
}SA;

char s[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>s+1;
int n=strlen(s+1);
for(int i=1;i<=n;i++) SA.a[i]=(int)s[i];
SA.build(n,(int)'z');
for(int i=1;i<=n;i++) cout<<SA.sa[i]<<' ';
return 0;
}

AC自动机

「洛谷」P3808

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

struct Tree
{
int c[maxn][26],val[maxn];
int fail[maxn],cnt;

void insert(char *s)
{
int len=strlen(s),u=0;
for(int i=0;i<len;i++)
{
int v=s[i]-'a';
if(!c[u][v]) c[u][v]=++cnt;
u=c[u][v];
}
val[u]++;
}

void build()
{
queue<int>q;
for(int i=0;i<26;i++) if(c[0][i]) fail[c[0][i]]=0,q.push(c[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(c[u][i]) fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
else c[u][i]=c[fail[u]][i];
}
}
}

int query(char *s)
{
int len=strlen(s);
int u=0,ans=0;
for(int i=0;i<len;i++)
{
u=c[u][s[i]-'a'];
for(int t=u;t && val[t]!=-1;t=fail[t])
{
ans+=val[t];
val[t]=-1;
}
}
return ans;
}
}AC;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;char s[maxn];
cin>>n;
for(int i=1;i<=n;i++) cin>>s,AC.insert(s);
AC.build();
cin>>s;
cout<<AC.query(s);
return 0;
}

回文自动机

「洛谷」P5496

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=5e5+5;
const int maxm=26+5;

struct PalAuto
{
char str[maxn];
int Ncnt,last,rt0,rt1;
int trans[maxn][maxm],link[maxn];
int len[maxn],cnt[maxn];

PalAuto()
{
rt0=Ncnt++,rt1=Ncnt++;last=rt1;
len[rt0]=0;link[rt0]=rt1;
len[rt1]=-1;link[rt1]=rt1;
}

void extend(int ch,int pos)
{
int u=last;
for(;str[pos-len[u]-1]!=str[pos];u=link[u]);
if(!trans[u][ch])
{
int newnode=Ncnt++,v=link[u];
len[newnode]=len[u]+2;
for(;str[pos-len[v]-1]!=str[pos];v=link[v]);
link[newnode]=trans[v][ch],trans[u][ch]=newnode;
cnt[newnode]=cnt[link[newnode]]+1;
}
last=trans[u][ch];
}

void build()
{
int Len=strlen(str);
for(int i=0;i<Len;i++)
{
extend(str[i]-'a'+1,i);
str[i+1]=(str[i+1]-97+cnt[last])%26+97;
cout<<cnt[last]<<' ';
}
}
}PAM;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>PAM.str;
PAM.build();
return 0;
}

后缀自动机

「洛谷」P3804

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e6+5;
#define ll long long

struct SufAuto
{
int n,cnt=1,last=1;
int ch[maxn][26],fa[maxn],len[maxn],size[maxn];
vector<int>vec[maxn];
ll ans;

void ins(int c)
{
int p=last,np=++cnt;size[np]=1;
len[last=np]=len[p]+1;
for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=1;
else
{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else
{
int nq=++cnt;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof ch[q]);
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}

void dfs(int u)
{
for(auto v:vec[u]) dfs(v),size[u]+=size[v];
if(size[u]>1) ans=max(ans,(ll)size[u]*len[u]);
}

ll calc()
{
for(int i=2;i<=cnt;i++) vec[fa[i]].push_back(i);
dfs(1);
return ans;
}
}SAM;

char s[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>s;
int len=strlen(s);
for(int i=0;i<len;i++) SAM.ins(s[i]-'a');
cout<<SAM.calc();
return 0;
}

广义后缀自动机

「洛谷」P6139

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e6+5;
#define ll long long

struct EXSufAuto
{
int cnt=1;
int fa[maxn],len[maxn],ch[maxn][26];

int ins(int v,int last)
{
if(ch[last][v])
{
int p=last,x=ch[p][v];
if(len[p]+1==len[x]) return x;
int y=++cnt;len[y]=len[p]+1;
memcpy(ch[y],ch[x],sizeof ch[x]);
while(p && ch[p][v]==x) ch[p][v]=y,p=fa[p];
fa[y]=fa[x],fa[x]=y;
return y;
}
int z=++cnt,p=last;len[z]=len[last]+1;
while(p && !ch[p][v]) ch[p][v]=z,p=fa[p];
if(!p) fa[z]=1;
else
{
int x=ch[p][v];
if(len[p]+1==len[x]) fa[z]=x;
else
{
int y=++cnt;len[y]=len[p]+1;
memcpy(ch[y],ch[x],sizeof ch[x]);
while(p && ch[p][v]==x) ch[p][v]=y,p=fa[p];
fa[y]=fa[x];fa[z]=fa[x]=y;
}
}
return z;
}

ll calc()
{
ll ans=0;
for(int i=2;i<=cnt;i++) ans+=len[i]-len[fa[i]];
return ans;
}
}SAM;

char s[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int T;cin>>T;
while(T--)
{
cin>>s;
int n=strlen(s),last=1;
for(int i=0;i<n;i++) last=SAM.ins(s[i]-'a',last);
}
cout<<SAM.calc();
return 0;
}

最小表示法

「HDU」P6863

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e6+5;

int n;
char s[maxn];

int get(int pos,int len)
{
int k=0,i=0,j=1;
int end=pos+len-1;
while(k<len && pos+i<=end && pos+j<=end)
{
if(s[pos+(i+k)%len]==s[pos+(j+k)%len]) k++;
else
{
s[pos+(i+k)%len]>s[pos+(j+k)%len]?i=i+k+1:j=j+k+1;
if(i==j) i++;
k=0;
}
}
return pos+min(i,j);
}

bool deal(int len)
{
int tot=n/len;
if(tot==1) return false;
int last=get(1,len);
for(int i=2;i<=tot;i++)
{
int temp=get(1+(i-1)*len,len);
for(int j=1;j<=len;j++)
{
int a=last+j-1;if(a>1+(i-2)*len+len-1) a-=len;
int b=temp+j-1;if(b>1+(i-1)*len+len-1) b-=len;
if(s[a]!=s[b]) return false;
}
last=temp;
}
return true;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int Case;cin>>Case;
while(Case--)
{
cin>>n>>s+1;
bool flag=false;
for(int i=1;i*i<=n;i++) if(n%i==0)
{
if(deal(i)){flag=true;break;};
if(deal(n/i)){flag=true;break;};
}
if(flag) cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#include <bits/stdc++.h>
using namespace std;

const int G = 3;
const int B = 19;
const int N = (1 << B) | 1;
const int IG = 332748118;
const int MOD = 998244353;
typedef long long ll;

inline int add(int a, int b) {
return (a + b >= MOD) ? (a + b - MOD) : (a + b);
}
inline int dec(int a, int b) { return (a - b >= 0) ? (a - b) : (a - b + MOD); }
inline int mul(ll a, int b) { return a * b - a * b / MOD * MOD; }
inline int qpow(int x, ll y) {
int res = 1;
for (; y; y >>= 1, x = mul(x, x))
if (y & 1) res = mul(res, x);
return res;
}

struct Node {
double x, y;
Node() {}
Node(const double &_x, const double &_y) : x(_x), y(_y) {}
Node operator+(const Node &t) { return Node(x + t.x, y + t.y); }
Node operator-(const Node &t) { return Node(x - t.x, y - t.y); }
Node operator*(const Node &t) {
return Node(x * t.x - y * t.y, x * t.y + y * t.x);
}
Node operator*(const double &k) { return Node(x * k, y * k); }
Node operator~() { return Node(x, -y); }
void MTTinit(int t) {
x = t >> 15;
y = t & 32767;
}
};

class MathMod {
public:
int inv(int t) { return qpow(t, MOD - 2); }
};

class Poly : protected MathMod {
public:
Poly() {
for (level = 1; level < B; ++level) {
limit = 1 << level, rev = REV[level];
for (int i = 0; i < limit; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (limit >> 1) : 0);
}
}

private:
int tmp_a[N], tmp_b[N], tmp_c[N], tmp_d[N];

protected:
int limit, level;
int *rev, REV[B][N];

void InitLimit(const int need_len) {
for (limit = 1, level = 0; limit <= need_len; limit <<= 1) ++level;
rev = REV[level];
InitLimitExtra();
}

virtual void InitLimitExtra() = 0;
virtual void Transform() = 0;

public:
virtual void Mul(const int len_a, const int *a, const int len_b,
const int *b, int *c) = 0;

void Inv(const int len, const int *a, int *b) {
if (!len) {
b[0] = inv(a[0]);
return;
}
Inv(len >> 1, a, b);
Mul(len, b, len, b, tmp_a);
Mul(len, tmp_a, len, a, tmp_a);

for (int i = 0; i <= len; ++i)
b[i] = add(add(b[i], b[i]), MOD - tmp_a[i]);

for (int i = len + 1; i < limit; ++i) b[i] = 0;
for (int i = 0; i < limit; ++i) tmp_a[i] = 0;
}

void Deriv(const int len, const int *a, int *b) {
for (int i = 0; i < len; ++i) b[i] = mul(a[i + 1], i + 1);
b[len] = 0;
}

void Integral(const int len, const int *a, int *b) {
for (int i = len; i > 0; --i) b[i] = mul(a[i - 1], inv(i));
b[0] = 0;
}

void Ln(const int len, const int *a, int *b) {
Deriv(len, a, b);
Inv(len, a, tmp_b);
Mul(len, b, len, tmp_b, tmp_b);
Integral(len, tmp_b, b);

for (int i = len + 1; i < limit; ++i) b[i] = 0;
for (int i = 0; i < limit; ++i) tmp_b[i] = 0;
}

void Exp(const int len, const int *a, int *b) {
if (!len) {
b[0] = 1;
return;
}
Exp(len >> 1, a, b);
Ln(len, b, tmp_c);
for (int i = 0; i <= len; ++i) tmp_c[i] = add(MOD - tmp_c[i], a[i]);
++tmp_c[0];
Mul(len, tmp_c, len, b, b);

for (int i = len + 1; i < limit; ++i) b[i] = 0;
for (int i = 0; i < limit; ++i) tmp_c[i] = 0;
}

void Sqrt(const int len, const int *a, int *b) {
static int inv2 = inv(2);
if (!len) {
b[0] = 1;
return;
}
Sqrt(len >> 1, a, b);
Inv(len, b, tmp_b);
Mul(len, a, len, tmp_b, tmp_b);
for (int i = 0; i <= len; ++i) b[i] = mul(add(tmp_b[i], b[i]), inv2);

for (int i = len + 1; i < limit; ++i) b[i] = 0;
for (int i = 0; i < limit; ++i) tmp_b[i] = 0;
}

void Power(const int len, const int *a, const char *s, int *b) {
int Len = strlen(s);
int val1 = 0, val2 = 0, val3 = 0;
for (int i = 0; i < Len; ++i) {
val1 = (10LL * val1 + s[i] - '0') % MOD;
val2 = (10LL * val2 + s[i] - '0') % (MOD - 1);
}
for (int i = 0; i < min(6, Len); ++i) val3 = 10 * val3 + s[i] - '0';
if (a[0] == 0 && val3 > len) {
fill(b, b + len + 1, 0);
return;
}

int u, v, shift = 0;
for (int i = 0; i <= len && a[i] == 0; ++i) shift++;
if ((ll)shift * val1 > len) {
fill(b, b + len + 1, 0);
return;
}
u = qpow(a[shift], MOD - 2);
v = qpow(a[shift], val2);
for (int i = 0; i <= len; ++i) b[i] = mul(a[i + shift], u);
Ln(len, b, tmp_d);
b[0] = tmp_d[0];
for (int i = 1; i <= len; ++i) b[i] = mul(tmp_d[i], val1);
Exp(len, b, tmp_d);
shift *= val1;
for (int i = 0; i < shift; ++i) b[i] = 0;
for (int i = shift; i <= len; ++i) b[i] = mul(tmp_d[i - shift], v);
for (int i = 0; i < limit; ++i) tmp_d[i] = 0;
for (int i = len + 1; i < limit; ++i) b[i] = 0;
}
};

class FFT : public Poly {
public:
FFT() {
const double Pi = acos(-1.0);
for (level = 1; level < B; ++level) {
limit = 1 << level, w = W[level];
for (int mid = 1; mid < limit; mid <<= 1) {
w[mid] = Node(1, 0);
for (int i = 1; i < mid; ++i) {
if ((i & 31) == 1)
w[mid + i] = Node(cos(Pi * i / mid), sin(Pi * i / mid));
else
w[mid + i] = w[mid + i - 1] * w[mid + 1];
}
}
}
}

private:
Node tmp_a[N], tmp_b[N], tmp_c[N], tmp_d[N];

protected:
Node *w, W[B][N];

void InitLimitExtra() { w = W[level]; }
void Transform() {}
void Transform(Node *val, int type) {
if (type == 1) reverse(val + 1, val + limit);
for (int i = 0; i < limit; ++i)
if (i < rev[i]) swap(val[i], val[rev[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
int R = mid << 1;
for (int i = 0; i < limit; i += R)
for (int j = 0; j < mid; ++j) {
Node v = w[mid + j] * val[i + mid + j];
val[i + mid + j] = val[i + j] - v;
val[i + j] = val[i + j] + v;
}
}
}

public:
void Mul(const int len_a, const int *a, const int len_b, const int *b,
int *c) {
InitLimit(len_a + len_b);
for (int i = 0; i <= len_a; ++i) tmp_a[i].MTTinit(a[i]);
for (int i = 0; i <= len_b; ++i) tmp_b[i].MTTinit(b[i]);
Transform(tmp_a, 1), Transform(tmp_b, 1);
for (int i = 0; i < limit; ++i) {
Node ft = ~tmp_a[i ? (limit - i) : 0];
Node f0 = (tmp_a[i] - ft) * Node(0, -0.5);
Node f1 = (tmp_a[i] + ft) * 0.5;
Node gt = ~tmp_b[i ? (limit - i) : 0];
Node g0 = (tmp_b[i] - gt) * Node(0, -0.5);
Node g1 = (tmp_b[i] + gt) * 0.5;
tmp_c[i] = f1 * g1,
tmp_d[i] = f0 * g1 + f1 * g0 + f0 * g0 * Node(0, 1);
}
Transform(tmp_c, -1), Transform(tmp_d, -1);
for (int i = 0; i <= len_a + len_b; ++i) {
ll v1 = (ll)(tmp_c[i].x / limit + 0.5) % MOD;
ll v2 = (ll)(tmp_d[i].x / limit + 0.5) % MOD;
ll v3 = (ll)(tmp_d[i].y / limit + 0.5) % MOD;
c[i] = ((v1 << 30) + (v2 << 15) + v3) % MOD;
}

for (int i = 0; i < limit; ++i)
tmp_a[i] = tmp_b[i] = tmp_c[i] = tmp_d[i] = Node(0, 0);
}
};

class NTT : public Poly {
private:
int tmp_a[N], tmp_b[N];

public:
void Mul(const int len_a, const int *a, const int len_b, const int *b,
int *c) {
InitLimit(len_a + len_b);
for (int i = 0; i <= len_a; ++i) tmp_a[i] = a[i];
for (int i = 0; i <= len_b; ++i) tmp_b[i] = b[i];
Transform(tmp_a, 1), Transform(tmp_b, 1);
for (int i = 0; i < limit; ++i) c[i] = mul(tmp_a[i], tmp_b[i]);
Transform(c, -1);
int INV = inv(limit);
for (int i = 0; i <= len_a + len_b; ++i) c[i] = mul(c[i], INV);
for (int i = len_a + len_b + 1; i < limit; ++i) c[i] = 0;
for (int i = 0; i < limit; ++i) tmp_a[i] = tmp_b[i] = 0;
}

protected:
void InitLimitExtra() {}
void Transform() {}
void Transform(int *val, int type) {
for (int i = 0; i < limit; ++i)
if (i < rev[i]) swap(val[i], val[rev[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
int wn = qpow(type == 1 ? G : IG, (MOD - 1) / (mid << 1));
for (int j = 0; j < limit; j += (mid << 1)) {
int w = 1;
for (int k = 0; k < mid; k++, w = mul(w, wn)) {
int x = val[j + k], y = mul(w, val[j + k + mid]);
val[j + k] = add(x, y);
val[j + k + mid] = dec(x, y);
}
}
}
}
};

组合数取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int f[maxn],g[maxn],r[maxn];

void init()
{
f[0]=g[0]=f[1]=g[1]=r[1]=1;
for(int i=2;i<maxn;i++)
{
f[i]=(ll)f[i-1]*i%mod;
r[i]=(ll)(mod-mod/i)*r[mod%i]%mod;
g[i]=(ll)g[i-1]*r[i]%mod;
}
}

inline int nCm(int n,int m)
{
if(m<0 || m>n) return 0;
return (ll)f[n]*g[m]%mod*g[n-m]%mod;
}

原根

「洛谷」P6091

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=1e6+5;
#define ll long long

int phi[maxn];
bool vis[maxn];
int prime[maxn],cnt;

vector<int>factor;
vector<int>ans;

void getphi(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) phi[i]=i-1,prime[++cnt]=i;
for(int j=1;j<=cnt && i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}

inline int quickpow(ll a,int b,int mod)
{
int ans=1;
for(;b;b>>=1,a=(a*a)%mod) if(b&1) ans=(a*ans)%mod;
return ans;
}

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

inline void divide(int x)
{
for(int i=2;i*i<=x;i++) if(x%i==0)
{
factor.push_back(i);
while(x%i==0) x/=i;
}
if(x>1) factor.push_back(x);
}

bool exist(int n)
{
if(n==2 || n==4) return true;
if(n%2==0) n/=2;
for(int i=2;prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
while(n%prime[i]==0) n/=prime[i];
return n==1;
}
}
return false;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

getphi(1e6);
int T;cin>>T;
while(T--)
{
int n,d;
cin>>n>>d;
if(!exist(n))
{
cout<<0<<'\n'<<'\n';
continue;
}
factor.clear();
ans.clear();
divide(phi[n]);
int g;
for(int i=1;;i++)
{
bool flag=true;
if(gcd(i,n)!=1) continue;
for(int j=0;j<factor.size();j++)
{
if(quickpow(i,phi[n]/factor[j],n)==1)
{
flag=false;
break;
}
}
if(flag){g=i;break;}
}
ll res=1;
for(int i=1;ans.size()<phi[phi[n]];i++)
{
res=res*g%n;
if(gcd(phi[n],i)==1) ans.push_back(res);
}
sort(ans.begin(),ans.end());
cout<<phi[phi[n]]<<'\n';
for(int i=d-1;i<phi[phi[n]]/d*d && i<ans.size();i+=d) cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}

FFT

「洛谷」P3803

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
#include <bits/stdc++.h>
using namespace std;

const double pi=acos(-1.0);
const int maxn=1e7+5;

struct comp
{
double x,y;
comp(double x_=0,double y_=0){x=x_,y=y_;}
comp operator + (comp b){return comp(x+b.x,y+b.y);}
comp operator - (comp b){return comp(x-b.x,y-b.y);}
comp operator * (comp b){return comp(x*b.x-y*b.y,x*b.y+y*b.x);}
}a[maxn],b[maxn];

int limit=1;
int l,r[maxn];

void FFT(comp *A,int type)
{
for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
comp wn(cos(pi/mid),type*sin(pi/mid));
for(int R=mid<<1,j=0;j<limit;j+=R)
{
comp w(1,0);
for(int k=0;k<mid;k++,w=w*wn)
{
comp x=A[j+k],y=w*A[j+mid+k];
A[j+k]=x+y;
A[j+mid+k]=x-y;
}
}
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;cin>>n>>m;
for(int i=0;i<=n;i++) cin>>a[i].x;
for(int i=0;i<=m;i++) cin>>b[i].x;
while(limit<=n+m) limit<<=1,l++;
for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
FFT(a,1);FFT(b,1);
for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<=m+n;i++) cout<<(int)(a[i].x/limit+0.5)<<' ';
return 0;
}

NTT

「洛谷」P3803

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e7+5;
#define ll long long
const int p=998244353;
const int g=3;
const int ig=332748118;

inline int quickpow(ll a,ll b)
{
int ans=1;
for(;b;b>>=1,a=(a*a)%p) if(b&1) ans=(a*ans)%p;
return ans;
}

int limit=1;
int l,r[maxn];
ll a[maxn],b[maxn];

void NTT(ll *A,int type)
{
for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
ll wn=quickpow(type==1?g:ig,(p-1)/(mid<<1));
for(int j=0;j<limit;j+=(mid<<1))
{
ll w=1;
for(int k=0;k<mid;k++,w=(w*wn)%p)
{
int x=A[j+k],y=w*A[j+k+mid]%p;
A[j+k]=(x+y)%p;
A[j+k+mid]=(x-y+p)%p;
}
}
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++) cin>>a[i];
for(int i=0;i<=m;i++) cin>>b[i];
while(limit<=n+m) limit<<=1,l++;
for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
NTT(a,1);NTT(b,1);
for(int i=0;i<limit;i++) a[i]=(a[i]*b[i])%p;
NTT(a,-1);
int inv=quickpow(limit,p-2);
for(int i=0;i<=m+n;i++) cout<<(a[i]*inv)%p<<' ';
return 0;
}

FWT

「洛谷」P4717

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1<<17|1;
const int mod=998244353;
const int inv2=499122177;
#define ll long long

struct FWT
{
int len;

inline int add(int a,int b)
{
a=(a+b)%mod;
return a>=0?a:a+mod;
}

void FWTOR(int *a,int op=1)
{
for(int i=2,ii=1;i<=len;i<<=1,ii<<=1)
for(int j=0;j<len;j+=i)
for(int k=0;k<ii;k++)
a[j+k+ii]=add(a[j+k+ii],op*a[j+k]);

}

void FWTAND(int *a,int op=1)
{
for(int i=2,ii=1;i<=len;i<<=1,ii<<=1)
for(int j=0;j<len;j+=i)
for(int k=0;k<ii;k++)
a[j+k]=add(a[j+k],op*a[j+k+ii]);
}

void FWTXOR(int *a,int op=1)
{
for(int i=2,ii=1;i<=len;i<<=1,ii<<=1)
for(int j=0;j<len;j+=i)
for(int k=0;k<ii;k++)
{
int t=a[j+k];
a[j+k]=(ll)op*add(t,a[j+k+ii])%mod;
a[j+k+ii]=(ll)op*add(t,mod-a[j+k+ii])%mod;
}
}
}T;

int A[maxn],B[maxn];
int a[maxn],b[maxn];

void init(int n)
{
for(int i=0;i<n;i++) a[i]=A[i],b[i]=B[i];
}

void deal(int n)
{
for(int i=0;i<n;i++) a[i]=((ll)a[i]*b[i])%mod;
}

void print(int n)
{
for(int i=0;i<n;i++) cout<<a[i]<<' ';
cout<<'\n';
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;cin>>n;
n=1<<n;
T.len=n;
for(int i=0;i<n;i++) cin>>A[i];
for(int i=0;i<n;i++) cin>>B[i];
init(n),T.FWTOR(a),T.FWTOR(b),deal(n),T.FWTOR(a,-1),print(n);
init(n),T.FWTAND(a),T.FWTAND(b),deal(n),T.FWTAND(a,-1),print(n);
init(n),T.FWTXOR(a),T.FWTXOR(b),deal(n),T.FWTXOR(a,inv2),print(n);
return 0;
}

EXCRT

「洛谷」P4777

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
#define ll long long

ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}

ll qmul(ll a,ll b,ll p)
{
ll res=0;
for(;b;b>>=1,a=(a+a)%p) if(b&1) res=(res+a)%p;
return res;
}

ll a[maxn],b[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;cin>>n;
for(int i=1;i<=n;i++) cin>>b[i]>>a[i];

ll x=a[1],m=b[1];
for(int i=2;i<=n;i++)
{
ll x0=0,y0=0,c=((a[i]-x)%b[i]+b[i])%b[i];
ll d=exgcd(m,b[i],x0,y0);
ll D=b[i]/d;
x0=qmul(x0,c/d,D);
x=x+x0*m;
m=D*m;
x=(x%m+m)%m;
}
cout<<x;
return 0;
}

扩展BSGS

「洛谷」P4195

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long

unordered_map<int,int>vis;

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

int EXBSGS(int a,int b,int p)
{
a%=p,b%=p;
if(b==1) return 0;
if(!a && !b) return 1;
if(!a) return -1;
if(!b)
{
int res=0,d=0;
while((d=gcd(a,p))!=1)
{
res++;p/=d;
if(p==1) return res;
}
return -1;
}

int res=0,A=a,B=b,P=p,C=1,d=0;
while((d=gcd(A,P))!=1)
{
if(B%d) return -1;
P/=d,B/=d;
C=(ll)C*(A/d)%P;
res++;
if(C==B) return res;
}

vis.clear();
int f=1,t=sqrt(P)+1;
for(int i=0;i<t;i++)
{
vis[(ll)f*B%P]=i;
f=(ll)f*A%P;
}
int tf=f;
f=(ll)f*C%P;
for(int i=1;i<=t;i++)
{
if(vis.find(f)!=vis.end()) return res+i*t-vis[f];
f=(ll)f*tf%P;
}
return -1;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int a,p,b;
while(cin>>a>>p>>b && a && p &&b)
{
int ans=EXBSGS(a,b,p);
if(ans!=-1) cout<<ans<<'\n';
else cout<<"No Solution\n";
}
return 0;
}

Min25筛

「洛谷」P5325

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
const int mod=1e9+7;
const int inv3=333333336;
#define ll long long

int cnt;
bool vis[maxn];
ll pri[maxn],sp1[maxn],sp2[maxn];

void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
pri[++cnt]=i;
sp1[cnt]=(sp1[cnt-1]+i)%mod;
sp2[cnt]=(sp2[cnt-1]+(ll)i*i)%mod;
}
for(int j=1;j<=cnt && (ll)i*pri[j]<=n;j++)
{
vis[i*pri[j]]=true;
if(i%pri[j]==0) break;
}
}
}

ll tot,sqr,n;
ll w[maxn],g1[maxn],g2[maxn];
ll ind1[maxn],ind2[maxn];

ll S(ll x,int y)
{
if(pri[y]>=x) return 0;
ll k=x<=sqr?ind1[x]:ind2[n/x];
ll ans=(g2[k]-g1[k]+mod-(sp2[y]-sp1[y])+mod)%mod;
for(int i=y+1;i<=cnt && (ll)pri[i]*pri[i]<=x;i++)
{
ll pe=pri[i];
for(int e=1;pe<=x;e++,pe=pe*pri[i])
{
ll xx=pe%mod;
ans=(ans+xx*(xx-1)%mod*(S(x/pe,i)+(e!=1)))%mod;
}
}
return ans;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>n;
sqr=sqrt(n);
init(sqr);

for(ll l=1,r=0;l<=n;l=r+1)
{
r=n/(n/l);
w[++tot]=n/l;
g1[tot]=w[tot]%mod;
g2[tot]=g1[tot]*(g1[tot]+1)/2%mod*(g1[tot]*2+1)%mod*inv3%mod;
g2[tot]--;
g1[tot]=g1[tot]*(g1[tot]+1)/2%mod-1;
if(n/l<=sqr) ind1[n/l]=tot;
else ind2[n/(n/l)]=tot;
}
for(int i=1;i<=cnt;i++) for(int j=1;j<=tot && (ll)pri[i]*pri[i]<=w[j];j++)
{
ll k=w[j]/pri[i]<=sqr?ind1[w[j]/pri[i]]:ind2[n/(w[j]/pri[i])];
g1[j]-=pri[i]*(g1[k]-sp1[i-1]+mod)%mod;
g2[j]-=pri[i]*pri[i]%mod*(g2[k]-sp2[i-1]+mod)%mod;
g1[j]%=mod,g2[j]%=mod;
if(g1[j]<0) g1[j]+=mod;
if(g2[j]<0) g2[j]+=mod;
}
cout<<(S(n,0)+1)%mod;
return 0;
}

杜教筛

「洛谷」P4213

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e6+5;
#define ll long long

bool vis[maxn];
int pri[maxn],mu[maxn],sum[maxn],phi[maxn];
ll s[maxn];

void init()
{
int cnt=0;mu[1]=1;phi[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) pri[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=cnt && (ll)i*pri[j]<maxn;j++)
{
vis[i*pri[j]]=true;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
mu[i*pri[j]]=-mu[i];
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
for(int i=1;i<maxn;i++)
{
sum[i]=sum[i-1]+mu[i];
s[i]=s[i-1]+phi[i];
}
}

unordered_map<ll,ll>Sum;

ll summu(ll n)
{
if(n<maxn) return sum[n];
if(Sum.find(n)!=Sum.end()) return Sum[n];
ll res=1;
for(ll l=2,r=0;l<=n;l=r+1)
{
r=n/(n/l);
res-=summu(n/l)*(r-l+1);
}
return Sum[n]=res;
}

unordered_map<ll,ll>S;

ll sumphi(ll n)
{
if(n<maxn) return s[n];
if(S.find(n)!=S.end()) return S[n];
ll res=n*(n+1)/2;
for(ll l=2,r=0;l<=n;l=r+1)
{
r=n/(n/l);
res-=sumphi(n/l)*(r-l+1);
}
return S[n]=res;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

init();
int T;cin>>T;
while(T--)
{
ll n;cin>>n;
cout<<sumphi(n)<<' '<<summu(n)<<'\n';
}
return 0;
}

二次剩余

「洛谷」P5491

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll w;

struct Num
{
ll x,y,p;
Num operator * (const Num &B) const
{
Num C={0,0,p};
C.x=((x*B.x%p+y*B.y%p*w%p)%p+p)%p;
C.y=((x*B.y%p+y*B.x%p)%p+p)%p;
return C;
}
};

ll qpowr(ll a,ll b,ll p)
{
ll res=1;
for(;b;b>>=1,a=(a*a)%p) if(b&1) res=(res*a)%p;
return res;
}

ll qpowi(Num a,ll b,ll p)
{
Num res={1,0,p};
for(;b;b>>=1,a=a*a) if(b&1) res=res*a;
return res.x;
}

ll solve(ll n,ll p)
{
n%=p;
if(p==2) return n;
if(qpowr(n,(p-1)/2,p)==p-1) return -1;

ll a=rand()%p;
while(1)
{
w=((a*a%p-n)%p+p)%p;
if(qpowr(w,(p-1)/2,p)==p-1) break;
a=rand()%p;
}
Num x={a,1,p};
return qpowi(x,(p+1)/2,p);
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

srand(time(0));
int T;cin>>T;
while(T--)
{
ll n,p;
cin>>n>>p;
if(!n){cout<<"0\n";continue;}
ll ans1=solve(n,p),ans2=0;
if(ans1==-1) cout<<"Hola!\n";
else
{
ans2=p-ans1;
if(ans1>ans2) swap(ans1,ans2);
if(ans1==ans2) cout<<ans1<<'\n';
else cout<<ans1<<' '<<ans2<<'\n';
}
}
return 0;
}

Pollard-Rho

「洛谷」P4718

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll maxfactor;

inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

inline ll qpow(ll a,ll b,ll p)
{
ll res=1;
for(;b;b>>=1,a=((__int128)a*a)%p) if(b&1) res=((__int128)res*a)%p;
return res;
}

inline bool MR(ll p)
{
if(p<2) return false;
if(p==2 || p==3) return true;
ll d=p-1,r=0;
while(!(d&1)) r++,d>>=1;
for(ll k=0;k<10;k++)
{
ll a=(ll)rand()%(p-2)+2;
ll x=qpow(a,d,p);
if(x==1 || x==p-1) continue;
for(int i=0;i<r-1;i++)
{
x=(__int128)x*x%p;
if(x==p-1) break;
}
if(x!=p-1) return false;
}
return true;
}

inline ll f(ll x,ll c,ll n){return ((__int128)x*x+c)%n;}

inline ll PR(ll x)
{
ll s=0,t=0,val=1;
ll c=(ll)rand()%(x-1)+1;
int step=0,goal=1;
for(goal=1;;goal<<=1,s=t,val=1)
{
for(step=1;step<=goal;step++)
{
t=f(t,c,x);
val=(__int128)val*abs(t-s)%x;
if(step%127==0)
{
ll d=gcd(val,x);
if(d>1) return d;
}
}
ll d=gcd(val,x);
if(d>1) return d;
}
}

inline void fac(ll x)
{
if(x<=maxfactor || x<2) return;
if(MR(x))
{
maxfactor=max(x,maxfactor);
return;
}
ll p=x;
while(p>=x) p=PR(x);
while(x%p==0) x/=p;
fac(x);fac(p);
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int T;cin>>T;
while(T--)
{
srand((unsigned)time(NULL));
maxfactor=0;
ll n;cin>>n;
fac(n);
if(maxfactor==n) cout<<"Prime\n";
else cout<<maxfactor<<'\n';
}
return 0;
}

计算几何

二维凸包

「洛谷」P2742

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct Node
{
double x,y;
Node operator - (const Node &B) const
{
return (Node){x-B.x,y-B.y};
}
double operator * (const Node &B) const
{
return x*B.y-B.x*y;
}
bool operator < (const Node &B) const
{
if(x==B.x) return y<B.y;
return x<B.x;
}
}A[maxn];

double dis(Node a,Node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool vis[maxn];
int sta[maxn],top;

int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&A[i].x,&A[i].y);
sort(A+1,A+n+1);

sta[++top]=1;
for(int i=2;i<=n;i++)
{
while(top>=2 && (A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0) vis[sta[top--]]=false;
vis[sta[++top]=i]=true;
}
int temp=top;
for(int i=n-1;i>=1;i--) if(!vis[i])
{
while(top>temp && (A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0) vis[sta[top--]]=false;
vis[sta[++top]=i]=true;
}
double ans=0;
for(int i=2;i<=top;i++) ans+=dis(A[sta[i]],A[sta[i-1]]);
printf("%.2lf",ans);
return 0;
}

杂项

CDQ分治

「洛谷」P3810

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;

struct BIT
{
int sum[maxn],n;
#define lowbit(x) (x&-x)

void add(int x,int val)
{
while(x<=n) sum[x]+=val,x+=lowbit(x);
}

int query(int x)
{
int res=0;
while(x) res+=sum[x],x-=lowbit(x);
return res;
}
}T;

struct Node
{
int x,y,z,ans,w;
bool operator != (Node B)
{
return x!=B.x || y!=B.y || z!=B.z;
}
}A[maxn],B[maxn];
int cnt;

bool cmpx(Node a,Node b)
{
if(a.x==b.x) return a.y==b.y?a.z<b.z:a.y<b.y;
return a.x<b.x;
}

bool cmpy(Node a,Node b)
{
if(a.y==b.y) return a.z<b.z;
return a.y<b.y;
}

void deal(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
deal(l,mid);deal(mid+1,r);
sort(A+l,A+mid+1,cmpy);
sort(A+mid+1,A+r+1,cmpy);

int i=mid+1,j=l;
for(;i<=r;i++)
{
while(A[j].y<=A[i].y && j<=mid) T.add(A[j].z,A[j].w),j++;
A[i].ans+=T.query(A[i].z);
}
for(i=l;i<j;i++) T.add(A[i].z,-A[i].w);
}

int ans[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,limit;
cin>>n>>limit;
T.n=limit;
for(int i=1;i<=n;i++) cin>>B[i].x>>B[i].y>>B[i].z;
sort(B+1,B+n+1,cmpx);

int num=0;
for(int i=1;i<=n;i++)
{
num++;
if(B[i]!=B[i+1]) A[++cnt]=B[i],A[cnt].w=num,num=0;
}
deal(1,cnt);
for(int i=1;i<=cnt;i++) ans[A[i].ans+A[i].w-1]+=A[i].w;
for(int i=0;i<n;i++) cout<<ans[i]<<'\n';
return 0;
}