本文章可能部分模板来自网上，若无意侵犯了您的权益，请电邮[email protected]，将会及时删除 大概挖点坑，目前还缺少线段树（区间）、树套树、fingertree、退火、爬山，将会于近期补充
数据结构
树状数组
ll query(int x){ll re=0;for(int i=x;i;i-=i&-i)re+=t[i];return re;}
void modify(int x,int val){if(x>m)return;for(int i=x;i<=m;i+=i&-i)t[i]+=val;}
线段树（单点）
#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=1e5+6;
int a[maxn],n,m;ll sum[maxn<<2],add[maxn<<2];
void pushup(int x){sum[x]=sum[lson]+sum[rson];}
void pushdown(int x,int l,int r){
if(!add[x])return;
ll tag=add[x];add[x]=0;int mid=(l+r)>>1;
add[lson]+=tag;add[rson]+=tag;
sum[lson]+=tag*1ll*(mid-l+1);sum[rson]+=tag*1ll*(r-mid);
}
void build(int x,int l,int r){
if(l==r){sum[x]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,int ql,int qr,ll v){
if(ql<=l&&r<=qr){sum[x]+=v*1ll*(r-l+1),add[x]+=v;return;}
int mid=(l+r)>>1;pushdown(x,l,r);
if(ql<=mid)modify(lson,l,mid,ql,qr,v);
if(qr>mid)modify(rson,mid+1,r,ql,qr,v);
pushup(x);
}
inline ll querysum(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[x];
pushdown(x,l,r);
int mid=(l+r)>>1;ll re=0;
if(ql<=mid)re+=querysum(lson,l,mid,ql,qr);
if(qr>mid)re+=querysum(rson,mid+1,r,ql,qr);
return re;
}
int main()
{
n=read(),m=read();
rep(i,1,n)a[i]=read();
build(1,1,n);
rep(i,1,m){
int opt=read(),l=read(),r=read();
if(opt==1){ll k=read();modify(1,1,n,l,r,k);}
else printf("%lld\n",querysum(1,1,n,l,r));
}
return 0;
}
左偏树
#include<iostream>
#include<cstdio>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
inline int read()
{
int f=1,x=0;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;
}
const int maxn=1e6+6;
struct tree{int l,r,w,d;}t[maxn];
int n,m,fa[maxn];
bool die[maxn];
char ch[10];
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
if(x==0||y==0)return x+y;
if(t[x].w>t[y].w||(t[x].w==t[y].w&&x>y))swap(x,y);
t[x].r=merge(t[x].r,y);
if(t[t[x].l].d<t[t[x].r].d)swap(t[x].l,t[x].r);
t[x].d=t[t[x].r].d+1;
return x;
}
int main()
{
n=read();m=read();
rep(i,1,n)t[i].w=read();
t[0].d=-1;rep(i,1,n)fa[i]=i;
rep(i,1,m){
int opt=read();
if(opt==1){
int x=read(),y=read();
if(die[x]||die[y])continue;
int r1=find(x),r2=find(y);
if(r1!=r2){int t=merge(r1,r2);fa[r1]=fa[r2]=t;}
}
if(opt==2){
int x=read();
if(die[x])printf("-1\n");
else{
int r1=find(x);die[r1]=1;
printf("%d\n",t[r1].w);
fa[r1]=merge(t[r1].l,t[r1].r);fa[fa[r1]]=fa[r1];
}
}
}
return 0;
}
非旋转treap
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxn=1e5+6;
struct tree{int l,r,size,w,f;}t[maxn<<1];
int n,len=0,root=0;
inline int getrank(){return (rand()<<16)+rand();}
void change(int x){
if(x==0)return;
t[x].size=t[t[x].l].size+t[t[x].r].size+1;
}
int merge(int x,int y){
if(x==0||y==0)return x+y;
if(t[x].f>t[y].f){
t[x].r=merge(t[x].r,y);change(x);return x;}
else{t[y].l=merge(x,t[y].l);change(y);return y;}
}
void splite(int x,int val,int &new1,int &new2){
if(x==0){new1=0;new2=0;return;}
if(t[x].w<val){
new1=x;splite(t[x].r,val,t[x].r,new2);
}else{new2=x;splite(t[x].l,val,new1,t[x].l);}
change(x);
}
int insert(int now,int want){
if(now==0)return want;
if(t[now].f>t[want].f){
if(t[now].w<t[want].w)t[now].r=insert(t[now].r,want);else t[now].l=insert(t[now].l,want);
change(now);return now;
}
splite(now,t[want].w,t[want].l,t[want].r);change(want);return want;
}
int find(int now,int want){
if(t[t[now].l].size==want-1)return t[now].w;
if(t[t[now].l].size>=want)return find(t[now].l,want);
return find(t[now].r,want-t[t[now].l].size-1);
}
int findleft(int now){while(t[now].l)now=t[now].l;return t[now].w;}
int findright(int now){while(t[now].r)now=t[now].r;return t[now].w;}
int main()
{
srand(1125);
n=read();
mem(t,0);
rep(i,1,n){
int opt=read();
if (opt==1){int x=read();t[++len].f=getrank();t[len].w=x;t[len].size=1;root=insert(root,len);}
else if(opt==2){int x=read(),new1,new2,new3;splite(root,x,new1,new2);splite(new2,x+1,new2,new3);root=merge(merge(new1,t[new2].l),merge(t[new2].r,new3));}
else if(opt==3){int x=read(),new1,new2;splite(root,x,new1,new2);printf("%d\n",t[new1].size+1);root=merge(new1,new2);}
else if(opt==4){int x=read();printf("%d\n",find(root,x));}
else if(opt==5){int x=read(),new1,new2;splite(root,x,new1,new2);printf("%d\n",findright(new1));root=merge(new1,new2);}
else{int x=read(),new1,new2;splite(root,x+1,new1,new2);printf("%d\n",findleft(new2));root=merge(new1,new2);}
}
return 0;
}
splay（翻转）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxn=1e5+6;
int n,m,sz,rt,fa[maxn],c[maxn][2],id[maxn],size[maxn];
bool rev[maxn];
void pushup(int k)
{
int l=c[k][0],r=c[k][1];
size[k]=size[l]+size[r]+1;
}
void pushdown(int k)
{
int l=c[k][0],r=c[k][1];
if(rev[k]){
swap(c[k][0],c[k][1]);
rev[l]^=1;rev[r]^=1;
rev[k]=0;
}
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;
r=l^1;
if(y==k)k=x;
else{
if(c[z][0]==y)c[z][0]=x;
else c[z][1]=x;
}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k)
{
while(x!=k){
int y=fa[x],z=fa[y];
if(y!=k){
if(c[y][0]==x^c[z][0]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int k,int rank)
{
pushdown(k);
int l=c[k][0],r=c[k][1];
if(size[l]+1==rank)return k;
else if(size[l]>=rank)return find(l,rank);
else return find(r,rank-size[l]-1);
}
void rever(int l,int r){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
rev[z]^=1;
}
void build(int l,int r,int f)
{
if(l>r)return;
int now=id[l],last=id[f];
if(l==r){
fa[now]=last;size[now]=1;
if(l<f)c[last][0]=now;
else c[last][1]=now;
return;
}
int mid=(l+r)>>1;now=id[mid];
build(l,mid-1,mid);build(mid+1,r,mid);
fa[now]=last;pushup(mid);
if(mid<f)c[last][0]=now;
else c[last][1]=now;
}
int main()
{
n=read(),m=read();
rep(i,1,n+2)id[i]=++sz;
build(1,n+2,0);rt=(n+3)>>1;
rep(i,1,m){
int l=read(),r=read();
rever(l,r);
}
rep(i,2,n+1)printf("%d ",find(rt,i)-1);
return 0;
}
树链剖分
#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=3e5+6;
struct tree{int l,r,v,lazy;}node[maxn<<1];
struct edge{int to,next;}e[maxn<<2];
int last[maxn],w[maxn],ex[maxn],top[maxn],rank[maxn],size[maxn],dep[maxn],tt[maxn],fa[maxn],cnt;
int mod,n,m,s,tid[maxn],tot;
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;tt[u]++;}
void pushdown(int x){
if(node[x].lazy==0)return;
node[x].v+=node[x].lazy*(node[x].r-node[x].l+1)%mod;
node[lson].lazy+=node[x].lazy;node[rson].lazy+=node[x].lazy;
node[x].lazy=0;
}
void build(int x,int l,int r){
int mid=(l+r)>>1;node[x].l=l,node[x].r=r;
if(l==r)return;
build(lson,l,mid);
build(rson,mid+1,r);
}
void modify(int x,int l,int r,int val){
if(node[x].l>r||node[x].r<l)return;
if(node[x].l>=l&&node[x].r<=r){node[x].lazy+=val;pushdown(x);return;}
modify(lson,l,r,val);
modify(rson,l,r,val);
pushdown(lson);pushdown(rson);
node[x].v=(node[lson].v+node[rson].v)%mod;
}
inline int query(int x,int l,int r){
if(node[x].l>r||node[x].r<l)return 0;
if(node[x].l>=l&&node[x].r<=r)return (node[x].v)%mod;
pushdown(lson);pushdown(rson);
return (query(lson,l,r)+query(rson,l,r))%mod;
}
void dfs(int x,int Fa){
size[x]=1;dep[x]=dep[Fa]+1;fa[x]=Fa;
reg(x){
if(e[i].to==Fa)continue;
dfs(e[i].to,x);
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int head){
int mson=0;
top[x]=head;tid[x]=++tot;rank[tid[x]]=tot;
modify(1,tot,tot,w[x]);
if(tt[x]==1&&x!=s){ex[x]=x;return;}
reg(x)
if(size[e[i].to]<size[x]&&size[e[i].to]>size[mson])mson=e[i].to;
dfs2(mson,head);
ex[x]=ex[mson];
reg(x)
if(size[e[i].to]<size[x]&&e[i].to!=mson){dfs2(e[i].to,e[i].to);ex[x]=ex[e[i].to];}
}
void pmodify(int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(1,tid[top[x]],tid[x],val);
x=fa[top[x]];
}
if(tid[x]>tid[y])swap(x,y);
modify(1,tid[x],tid[y],val);
}
inline int pquery(int x,int y){
int re=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
re=(re+query(1,tid[top[x]],tid[x]))%mod;
x=fa[top[x]];
}
if(tid[x]>tid[y])swap(x,y);
re=(re+query(1,tid[x],tid[y]))%mod;
return re;
}
int main()
{
n=read(),m=read(),s=read(),mod=read();
rep(i,1,n)w[i]=read();
rep(i,1,n-1){
int u=read(),v=read();
insert(u,v);insert(v,u);
}
build(1,1,n);
dfs(s,0);dfs2(s,s);
rep(i,1,m){
int opt=read();
if(opt==1){int x=read(),y=read(),z=read();pmodify(x,y,z);}
if(opt==2){int x=read(),y=read();printf("%d\n",pquery(x,y)%mod);}
if(opt==3){int x=read(),y=read();modify(1,tid[x],tid[ex[x]],y);}
if(opt==4){int x=read();printf("%d\n",query(1,tid[x],tid[ex[x]])%mod);}
}
return 0;
}
LCT
const int maxn=3e5+6;
int n,m,top,c[maxn][2],fa[maxn],v[maxn],s[maxn],que[maxn];
bool rev[maxn];
void update(int x){
int l=c[x][0],r=c[x][1];
s[x]=s[l]^s[r]^v[x];
}
void pushdown(int x){
int l=c[x][0],r=c[x][1];
if(rev[x]){
rev[x]^=1;rev[l]^=1;rev[r]^=1;
swap(c[x][0],c[x][1]);
}
}
bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;r=l^1;
if(!isroot(y)){
if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(y);update(x);
}
void splay(int x){
top=0;que[++top]=x;
for(int i=x;!isroot(i);i=fa[i])que[++top]=fa[i];
dep(i,top,1)pushdown(que[i]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)){
if(c[y][0]==x^c[z][0]==y)rotate(x);else rotate(y);
}
rotate(x);
}
}
void access(int x){
for(int t=0;x;t=x,x=fa[x])splay(x),c[x][1]=t,update(x);
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
int find(int x){
access(x);splay(x);
while(c[x][0])x=c[x][0];
return x;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
if(c[y][0]==x)c[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
int main()
{
n=read(),m=read();
rep(i,1,n)v[i]=read(),s[i]=v[i];
rep(i,1,m){
int opt=read(),x=read(),y=read();
if(opt==0){makeroot(x);access(y);splay(y);printf("%d\n",s[y]);}
if(opt==1){if(find(x)!=find(y))link(x,y);}
if(opt==2){if(find(x)==find(y))cut(x,y);}
if(opt==3){access(x);splay(x);v[x]=y;update(x);}
}
return 0;
}
主席树
const int maxn=1e5+6,maxm=2e6+6;
int n,m,tot,sz,cnt,ind,now,num[maxn],pos[maxn],v[maxn],tmp[maxn],hash[maxn],root[maxn];
int last[maxn],deep[maxn],fa[maxn][17],ls[maxm],rs[maxm],sum[maxm];
struct edge{int to,next;}e[maxm];
void insert(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
inline int find(int x){
int l=1,r=tot,mid;
while(l<=r){
mid=(l+r)>>1;
if(hash[mid]<x)l=mid+1;else r=mid-1;
}
return l;
}
void dfs(int x){
num[++ind]=x;pos[x]=ind;
rep(i,1,16)if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];else break;
reg(x)
if(fa[x][0]!=e[i].to){
deep[e[i].to]=deep[x]+1;
fa[e[i].to][0]=x;
dfs(e[i].to);
}
}
int lca(int x,int y){
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
rep(i,0,16)if((1<<i)&t)x=fa[x][i];
dep(i,16,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if(x==y)return x;else return fa[x][0];
}
void update(int l,int r,int x,int &y,int v){
y=++sz;sum[y]=sum[x]+1;
if(l==r)return;
ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;
if(v<=mid)update(l,mid,ls[x],ls[y],v);else update(mid+1,r,rs[x],rs[y],v);
}
int query(int x,int y,int rank){
int a=x,b=y,c=lca(x,y),d=fa[c][0];
a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
int l=1,r=tot,mid;
while(l<r){
mid=(l+r)>>1;
int t=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if(t>=rank)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
else rank-=t,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
}
return hash[l];
}
数论
Lucas求组合数（包括乘法逆元）
void work()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
rep(i,2,p-1)fac[i]=fac[i-1]*i%p; //阶乘预处理
rep(i,2,p-1)inv[i]=(p-p/i)*inv[p%i]%p;
rep(i,1,p-1)inv[i]=inv[i-1]*inv[i]%p; //逆元预处理
}
ll C(ll n,ll m)
{
if(n<m)return 0; //舍去组合数无意义的情况
if(n<p&&m<p)return fac[n]*inv[m]%p*inv[n-m]%p;
return C(n/p,m/p)*C(n%p,m%p)%p;
}
扩展欧几里得
void exgcd(int a,int b,LL &x,LL &y){
if(b==0){x=1,y=0;return;}
exgcd(b,a%b,x,y);
LL t=x;
x=y,y=t-a/b*y;
}
欧拉函数
void shaker() {
int j;phi[1]=1;
rep(i,2,n){
if(!not_prime[i]){prime[++top]=i;phi[i]=i-1;}
for(j=1;j<=top&&i*prime[j]<=n;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0){phi[prime[j]*i]=phi[i]*prime[j];break;}
phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
}
莫比乌斯函数
mu[1]=1;
rep(i,2,maxn-6){
if(!is_prime[i])prime[++cnt]=i,mu[i]=-1;
rep(j,1,cnt){
if(prime[j]*i>maxn-6)break;
is_prime[i*prime[j]]=1;
if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
else mu[i*prime[j]]=-mu[i];
}
}
FFT
const int maxn=2e5+6;
typedef complex<double> E;
int n,m,L;
char ch[maxn];
int R[maxn],c[maxn];
E a[maxn],b[maxn];
void fft(E *a,int f)
{
rep(i,0,n-1)
if(i<R[i])swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1){
E wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=(i<<1)){
E w(1,0);
for(int k=0;k<i;k++,w*=wn){
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;
a[j+k+i]=x-y;
}
}
}
if(f==-1)rep(i,0,n-1)a[i]/=n;
}
int main()
{
n=read();n--;
scanf("%s",ch);
rep(i,0,n)a[i]=ch[n-i]-'0';
scanf("%s",ch);
rep(i,0,n)b[i]=ch[n-i]-'0';
m=2*n;
for(n=1;n<=m;n<<=1)L++;
rep(i,0,n-1)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
fft(a,1);fft(b,1);
rep(i,0,n)a[i]*=b[i];
fft(a,-1);
rep(i,0,m)c[i]=(int)(a[i].real()+0.1);
rep(i,0,m)
if(c[i]>=10){
c[i+1]+=c[i]/10,c[i]%=10;
if(i==m)m++;
}
dep(i,m,0)printf("%d",c[i]);
return 0;
}
图论
Floyd求最短路
适用于点数较小，可以传递闭包
#define inf 1e9
const int maxn=500;
int Map[maxn][maxn],n,m,S;
void Pre(){
rep(i,1,n)
rep(j,1,n)Map[i][j]=(i==j?0:inf);
}
void Floyd(){
rep(k,1,n)
rep(i,1,n)
rep(j,1,n)
Map[i][j]=min(Map[i][k]+Map[k][j],Map[i][j]);
}
SPFA求最短路
玄学复杂度，O(能用)，偶尔毒瘤出题人卡一卡
注意队列que大小开了4倍，inq[now]要及时清空
#define inf 0x7fffffff
const int maxn=1e4+6,maxm=5e5+6;
struct edge{int to,next,w;}e[maxm<<1];
int n,m,S,dis[maxn],que[maxn<<2],last[maxn],cnt=0;
bool inq[maxn];
void Pre(){rep(i,1,n)dis[i]=inf;dis[S]=0;}
void insert(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
}
void SPFA(){
int head=0,tail=1;
que[head]=S;dis[S]=0;inq[S]=1;
while(head<tail){
int now=que[head++];
reg(now)
if(dis[e[i].to]>dis[now]+e[i].w){
dis[e[i].to]=dis[now]+e[i].w;
if(!inq[e[i].to])inq[e[i].to]=1,que[tail++]=e[i].to;
}
inq[now]=0;
}
}
Kruscal求最小生成树
注意要置fa数组初始化为自己
const int maxn=5e3+6,maxm=2e5+6;
int n,m,fa[maxn],cnt;ll ans=0;
struct Kedge{int u,v,w;}Ke[maxm<<1];
void Pre(){rep(i,1,n)fa[i]=i;}
inline int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
inline bool Kcmp(Kedge a,Kedge b){return a.w<b.w;}
void Kruscal(){
sort(Ke+1,Ke+1+m,Kcmp);
rep(i,1,m){
int root1=findfa(Ke[i].u),root2=findfa(Ke[i].v);
if(root1!=root2)fa[root1]=root2,cnt++,ans+=Ke[i].w;
if(cnt==n-1)break;
}
}
tarjan缩点重构图
const int maxn=2006;
int n,cnt=0,scc,top=0,tim,lim,ans=0;
int head[maxn],h[maxn],r[maxn],dfn[maxn],low[maxn],que[maxn],inque[maxn];
int belong[maxn],hav[maxn],mark[maxn][maxn];
char ch[maxn];
struct edge{int to,next;}e[4000006],ed[4000006];
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define v e[i].to
#define newreg(x) for(int i=h[x];i;i=ed[i].next)
#define newv ed[i].to
void tarjan(int x)
{
int now=0;
dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;
reg(x)
if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}
else if(inque[v])low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=que[top--];
inque[now]=0;belong[now]=scc;hav[scc]++;
}
}
}
void rebuild()
{
cnt=0;
rep(k,1,n)
reg(k)
if(belong[k]!=belong[v])ed[++cnt]=(edge){belong[k],h[belong[v]]},h[belong[v]]=cnt,r[belong[k]]++;
}
匈牙利算法求二分图匹配
const int maxn=1506;
int match[maxn][maxn],use[maxn],result[maxn],n,m,ans=0;
bool dfs(int now)
{
rep(i,0,n-1)
if(match[now][i]&&!use[i]){
use[i]=true;
if(!result[i]||dfs(result[i])){
result[i]=now;
return true;
}
}
return false;
}
int main()
{
n=read(),m=read();
rep(i,1,m){
int x=read(),y=read();
match[i][x]=match[i][y]=1;
}
rep(i,1,m){
mem(use,0);
if(dfs(i))ans++;else break;
}
cout<<ans<<endl;
return 0;
}
最大流
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ll long long
#define mem(x,num) memset(x,num,sizeof(x))
#define inf 1844387848
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxn=1e5+6,maxq=1e6+6;
struct edge{ll to,from,v,t,next;}e[maxn<<1];
ll n,m,k,cnt=1,ans,s,t,last[maxn],que[maxq],h[maxq];
bool bfs()
{
ll head=0,tail=0,now;
mem(h,-1);que[0]=s,h[s]=0;
while(head<=tail){
now=que[head++];
reg(now)
if(e[i].v&&h[e[i].to]==-1){h[e[i].to]=h[now]+1;que[++tail]=e[i].to;}
}
if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int f)
{
if(x==t)return f;
ll w,used=0;
reg(x)
if(e[i].v&&h[e[i].to]==h[x]+1){
w=f-used;w=dfs(e[i].to,min(w,e[i].v));
e[i].v-=w;e[i^1].v+=w;
used+=w;if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans+=dfs(s,inf);}
int main()
{
n=read(),m=read(),s=read(),t=read();
rep(i,1,m){
ll u=read(),v=read(),w=read();
e[++cnt]=(edge){v,u,w,w,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,v,0,-w,last[v]};last[v]=cnt;
}
dinic();
cout<<ans<<endl;
return 0;
}
zkw费用流
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define inf 1000000000
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxm=1e6+6;
int S,T,ans,n,m,k,cnt=1,que[maxm],d[maxm],last[maxm];
bool inq[maxm];
struct edge{int to,next,v,c;}e[maxm<<2];
void insert(int u,int v,int w,int c){
e[++cnt]=(edge){v,last[u],w,c};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0,-c};last[v]=cnt;
}
bool spfa(int S,int T)
{
mem(inq,0);
int head=0,tail=1,now;
rep(i,0,n)d[i]=inf;
que[0]=T;d[T]=0;inq[T]=1;
while(head<tail){
now=que[head++];
reg(now)
if(e[i^1].v&&d[now]-e[i].c<d[e[i].to]){
d[e[i].to]=d[now]-e[i].c;
if(!inq[e[i].to])inq[e[i].to]=1,que[tail++]=e[i].to;
}
inq[now]=0;
}
if(d[S]!=inf)return 1;else return 0;
}
int dfs(int x,int f)
{
if(x==T)return f;
int used=0,w;inq[x]=1;
reg(x)
if(!inq[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to]){
w=dfs(e[i].to,min(e[i].v,f-used));
if(w)ans+=w*e[i].c,e[i].v-=w,e[i^1].v+=w,used+=w;
if(used==f)return f;
}
return used;
}
void zkw()
{
int flow=0;
while(spfa(S,T)){
inq[T]=1;
while(inq[T]){mem(inq,0);flow+=dfs(S,inf);}
}
cout<<flow<<' '<<ans<<endl;
}
int main()
{
n=read(),m=read(),S=read(),T=read();
rep(i,1,m){
int u=read(),v=read(),w=read(),c=read();
insert(u,v,w,c);
}
zkw();
return 0;
}
字符串
最小表示法
const int maxn=1e6+6;
int n,a[maxn],pos;
int find(){
int i=1,j=2,k;
while(i<=n&&j<=n){
k=1;while(k<=n&&a[i+k]==a[j+k])k++;
if(k==n+1)return i;
if(a[i+k]>a[j+k])i+=k;else j+=k;
if(i==j)j++;
}
return min(i,j);
}
int main()
{
n=read();
rep(i,1,n)a[i+n]=a[i]=read();
pos=find();
rep(i,1,n-1)printf("%d ",a[i+pos]);printf("%d\n",a[n+pos-1]);
return 0;
}
KMP
n=read();
scanf("%s",st+1);
int j=0;
rep(i,2,n){
while(st[j+1]!=st[i]&&j)j=fail[j];
if(st[j+1]==st[i])j++;
fail[i]=j;
}
Manacher
void manacher(){
int Max=0,id;
rep(i,1,n){
if(Max>=i)p[i]=min(Max-i,p[2*id-i]);else p[i]=0;
while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++;
if(p[i]+i>Max)Max=p[i]+i,id=i;
}
}
字典树
注意insert建字典树的传参，clear不能用memset，strlen不能写在循环内
const int maxn=3e5+6;
char a[10006][36];
int son[maxn],trie[maxn][27],n,id;
void insert(char st[]){
int k,now=0,len=strlen(st+1);
rep(i,1,len){
k=st[i]-'a';
if(!trie[now][k])trie[now][k]=++id;
now=trie[now][k];
son[now]++;
}
}
void ask(char st[]){
int k,now=0,len=strlen(st+1);
rep(i,1,len){
if(son[now]==1)break;
k=st[i]-'a';
printf("%c",st[i]);
now=trie[now][k];
}
}
AC自动机
注意insert建字典树的传参，clear不能用memset，strlen不能写在循环内
const int maxn=5e5+6;
char st[56],m[1000006];
int T,n,id,ans,trie[maxn][27],que[maxn],point[maxn],danger[maxn];
bool mark[maxn];
void insert(char st[]){
int now=1,len=strlen(st+1),k;
rep(i,1,len){
k=st[i]-'a'+1;
if(!trie[now][k])trie[now][k]=++id;
now=trie[now][k];
}
danger[now]++;
}
void acmach(){
int head=0,tail=1,now;
que[0]=1;point[1]=0;
while(head<tail){
now=que[head++];
rep(i,1,26){
if(!trie[now][i])continue;
int k=point[now];while(!trie[k][i])k=point[k];
point[trie[now][i]]=trie[k][i];que[tail++]=trie[now][i];
}
}
}
void solve(){
int now=1,len=strlen(m+1);
rep(i,1,len){
mark[now]=1;
int k=m[i]-'a'+1;
while(!trie[now][k])now=point[now];
now=trie[now][k];
if(!mark[now])
for(int j=now;j;j=point[j])ans+=danger[j],danger[j]=0;
}
printf("%d\n",ans);
}
void clear(){
rep(i,1,id){
point[i]=danger[i]=mark[i]=0;
rep(j,1,26)trie[i][j]=0;
}
}
后缀数组
注意work内循环1->30范围可能需要更改
const int maxn=2e5+6;
int len,a[maxn],h[maxn],v[maxn],sa[2][maxn],rank[2][maxn],p,q,k;
char st[maxn];
void Pre(){
len=strlen(st+1);
rep(i,1,len)a[i]=st[i]-'a'+1;
}
void calsa(int sa[maxn],int rank[maxn],int SA[maxn],int Rank[maxn]){
rep(i,1,len)v[rank[sa[i]]]=i;
dep(i,len,1)
if(sa[i]>k)SA[v[rank[sa[i]-k]]--]=sa[i]-k;
rep(i,len-k+1,len)SA[v[rank[i]]--]=i;
rep(i,1,len)Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i]]!=rank[SA[i-1]]||rank[SA[i]+k]!=rank[SA[i-1]+k]);
}
void work(){
p=0,q=1,k=1;
rep(i,1,len)v[a[i]]++;
rep(i,1,30)v[i]+=v[i-1];
rep(i,1,len)sa[p][v[a[i]]--]=i;
rep(i,1,len)rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
while(k<len){
calsa(sa[p],rank[p],sa[q],rank[q]);
swap(p,q);k<<=1;
}
}
void geth(){
k=0;
rep(i,1,len)
if(rank[p][i]==1)h[rank[p][i]]=0;
else{
int j=sa[p][rank[p][i]-1];
while(a[i+k]==a[j+k])k++;
h[rank[p][i]]=k;if(k>0)k--;
}
}
int main()
{
scanf("%s",st+1);
Pre();
work();
geth();
rep(i,1,len)printf("%d ",sa[p][i]);
printf("\n");
rep(i,1,len)printf("%d ",h[i]);
return 0;
}
计算几何
凸包
int n,top;double ans;
const int maxn=5006;
struct P{int x,y;}p[maxn],s[maxn];
inline P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline ll operator*(P a,P b){return a.x*b.y-a.y*b.x;}
inline ll dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline bool operator<(P a,P b){
ll t=(a-p[1])*(b-p[1]);
if(t==0)return dis(p[1],a)<dis(p[1],b);else return t>0;
}
void graham(){
int t=1;
rep(i,2,n)
if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x))t=i;//找纵坐标最小的点
swap(p[1],p[t]);
sort(p+2,p+n+1);//将剩下的点排序
s[++top]=p[1];s[++top]=p[2];
rep(i,3,n){
while((s[top]-s[top-1])*(p[i]-s[top-1])<=0)top--;
s[++top]=p[i];
}
s[top+1]=p[1];
rep(i,1,top)ans+=sqrt(dis(s[i],s[i+1]));
}
旋转卡壳
const int maxn=2e3+6;
int n,top;
struct P{double x,y;}p[maxn],s[maxn];
inline P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
inline double dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline bool operator<(P a,P b){
double t=(a-p[1])*(b-p[1]);
if(t==0)return dis(a,p[1])<dis(b,p[1]);else return t<0;
}
void graham(){
int t=1;
rep(i,2,n)
if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x))t=i;
swap(p[1],p[t]);sort(p+2,p+n+1);
s[++top]=p[1];s[++top]=p[2];
rep(i,3,n){
while(top>1&&((p[i]-s[top-1])*(s[top]-s[top-1]))<=0)top--;
s[++top]=p[i];
}
s[top+1]=p[1];
}
inline double RC(){
double ans=0;int a,b;
rep(i,1,top){
a=i%top+1,b=(i+2)%top+1;
rep(j,i+2,top){
while(a%top+1!=j&&(s[j]-s[i])*(s[a+1]-s[i])>(s[j]-s[i])*(s[a]-s[i]))a=a%top+1;
while(b%top+1!=i&&(s[b+1]-s[i])*(s[j]-s[i])>(s[b]-s[i])*(s[j]-s[i]))b=b%top+1;
ans=max((s[j]-s[i])*(s[a]-s[i])+(s[b]-s[i])*(s[j]-s[i]),ans);
}
}
return ans;
}
半平面交
const int maxn=1e5+6;
int n,top,ans[maxn];
struct node{
int p,v,id;
friend double Inter(node a,node b){return (double)(a.p-b.p)/(b.v-a.v);}
friend bool operator<(node a,node b){return a.v!=b.v?a.v<b.v:a.p<b.p;}
}c[maxn],que[maxn];
inline bool jud(node a,node b,node t){return Inter(a,b)>Inter(a,t);}
~~~
que[++top]=c[1];ans[1]=c[1].id;
rep(i,2,n){
while(top>=1&&(Inter(que[top],c[i])<-eps))top--;
while(top>=2&&jud(que[top-1],que[top],c[i]))top--;
que[++top]=c[i],ans[top]=c[i].id;
}
特殊
IDA* 搜索
以洛谷P2324 [SCOI2005]骑士精神为例
注意先写搜索出口和状态回溯
const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
const int Std[5][5]=\{\{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0\}\}\;
bool flag=0;int T,Map[5][5],x,y,f;
char ch;
inline bool eva(int g){
int s=0;
rep(i,0,4)
rep(j,0,4)
if(Map[i][j]!=Std[i][j]){s++;if(s+g>f)return 0;}//预估函数值s
return 1;
}
void idsearch(int g,int x,int y){
if(g==f){if(check())flag=1;return;}//判断是否符合条件
if(flag==1)return;
rep(i,0,7){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>4||ny<0||ny>4)continue;
swap(Map[x][y],Map[nx][ny]);
if(eva(g))idsearch(g+1,nx,ny);//判断是否继续搜索
swap(Map[x][y],Map[nx][ny]);
}
}
int main()
{
~~~~~~
rep(i,1,15){//答案有一定限制
f=i;//迭代加深总值f
idsearch(0,x,y);
if(flag){cout<<f<<endl;break;}
}
if(!flag)cout<<"-1"<<endl;
~~~~~~
}
悬线法优化DP
const int maxn=2006;
int n,m,a[maxn][maxn],h[maxn][maxn],l[maxn][maxn];
int r[maxn][maxn],ans1=0,ans2=0;
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n)
rep(j,1,m){
scanf("%d",&a[i][j]);
if(i==1)h[i][j]=1;
else if(a[i][j]!=a[i-1][j])h[i][j]=h[i-1][j]+1;
else h[i][j]=1;
}
rep(i,1,n){
rep(j,1,m){
l[i][j]=j;
while(l[i][j]>1&&h[i][l[i][j]-1]>=h[i][j]&&a[i][l[i][j]]!=a[i][l[i][j]-1])
l[i][j]=l[i][l[i][j]-1];
}
dep(j,m,1){
r[i][j]=j;
while(r[i][j]<n&&h[i][r[i][j]+1]>=h[i][j]&&a[i][r[i][j]]!=a[i][r[i][j]+1])
r[i][j]=r[i][r[i][j]+1];
}
rep(j,1,m){
int temp=r[i][j]-l[i][j]+1;
ans2=max(ans2,temp*h[i][j]);
ans1=max(ans1,min(temp,h[i][j])*min(temp,h[i][j]));
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
倍增求LCA
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
rep(i,0,10)
if((1<<i)&t)x=fa[x][i];
dep(i,10,0)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if(x==y)return x;
else return fa[x][0];
}
莫队算法
洛谷P3604
const int maxn=6e4+6;
int n,m,t,blo,belong[maxn],a[maxn],ans[maxn],re;
unsigned short cnt[1<<26];
char s[maxn];
struct ask{int l,r,pos;}q[maxn];
inline bool cmp(ask a,ask b){
return belong[a.l]^belong[b.l]?belong[a.l]<belong[b.l]:belong[a.l]&1?a.r<b.r:a.r>b.r;
}
void insert(int x){
rep(i,0,t-1)re+=cnt[x^(1<<i)];
re+=cnt[x]++;
}
void erase(int x){
rep(i,0,t-1)re-=cnt[x^(1<<i)];
re-=--cnt[x];
}
int main()
{
n=read(),m=read();scanf("%s",s+1);
rep(i,1,n)t=max(t,s[i]-'a'+1);
blo=n/sqrt(m*2/3);
rep(i,1,n)belong[i]=(i-1)/blo,a[i]=a[i-1]^(1ll<<s[i]-'a');
rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].pos=i;
sort(q+1,q+1+m,cmp);
for(int i=1,l=1,r=0;i<=m;i++){
while(l>q[i].l)insert(a[--l]);
while(r<q[i].r)insert(a[++r]);
while(l<q[i].l)erase(a[l++]);
while(r>q[i].r)erase(a[r--]);
insert(a[l-1]);
ans[q[i].pos]=re;
erase(a[l-1]);
}
rep(i,1,m)cout<<ans[i]<<endl;
return 0;
}
三分
int main()
{
ax=read(),ay=read(),bx=read(),by=read();
cx=read(),cy=read(),dx=read(),dy=read();
p=read(),q=read(),r=read();
double lx=ax,ly=ay,rx=bx,ry=by,x1,y1,x2,y2,t1,t2;
while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){
x1=lx+(rx-lx)/3,y1=ly+(ry-ly)/3;
x2=lx+(rx-lx)/3*2,y2=ly+(ry-ly)/3*2;
t1=cal(x1,y1),t2=cal(x2,y2);
if(t1>t2)lx=x1,ly=y1;else rx=x2,ry=y2;
}
printf("%.2lf\n",cal(lx,ly));
return 0;
}
