splay
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+500,inf=1e9+7;
int T,ch[N][2],siz[N],val[N],fa[N],ro,tot,cnt[N];
#define ls ch[x][0]
#define rs ch[x][1]
void up(int x)
{
siz[x]=siz[ls]+siz[rs]+cnt[x];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=(ch[y][1]==x),q=(ch[z][1]==y),an=ch[x][k^1];
if(z)ch[z][q]=x;ch[y][k]=an;ch[x][k^1]=y;
if(an)fa[an]=y;fa[x]=z;fa[y]=x;
up(y),up(x);
}
void splay(int x,int g)
{
while(fa[x]!=g)
{
int y=fa[x],z=fa[y];
if(z!=g)rotate(((ch[z][1]==y)^(ch[y][1]==x))?x:y);
rotate(x);
}
if(!g)ro=x;
}
void add(int x)
{
int u=ro,f=0;
while(u&&val[u]!=x)f=u,u=ch[u][x>val[u]];
if(u)++cnt[u];
else
{
u=++tot;
if(f)ch[f][x>val[f]]=u;
fa[u]=f;val[u]=x;
siz[u]=cnt[u]=1;
}
splay(u,0);
}
void find(int x)
{
int u=ro;
if(!u)return;
while(ch[u][x>val[u]]&&x!=val[u])u=ch[u][x>val[u]];
splay(u,0);
}
int rk(int x,int f)
{
find(x);
int u=ro;
if(val[u]>x&& f)return u;
if(val[u]<x&&!f)return u;
u=ch[u][f];
while(ch[u][f^1])u=ch[u][f^1];
return u;
}
void del(int x)
{
int la=rk(x,0),nx=rk(x,1);
splay(la,0),splay(nx,la);
int u=ch[nx][0];
--cnt[u];
if(!cnt[u])ch[nx][0]=0;
else splay(u,0);
}
int get_rk(int x)
{
int u=ro;x++;
if(siz[u]<x)return 0;
while(1)
{
int y=ch[u][0];
if(x>siz[y]+cnt[u])x-=siz[y]+cnt[u],u=ch[u][1];
else
{
if(x>siz[y])return val[u];
u=y;
}
}
}
main()
{
cin>>T;
add(-inf),add(inf);
while(T--)
{
int opt,x;
cin>>opt>>x;
switch(opt)
{
case 1:
add(x);
break;
case 2:
del(x);
break;
case 3:
find(x);
cout<<siz[ch[ro][0]]<<'\n';
break;
case 4:
cout<<get_rk(x)<<'\n';
break;
case 5:
cout<<val[rk(x,0)]<<'\n';
break;
case 6:
cout<<val[rk(x,1)]<<'\n';
break;
}
}
}
fhq
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+500;
class fhq
{
public:
int ch[N][2],v[N],siz[N],rd[N],ro,tot;
#define ls ch[x][0]
#define rs ch[x][1]
inline void up(int x){siz[x]=siz[ls]+siz[rs]+1;}
inline int make_new(int val)
{
int x=++tot;
v[x]=val;
siz[x]=1;
rd[x]=rand();
return x;
}
inline void split(int x,int k,int&a,int&b)
{
if(!x)a=b=0;
else
{
if(v[x]<=k)a=x,split(rs,k,rs,b);
else b=x,split(ls,k,a,ls);
up(x);
}
}
inline int merge(int a,int b)
{
if(!a||!b)return a+b;
if(rd[a]<rd[b])
{
ch[a][1]=merge(ch[a][1],b);
up(a);return a;
}
else
{
ch[b][0]=merge(a,ch[b][0]);
up(b);return b;
}
}
inline void add(int x)
{
int a=0,b=0;
split(ro,x,a,b);int k=make_new(x);
ro=merge(merge(a,k),b);
}
inline void del(int x)
{
int a=0,b=0,c=0;
split(ro,x,a,b);
split(a,x-1,a,c);
c=merge(ch[c][0],ch[c][1]);
ro=merge(merge(a,c),b);
}
inline int rk(int x,int k)
{
while(1)
{
if(siz[ls]+1<k)k-=siz[ls]+1,x=rs;
else
{
if(siz[ls]<k)return x;
x=ls;
}
}
}
inline int the_rk_of(int x)
{
int a=0,b=0,ans;
split(ro,x-1,a,b);
ans=siz[a]+1;
ro=merge(a,b);
return ans;
}
inline int pre(int x)
{
int a=0,b=0,ans;
split(ro,x-1,a,b);
ans=v[rk(a,siz[a])];
ro=merge(a,b);
return ans;
}
inline int las(int x)
{
int a=0,b=0,ans;
split(ro,x,a,b);
ans=v[rk(b,1)];
ro=merge(a,b);
return ans;
}
}A;
int n;
char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa,f;inline int read(){
f=0;while(ch=getc(),ch<'0'||ch>'9')f=(ch=='-');aa=ch-'0';
while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return f?-aa:aa;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
main()
{
srand(time(0));
n=read();
while(n--)
{
int opt=read(),x=read();
if(opt==1)A.add(x);
else if(opt==2)A.del(x);
else if(opt==3)write(A.the_rk_of(x)),puts("");
else if(opt==4)write(A.v[A.rk(A.ro,x)]),puts("");
else if(opt==5)write(A.pre(x)),puts("");
else write(A.las(x)),puts("");
}
}
LCT
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+500;
int v[N],s[N],ch[N][2],rev[N],f[N];
#define ls ch[x][0]
#define rs ch[x][1]
int isroot(int x){return ch[f[x]][0]==x|ch[f[x]][1]==x;}//rev 0,1
void up(int x){s[x]=s[ls]^s[rs]^v[x];}
void reversal(int x){swap(ls,rs);rev[x]^=1;}
void down(int x){if(!rev[x])return;reversal(ls),reversal(rs);rev[x]=0;}
void rotate(int x)
{
int y=f[x],z=f[y],k=(ch[y][1]==x),w=(ch[z][1]==y),an=ch[x][k^1];
if(isroot(y))ch[z][w]=x;ch[x][k^1]=y;ch[y][k]=an;
if(an)f[an]=y;f[y]=x,f[x]=z;
up(y);up(x);
}
int st[N];
void splay(int x)
{
int y=x,z=0;
st[++z]=x;
while(isroot(y))st[++z]=y=f[y];
while(z)down(st[z--]);
while(isroot(x))
{
y=f[x],z=f[y];
if(isroot(y))rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
rotate(x);
}
up(x);
}
void access(int x){for(int y=0;x;x=f[y=x])splay(x),rs=y,up(x);}
void make_root(int x){access(x);splay(x);reversal(x);}
int find_root(int x){access(x);splay(x);while(ls)down(x),x=ls;splay(x);return x;}
void split(int x,int y){make_root(x);access(y);splay(y);}
void link(int x,int y){make_root(x);if(find_root(y)!=x)f[x]=y;}
void cut(int x,int y){make_root(x);if(find_root(y)==x&&f[y]==x&&!ch[y][0])f[y]=rs=0,up(x);}
int n,m;
char cch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;int read(){
while(cch=getc(),cch<'0'||cch>'9');aa=cch-'0';
while(cch=getc(),cch>='0'&&cch<='9')aa=((aa<<3)+(aa<<1))+cch-'0';return aa;
}
main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)v[i]=read();
int opt,x,y;
while(m--)
{
opt=read(),x=read(),y=read();
if(opt==0)split(x,y),printf("%ld\n",s[y]);
if(opt==1)link(x,y);
if(opt==2)cut(x,y);
if(opt==3)make_root(x),v[x]=y;
}
}
##二分图
#include<bits/stdc++.h>
using namespace std;
const int N=505,M=50005;
struct node
{
int v,nxt;
}ed[M];
int girl[N],ans,n,m,e;
int head[N],cnt;
bool used[N];
void add(int u,int v)
{
ed[++cnt].v=v;
ed[cnt].nxt=head[u];
head[u]=cnt;
}
int find(int now)
{
for(int i=head[now];i;i=ed[i].nxt)
{
int v=ed[i].v;
if(!used[v])
{
used[v]=1;
if(!girl[v]||find(girl[v]))
{
girl[v]=now;
return 1;
}
}
}
return 0;
}
main()
{
cin>>n>>m>>e;
for(int i=1;i<=e;i++)
{
int u,v;
cin>>u>>v;
add(u,v);
}
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
if(find(i))
ans++;
}
cout<<ans;
}
最大流
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=7e2+20,M=2e4+500,inf=1e17+7;
struct node
{
int u,v,w,nxt;
}e[M];
int n,m,head[N],cnt=1,st,ed,ans,dep[N],cur[N];
char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;int read(){
while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
void add(int u,int v,int w)
{
e[++cnt]=(node){u,v,w,head[u]};head[u]=cnt;
e[++cnt]=(node){v,u,0,head[v]};head[v]=cnt;
}
void read_add_edge()
{
n=read(),m=read(),st=read(),ed=read();
for(int i=1,u,v,w;i<=m;i++)
{
u=read(),v=read(),w=read();
if(w<=0)continue;
add(u,v,w);
}
}
int bfs()
{
queue<int>q;
for(int i=1;i<=ed;i++)dep[i]=0;
dep[st]=1,q.push(st);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(!dep[v]&&e[i].w>0)
{
q.push(v);
dep[v]=dep[u]+1;
}
}
}
return dep[ed];
}
int dfs(int now,int flow)
{
if(now==ed||!flow)return flow;
int res=0;
for(int &i=cur[now];i;i=e[i].nxt)
{
int v=e[i].v;
if(dep[v]==dep[now]+1&&e[i].w>0)
{
int x=dfs(v,min(flow-res,e[i].w));
if(x>0)
{
e[i].w-=x;
e[i^1].w+=x;
res+=x;
if(flow==res)return res;
}
}
}
return res;
}
void dinic()
{
while(bfs()>0)
{
for(int i=1;i<=ed;i++)
cur[i]=head[i];
ans+=dfs(st,inf);
}
}
void print()
{
cout<<ans;
}
main()
{
read_add_edge();
dinic();
print();
}
费用流
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+500,M=3e5+500,inf=1e9+7;
struct node
{
int u,v,w,c,nxt;
}e[M];
int n,m,head[N],cnt=1,st,ed;
void add(int u,int v,int w,int c)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].c=c;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void read()
{
cin>>n>>m>>st>>ed;
for(int i=1;i<=m;i++)
{
int u,v,w,c;
cin>>u>>v>>w>>c;
add(u,v,w,c);
add(v,u,0,-c);
}
}
int vis[N],mincost,maxflow,dep[N];
int spfa()
{
deque<int>q;
for(int i=1;i<=n;i++)vis[i]=0,dep[i]=inf;
q.push_back(ed);vis[ed]=1;dep[ed]=0;
while(!q.empty())
{
int x=q.front();q.pop_front();vis[x]=0;
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(e[i^1].w>0&&dep[v]>dep[x]-e[i].c)
{
dep[v]=dep[x]-e[i].c;
if(!vis[v])
{
vis[v]=1;
if(!q.empty()&&dep[v]<dep[q.front()])q.push_front(v);
else q.push_back(v);
}
}
}
}
return dep[st]<inf;
}
int dfs(int now,int flow)
{
vis[now]=1;
if(now==ed||flow<=0)return flow;
int res=0;
for(int i=head[now];i;i=e[i].nxt)
{
int v=e[i].v;
if(!vis[v]&&e[i].w&&dep[now]-e[i].c==dep[v])
{
int d=dfs(v,min(flow-res,e[i].w));
if(d<=0)continue;
e[i].w-=d,e[i^1].w+=d;
res+=d,mincost+=d*e[i].c;
if(res==flow)return res;
}
}
return res;
}
void zkw()
{
while(spfa())
{
vis[ed]=1;
while(vis[ed])
{
for(int i=1;i<=n;i++)vis[i]=0;
maxflow+=dfs(st,inf);
}
}
}
void print()
{
cout<<maxflow<<' '<<mincost;
}
main()
{
read();
zkw();
print();
}
NTT
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+500,mod=998244353;
int a[N],b[N],n,m,g=3,fg,len=2,to[N],k=1,inv;
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
void NTT(int*a,int f)
{
for(int i=0;i<len;i++)if(i<to[i])
swap(a[i],a[to[i]]);
for(int i=1;i<len;i<<=1)
{
int gn=ksm(f==1?g:fg,(mod-1)/(i<<1));
for(int j=0;j<len;j+=(i<<1))
{
int g=1;
for(int k=j;k<j+i;k++)
{
int x=a[k],y=g*a[i+k]%mod;
a[k]=(x+y)%mod;
a[i+k]=(x-y+mod)%mod;
g=g*gn%mod;
}
}
}
}
main()
{
fg=ksm(g,mod-2);
cin>>n>>m;
for(int i=0;i<=n;i++)cin>>a[n-i];
for(int i=0;i<=m;i++)cin>>b[m-i];
while(len<=n+m)len<<=1,k++;
for(int i=0;i<len;i++)
to[i]=(to[i>>1]>>1)|((i&1)<<(k-1));
NTT(a,1),NTT(b,1);
for(int i=0;i<len;i++)a[i]=a[i]*b[i]%mod;
NTT(a,0);
inv=ksm(len,mod-2);
for(int i=n+m;i>=0;i--)cout<<(a[i]*inv)%mod<<' ';
}
杜教筛
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=5*1e6+10;
ll n,m,T,p[N],tot,vis[N];
ll mul[N],f[N],sum[N],phi[N];
ll Mul[N],Phi[N];
map<int, ll > spha;
map<int, ll > smul;
inline void phigros(){
mul[1]=1;
phi[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
p[++tot]=i;
mul[i]=-1;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*p[j]<=N;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
mul[i*p[j]]=-mul[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
for(int i=1;i<=N;i++){
Mul[i]=Mul[i-1]+mul[i];
Phi[i]=Phi[i-1]+phi[i];
}
}
inline ll pha(int x){
if(x<=N) return Phi[x];
if(spha[x]) return spha[x];
ll ans=(1ll*x+1)*(1ll*x)/2;
for(ll i=2,j;i<=x;i=j+1){
j=x/(x/i);
ans-=(j-i+1)*pha(x/i);
}
return spha[x]=ans;
}
inline int mu(int x){
if(x<=N) return Mul[x];
if(smul[x]) return smul[x];
ll ans=1;
for(int i=2,j;i<=x;i=j+1){
j=x/(x/i);
ans-=(j-i+1)*mu(x/i);
}
return smul[x]=ans;
}
main(){
scanf("%lld",&T);
phigros();
while(T--){
scanf("%d",&n);
printf("%lld %d\n",pha(n),mu(n));
}
return 0;
}
AC 自动机
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int tree[N][27],book[N],fail[N],tot,n;
string s;
void build_tree(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int a=s[i]-'a';
if(!tree[p][a])
tree[p][a]=++tot;
p=tree[p][a];
}
book[p]++;
}
void get_fail()
{
queue<int>q;
for(int i=0;i<26;i++)
if(tree[0][i])
q.push(tree[0][i]);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(tree[now][i])
{
q.push(tree[now][i]);
fail[tree[now][i]]=tree[fail[now]][i];
}
else
tree[now][i]=tree[fail[now]][i];
}
}
}
void AC(string s)
{
int now=0,ans=0;
for(int i=0;i<s.size();i++)
{
now=tree[now][s[i]-'a'];
for(int j=now;j&&book[j]!=-1;j=fail[j])
{
ans+=book[j];
book[j]=-1;
}
}
cout<<ans;
return;
}
main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
build_tree(s);
}
get_fail();
cin>>s;
AC(s);
}
KMP
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+500;
int nxt[N],l1,l2;
char s[N],c[N];
main()
{
cin>>(c+1)>>(s+1);
l1=strlen(c+1),l2=strlen(s+1);
nxt[1]=0;
for(int i=2,j=0;i<=l2;i++)
{
while(j&&s[j+1]!=s[i])j=nxt[j];
if(s[j+1]==s[i])j++;
nxt[i]=j;
}
for(int i=1,j=0;i<=l1;i++)
{
while(j&&s[j+1]!=c[i])j=nxt[j];
if(s[j+1]==c[i])j++;
if(j==l2)cout<<i-l2+1<<'\n';
}
for(int i=1;i<=strlen(s+1);i++)cout<<nxt[i]<<' ';
}
