第一部分，主要以数据结构和图论为主。
遗漏了许多，懒得补了。
0.快读
为了观感，之后的代码就将前面这几行去掉了。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define gc getchar()
#define dg(ch) isdigit(ch)
#define _mul(x) ((x<<3)+(x<<1))
#define ll long long
#define il inline
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
il int read(){int x=0,f=1;char ch=gc;while(!dg(ch)){if(ch=='-')f=-1;ch=gc;}while(dg(ch))x=_mul(x)+(ch^48),ch=gc;return x*f;}
1.线段树维护区间加、区间乘、区间和
先乘后加。
...
const int N=1e5+10;
int n,q,mod,a[N];ll sum[N<<2],add[N<<2],mul[N<<2];
int MOD(int x){return x>=mod?x-mod:x;}
struct SMT{
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
void pushdown(int u,int l,int r){
sum[ls]=MOD(1ll*sum[ls]*mul[u]%mod+1ll*(mid-l+1)*add[u]%mod);
sum[rs]=MOD(1ll*sum[rs]*mul[u]%mod+1ll*(r-mid)*add[u]%mod);
mul[ls]=1ll*mul[ls]*mul[u]%mod,mul[rs]=1ll*mul[rs]*mul[u]%mod;
add[ls]=MOD(1ll*add[ls]*mul[u]%mod+add[u]),add[rs]=MOD(1ll*add[rs]*mul[u]%mod+add[u]);
add[u]=0,mul[u]=1;
}
void pushup(int u){sum[u]=sum[ls]+sum[rs];}
void build(int u,int l,int r){
mul[u]=1;
if(l==r){sum[u]=a[l];return;}
build(ls,l,mid),build(rs,mid+1,r),pushup(u);
}
void modify(int u,int l,int r,int ql,int qr,int ad,int mu){
if(ql<=l&&r<=qr){
sum[u]=MOD(1ll*sum[u]*mu%mod+1ll*(r-l+1)*ad%mod);
mul[u]=1ll*mul[u]*mu,add[u]=MOD(1ll*add[u]*mu%mod+ad);
return;
}
pushdown(u,l,r);
if(ql<=mid) modify(ls,l,mid,ql,qr,ad,mu);
if(qr>mid) modify(rs,mid+1,r,ql,qr,ad,mu);
pushup(u);
}
int query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[u];
pushdown(u,l,r);int ans=0;
if(ql<=mid) ans=MOD(ans+query(ls,l,mid,ql,qr));
if(qr>mid) ans=MOD(ans+query(rs,mid+1,r,ql,qr));
return ans;
}
#undef mid
#undef ls
#undef rs
}S;
int main(){
n=rd,q=rd,mod=rd;FOR(i,1,n) a[i]=rd%mod;
S.build(1,1,n);
while(q--){
int op=rd,l=rd,r=rd,x;
if(op==1) x=rd,S.modify(1,1,n,l,r,0,x%mod);
else if(op==2) x=rd,S.modify(1,1,n,l,r,x%mod,1);
else printf("%d\n",S.query(1,1,n,l,r));
}
return 0;
}
2.树状数组
单点加、区间查。
...
const int N=5e5+10;
int n,q,tr[N],a[N];
void add(int x,int y){for(int i=x;i<=n;i+=i&(-i))tr[i]+=y;}
int query(int x){int res=0;for(int i=x;i;i-=i&(-i))res+=tr[i];return res;}
int main(){
n=rd,q=rd;FOR(i,1,n) a[i]=rd,add(i,a[i]);
while(q--){
int op=rd,l=rd,r=rd;
if(op==1) add(l,r);
else printf("%d\n",query(r)-query(l-1));
}
return 0;
}
3.st 表
...
const int N=1e5+10;
int n,m,f[N][20];
int query(int l,int r){
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
n=rd,m=rd;FOR(i,1,n) f[i][0]=rd;
FOR(i,1,19) for(int j=1;(j+(1<<i-1))<=n;j++) f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);
while(m--){
int l=rd,r=rd;
printf("%d\n",query(l,r));
}
return 0;
}
4.单调栈
const int N=3e6+10;
int n,a[N],stk[N],top,ans[N];
int main(){
n=rd;FOR(i,1,n) a[i]=rd;
ROF(i,n,1){
while(top&&a[stk[top]]<=a[i]) top--;
ans[i]=stk[top],stk[++top]=i;
}
FOR(i,1,n) printf("%d ",ans[i]);
return 0;
}
5.树链剖分
const int N=1e5+10;
int n,m,rt,mod,sum[N<<2],tag[N<<2],w[N],head[N],tot;
int sz[N],son[N],fa[N],dep[N],nw[N],dfn[N],idx,top[N];
struct node{int to,nxt;}edge[N<<1];
void add(int x,int y){edge[++tot]={y,head[x]},head[x]=tot;}
int MOD(int x){return x>=mod?x-mod:x;}
struct SMT{
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
void pushdown(int u,int l,int r){
if(!tag[u]) return;
tag[ls]=MOD(tag[ls]+tag[u]),tag[rs]=MOD(tag[rs]+tag[u]);
sum[ls]=MOD(sum[ls]+1ll*(mid-l+1)*tag[u]%mod),sum[rs]=MOD(sum[rs]+1ll*(r-mid)*tag[u]%mod);
tag[u]=0;
}
void pushup(int u){sum[u]=MOD(sum[ls]+sum[rs]);}
void build(int u,int l,int r){
if(l==r){sum[u]=nw[l];return;}
build(ls,l,mid),build(rs,mid+1,r),pushup(u);
}
void modify(int u,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
tag[u]=MOD(tag[u]+v),sum[u]=MOD(sum[u]+1ll*(r-l+1)*v%mod);
return;
}
pushdown(u,l,r);
if(ql<=mid) modify(ls,l,mid,ql,qr,v);
if(qr>mid) modify(rs,mid+1,r,ql,qr,v);
pushup(u);
}
int query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[u];
pushdown(u,l,r);int ans=0;
if(ql<=mid) ans=MOD(ans+query(ls,l,mid,ql,qr));
if(qr>mid) ans=MOD(ans+query(rs,mid+1,r,ql,qr));
return ans;
}
#undef mid
#undef ls
#undef rs
}S;
namespace HPD{
void dfs1(int x,int fat){
sz[x]=1,fa[x]=fat,dep[x]=dep[fat]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fat) continue;
dfs1(y,x),sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}
void dfs2(int x,int t){
dfn[x]=++idx,nw[idx]=w[x],top[x]=t;
if(!son[x]) return;
dfs2(son[x],t);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void tree_modify(int x,int y,int v){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]>=dep[fy]) S.modify(1,1,n,dfn[fx],dfn[x],v),x=fa[fx];
else S.modify(1,1,n,dfn[fy],dfn[y],v),y=fa[fy];
fx=top[x],fy=top[y];
}
if(dfn[x]<dfn[y]) S.modify(1,1,n,dfn[x],dfn[y],v);
else S.modify(1,1,n,dfn[y],dfn[x],v);
}
int tree_query(int x,int y){
int fx=top[x],fy=top[y],res=0;
while(fx!=fy){
if(dep[fx]>=dep[fy]) res=MOD(res+S.query(1,1,n,dfn[fx],dfn[x])),x=fa[fx];
else res=MOD(res+S.query(1,1,n,dfn[fy],dfn[y])),y=fa[fy];
fx=top[x],fy=top[y];
}
if(dfn[x]<dfn[y]) res=MOD(res+S.query(1,1,n,dfn[x],dfn[y]));
else res=MOD(res+S.query(1,1,n,dfn[y],dfn[x]));
return res;
}
int subtree_query(int x){return S.query(1,1,n,dfn[x],dfn[x]+sz[x]-1);}
void subtree_modify(int x,int v){S.modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,v);}
}
using namespace HPD;
int main(){
n=rd,m=rd,rt=rd,mod=rd;FOR(i,1,n) w[i]=rd%mod;
FOR(i,1,n-1){int x=rd,y=rd;add(x,y),add(y,x);}
HPD::dfs1(rt,0),HPD::dfs2(rt,rt),S.build(1,1,n);
while(m--){
int op=rd,x,y,v;
if(op==1) x=rd,y=rd,v=rd,HPD::tree_modify(x,y,v);
else if(op==2) x=rd,y=rd,printf("%d\n",HPD::tree_query(x,y));
else if(op==3) x=rd,v=rd,HPD::subtree_modify(x,v);
else x=rd,printf("%d\n",HPD::subtree_query(x));
}
return 0;
}
6.树上 K 级祖先（重链剖分做法）
直接往上跳就行，时间复杂度 \(O(n\log n)\)，会劣一些。
const int N=5e5+10;ui s;
int n,q,head[N],tot,rt;ll ans;
int sz[N],fa[N],son[N],dep[N],top[N],idx,D[N],dfn[N];
struct node{int to,nxt;}edge[N<<1];
void add(int x,int y){edge[++tot]={y,head[x]},head[x]=tot;}
namespace HPD{
void dfs1(int x){
sz[x]=1,dep[x]=dep[fa[x]]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa[x]) continue;
dfs1(y),sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}
void dfs2(int x,int t){
top[x]=t,dfn[x]=++idx,D[idx]=x;
if(!son[x]) return;
dfs2(son[x],t);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int KA(int x,int k){
while(k>=dep[x]-dep[top[x]]+1&&x!=rt){
k-=dep[x]-dep[top[x]]+1;
x=fa[top[x]];
}
return D[dfn[x]-k];
}
}
using namespace HPD;
il ui get(ui x){
x^=x<<13,x^=x>>17,x^=x<<5;
return s=x;
}
int main(){
n=rd,q=rd,cin>>s;int la=0;
FOR(i,1,n){
fa[i]=rd;
if(fa[i]!=0) add(i,fa[i]),add(fa[i],i);
else rt=i;
}
HPD::dfs1(rt),HPD::dfs2(rt,rt);
FOR(i,1,q){
int x=((get(s)^la)%n)+1,k=(get(s)^la)%dep[x];
la=HPD::KA(x,k),ans^=1ll*i*la;
}
printf("%lld\n",ans);
return 0;
}
7.笛卡尔树
每个节点由键值二元组 \((k,w)\) 组成，通常先按 \(k\) 排好序，然后利用栈来建树。
const int N=1e7+10;
int n,a[N],stk[N],top,ls[N],rs[N];ll ans1=0,ans2=0;
namespace Dtree{
void build(){
FOR(i,1,n){
int k=top;
while(k&&a[stk[k]]>a[i]) k--;
if(k) rs[stk[k]]=i;if(k<top) ls[i]=stk[k+1];
stk[++k]=i,top=k;
}
}
}
using namespace Dtree;
int main(){
n=rd;FOR(i,1,n) a[i]=rd;
Dtree::build();
FOR(i,1,n) ans1^=1ll*i*(ls[i]+1),ans2^=1ll*i*(rs[i]+1);
printf("%lld %lld\n",ans1,ans2);
return 0;
}
8.FHQ Treap
按值分裂。
const int N=1e5+10;
int n,rt,idx;
struct{int l,r,val,key,sz;}tr[N];
namespace FHQ{
int get(int v){
tr[++idx].val=v,tr[idx].key=rand(),tr[idx].sz=1;
return idx;
}
void pushup(int u){tr[u].sz=tr[tr[u].l].sz+tr[tr[u].r].sz+1;}
void split(int u,int v,int &x,int &y){
if(!u){x=y=0;return;}
if(tr[u].val<=v) x=u,split(tr[x].r,v,tr[x].r,y),pushup(x);
else y=u,split(tr[y].l,v,x,tr[y].l),pushup(y);
}
int merge(int x,int y){
if(!x||!y) return x^y;
if(tr[x].key<tr[y].key){tr[x].r=merge(tr[x].r,y),pushup(x);return x;}
else{tr[y].l=merge(x,tr[y].l),pushup(y);return y;}
}
void insert(int v){
int x,y,z;
split(rt,v,x,y),z=get(v),rt=merge(merge(x,z),y);
}
void del(int v){
int x,y,z;
split(rt,v,x,z),split(x,v-1,x,y),y=merge(tr[y].l,tr[y].r);
rt=merge(merge(x,y),z);
}
int getrank(int v){
int x,y,ans;
split(rt,v-1,x,y),ans=tr[x].sz+1,rt=merge(x,y);
return ans;
}
int getval(int u,int k){
if(k==tr[tr[u].l].sz+1) return tr[u].val;
if(k<tr[tr[u].l].sz+1) return getval(tr[u].l,k);
return getval(tr[u].r,k-tr[tr[u].l].sz-1);
}
int getpre(int v){
int x,y,ans;
split(rt,v-1,x,y),ans=getval(x,tr[x].sz),rt=merge(x,y);
return ans;
}
int getnxt(int v){
int x,y,ans;
split(rt,v,x,y),ans=getval(y,1),rt=merge(x,y);
return ans;
}
}
using namespace FHQ;
int main(){
n=rd;
while(n--){
int op=rd,x=rd;
if(op==1) FHQ::insert(x);
else if(op==2) FHQ::del(x);
else if(op==3) printf("%d\n",FHQ::getrank(x));
else if(op==4) printf("%d\n",FHQ::getval(rt,x));
else if(op==5) printf("%d\n",FHQ::getpre(x));
else printf("%d\n",FHQ::getnxt(x));
}
return 0;
}
9.FHQ-Treap（区间翻转操作）
按大小分裂。
const int N=1e5+10;
int n,q,rt,idx;
struct node{int l,r,val,key,sz,tag;}tr[N];
namespace FHQ{
#define ls (tr[u].l)
#define rs (tr[u].r)
int get(int v){
tr[++idx].val=v,tr[idx].key=rand(),tr[idx].sz=1,tr[idx].tag=0;
return idx;
}
void pushup(int u){tr[u].sz=tr[ls].sz+tr[rs].sz+1;}
void pushdown(int u){
if(!tr[u].tag) return;
swap(ls,rs);
tr[ls].tag^=1,tr[rs].tag^=1,tr[u].tag=0;
}
void split(int u,int k,int &x,int &y){
if(!u){x=y=0;return;}
pushdown(u);int res=tr[ls].sz+1;
if(res<=k) x=u,split(tr[x].r,k-res,tr[x].r,y),pushup(x);
else y=u,split(tr[y].l,k,x,tr[y].l),pushup(y);
}
int merge(int x,int y){
if(!x||!y) return x^y;
if(tr[x].key<tr[y].key){pushdown(x),tr[x].r=merge(tr[x].r,y),pushup(x);return x;}
else{pushdown(y),tr[y].l=merge(x,tr[y].l),pushup(y);return y;}
}
void output(int u){
if(!u) return;pushdown(u);
output(ls),printf("%d ",tr[u].val),output(rs);
}
#undef ls
#undef rs
}
using namespace FHQ;
int main(){
n=rd,q=rd;FOR(i,1,n) rt=merge(rt,get(i));
while(q--){
int l=rd,r=rd,x,y,z;
FHQ::split(rt,r,x,z),FHQ::split(x,l-1,x,y),tr[y].tag^=1,rt=FHQ::merge(merge(x,y),z);
}
FHQ::output(rt);
return 0;
}
10.线段树合并
洛谷的板子题。
const int N=1e5+10;
int n,m,head[N],tot,ls[N*100],rs[N*100],mx[N*100],id[N*100],idx,rt[N],ans[N];
struct node{int to,nxt;}edge[N<<1];
void add(int x,int y){edge[++tot]={y,head[x]},head[x]=tot;}
namespace LCA{
int f[N][20],dep[N];
void dfs(int x,int fa){
f[x][0]=fa,dep[x]=dep[fa]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa) continue;
dfs(y,x);
}
}
void init(){FOR(i,1,19) FOR(j,1,n) f[j][i]=f[f[j][i-1]][i-1];}
int lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
int k=log2(dep[y]+1);
ROF(i,k,0) if(dep[y]-(1<<i)>=dep[x]) y=f[y][i];
if(x==y) return x;
ROF(i,k,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
}
using namespace LCA;
namespace SMT{
#define mid ((l+r)>>1)
void pushup(int u){
if(mx[ls[u]]>=mx[rs[u]]) mx[u]=mx[ls[u]],id[u]=id[ls[u]];
else mx[u]=mx[rs[u]],id[u]=id[rs[u]];
}
void modify(int &u,int l,int r,int x,int v){
if(!u) u=++idx;
if(l==r){mx[u]+=v,id[u]=x;return;}
if(x<=mid) modify(ls[u],l,mid,x,v);
else modify(rs[u],mid+1,r,x,v);
pushup(u);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x^y;
if(l==r){mx[x]+=mx[y];return x;}
ls[x]=merge(ls[x],ls[y],l,mid),rs[x]=merge(rs[x],rs[y],mid+1,r);
pushup(x);return x;
}
void Tmerge(int x,int fa){
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa) continue;
Tmerge(y,x),rt[x]=merge(rt[x],rt[y],1,1e5);
}
if(mx[rt[x]]>0) ans[x]=id[rt[x]];
}
#undef mid
}
using namespace SMT;
int main(){
n=rd,m=rd;
FOR(i,1,n-1){int x=rd,y=rd;add(x,y),add(y,x);}
LCA::dfs(1,0),LCA::init();
while(m--){
int x=rd,y=rd,z=rd;
SMT::modify(rt[x],1,1e5,z,1),SMT::modify(rt[y],1,1e5,z,1);
SMT::modify(rt[LCA::lca(x,y)],1,1e5,z,-1);
if(f[LCA::lca(x,y)][0]) SMT::modify(rt[f[LCA::lca(x,y)][0]],1,1e5,z,-1);
}
SMT::Tmerge(1,0);
FOR(i,1,n) printf("%d\n",ans[i]);
return 0;
}
11.倍增 LCA
const int N=5e5+10;
int n,m,rt,head[N],tot;
struct node{int to,nxt;}edge[N<<1];
void add(int x,int y){edge[++tot]={y,head[x]},head[x]=tot;}
namespace LCA{
int f[N][20],dep[N];
void dfs(int x,int fa){
f[x][0]=fa,dep[x]=dep[fa]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa) continue;
dfs(y,x);
}
}
void init(){FOR(i,1,19) FOR(j,1,n) f[j][i]=f[f[j][i-1]][i-1];}
int lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
int k=log2(dep[y]+1);
ROF(i,k,0) if(dep[y]-(1<<i)>=dep[x]) y=f[y][i];
if(x==y) return x;
ROF(i,k,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
}
using namespace LCA;
int main(){
n=rd,m=rd,rt=rd;FOR(i,1,n-1){int x=rd,y=rd;add(x,y),add(y,x);}
LCA::dfs(rt,0),LCA::init();
while(m--){
int x=rd,y=rd;
printf("%d\n",LCA::lca(x,y));
}
return 0;
}
12.李超线段树
const int N=1e5+10,M=40000,mod=1e9;
const double eps=1e-12;
int n,seg[N<<2],cnt;
struct segment{double k,b;}p[N];
int cmp(double a,double b){
if(a-b>=eps) return 1;
if(b-a>=eps) return -1;
return 0;
}
double cal(int cnt,int x){return p[cnt].k*x+p[cnt].b;}
namespace SMT{
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
void update(int u,int l,int r,int c){
int &g=seg[u],cm=cmp(cal(c,mid),cal(g,mid));
if(cm==1||(cm==0&&c<g)) swap(g,c);
int cl=cmp(cal(c,l),cal(g,l)),cr=cmp(cal(c,r),cal(g,r));
if(cl==1||(cl==0&&c<g)) update(ls,l,mid,c);
if(cr==1||(cr==0&&c<g)) update(rs,mid+1,r,c);
}
void modify(int u,int l,int r,int ql,int qr,int c){
if(ql<=l&&r<=qr){update(u,l,r,c);return;}
if(ql<=mid) modify(ls,l,mid,ql,qr,c);
if(qr>mid) modify(rs,mid+1,r,ql,qr,c);
}
PDI pmx(PDI a,PDI b){
if(cmp(a.fi,b.fi)>0) return a;
if(cmp(a.fi,b.fi)<0) return b;
if(a.se<b.se) return a;
return b;
}
PDI query(int u,int l,int r,int x){
if(l>x||r<x) return mp(-1e16,0);
PDI res=mp(cal(seg[u],x),seg[u]);
if(l==r) return res;
return pmx(res,pmx(query(ls,l,mid,x),query(rs,mid+1,r,x)));
}
#undef mid
#undef ls
#undef rs
}
using namespace SMT;
int main(){
n=rd;int la=0;p[0].b=-1e9;
while(n--){
int op=rd;
if(op){
int x0=rd,y0=rd,x1=rd,y1=rd;
x0=(x0+la-1)%39989+1,x1=(x1+la-1)%39989+1;
y0=(y0+la-1)%mod+1,y1=(y1+la-1)%mod+1;
if(x0>x1) swap(x0,x1),swap(y0,y1);
if(x0==x1){
p[++cnt].k=0;int tmp=max(y0,y1);
p[cnt].b=1.0*tmp;
}
else{
p[++cnt].k=1.0*(y0-y1)/(x0-x1),p[cnt].b=-p[cnt].k*x0+y0;
}
SMT::modify(1,1,M,x0,x1,cnt);
}
else{
int k=rd;k=(k+la-1)%39989+1;
PDI res=SMT::query(1,1,M,k);
la=res.se;printf("%d\n",la);
}
}
return 0;
}
13.并查集
const int N=10010;
int n,m,fa[N];
int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];}
void merge(int x,int y){if(find(x)==find(y))return;fa[find(x)]=find(y);}
int main(){
n=rd,m=rd;FOR(i,1,n) fa[i]=i;
FOR(i,1,m){
int op=rd,x=rd,y=rd;
if(op==1) merge(x,y);
else puts(find(x)==find(y)?"Y":"N");
}
return 0;
}
14.堆优化 dijkstra
void dijkstra(int s){
memset(vis,0,sizeof(vis)),memset(dist,0x3f,sizeof(dist));
pq<PII,vector<PII>,greater<PII> > q;q.push(mp(0,s)),dist[s]=0;
while(!q.empty()){
int t=q.top().se;q.pop();
if(vis[t]) continue;vis[t]=1;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dist[y]>dist[t]+edge[i].w)
dist[y]=dist[t]+edge[i].w,q.push(mp(dist[y],y));
}
}
}
15.Floyd
const int N=110;
int n,m,g[N][N];
int main(){
n=rd,m=rd;memset(g,0x3f,sizeof(g));
FOR(i,1,n) g[i][i]=0;
FOR(i,1,m){int x=rd,y=rd,w=rd;g[x][y]=g[y][x]=min(g[x][y],w);}
FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
FOR(i,1,n){FOR(j,1,n)printf("%d ",g[i][j]);puts("");}
return 0;
}
还可以维护传递闭包。
FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) g[i][j]|=(g[i][k]&&g[k][j]);
16.kruskal
const int N=2e5+10;
int n,m,fa[N],tot;
struct node{int from,to,w;}edge[N];
void add(int x,int y,int w){edge[++tot]={x,y,w};}
bool cmp(node a,node b){return a.w<b.w;}
namespace DSU{
int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];}
void merge(int x,int y){if(find(x)==find(y))return;fa[find(x)]=find(y);}
}
using namespace DSU;
int main(){
n=rd,m=rd;FOR(i,1,n) fa[i]=i;
FOR(i,1,m){int x=rd,y=rd,w=rd;add(x,y,w);}
sort(edge+1,edge+1+m,cmp);
int cnt=0,res=0;
FOR(i,1,m){
int x=DSU::find(edge[i].from),y=DSU::find(edge[i].to),w=edge[i].w;
if(x==y) continue;
fa[x]=y,res+=w,cnt++;
}
if(cnt<n-1) puts("orz");
else printf("%d\n",res);
return 0;
}
17.差分约束（spfa 判负环）
const int N=10010;
int n,m,head[N],tot,cnt[N],dist[N],vis[N];
struct node{int to,nxt,w;}edge[N<<1];
void add(int x,int y,int w){edge[++tot]={y,head[x],w},head[x]=tot;}
bool spfa(int s){
memset(vis,0,sizeof(vis)),memset(dist,0x3f,sizeof(dist));
queue<int> q;q.push(s),dist[s]=0,vis[s]=1;
while(!q.empty()){
int t=q.front();q.pop(),vis[t]=0;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dist[y]>dist[t]+edge[i].w){
dist[y]=dist[t]+edge[i].w,cnt[y]=cnt[t]+1;
if(cnt[y]>n) return true;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
return false;
}
int main(){
n=rd,m=rd;
FOR(i,1,m){int x=rd,y=rd,w=rd;add(y,x,w);}
FOR(i,1,n) add(0,i,0);
if(spfa(0)) puts("NO");
else{
FOR(i,1,n) printf("%d ",dist[i]);
}
return 0;
}
18.Trie 维护字符串
const int N=3e6+10;
int T,n,q,tr[N][66],cnt[N],idx;char ch[N];
namespace Trie{
int cal(char ch){
if(ch>='a'&&ch<='z') return ch-'a';
else if(ch>='A'&&ch<='Z') return ch-'A'+26;
return ch-'0'+52;
}
void insert(char a[]){
int p=0,len=strlen(a+1);
FOR(i,1,len){
int t=cal(a[i]);
if(!tr[p][t]) tr[p][t]=++idx;
p=tr[p][t],cnt[p]++;
}
}
int query(char a[]){
int p=0,len=strlen(a+1);
FOR(i,1,len){
int t=cal(a[i]);
if(!tr[p][t]) return 0;
p=tr[p][t];
}
return cnt[p];
}
}
using namespace Trie;
void solve(){
FOR(i,0,idx) FOR(j,0,65) tr[i][j]=0;
FOR(i,0,idx) cnt[i]=0;
idx=0,n=rd,q=rd;
FOR(i,1,n) scanf("%s",ch+1),Trie::insert(ch);
while(q--){
scanf("%s",ch+1);
printf("%d\n",Trie::query(ch));
}
}
int main(){
T=rd;
while(T--) solve();
return 0;
}
19.01 Trie
const int N=1e5+10;
int n,dis[N],head[N],tot,ans,idx;
struct trie{int son[2];}tr[N*32];
struct node{int to,nxt,w;}edge[N<<1];
void add(int x,int y,int w){edge[++tot]={y,head[x],w},head[x]=tot;}
void dfs(int x,int fa){
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;if(y==fa) continue;
dis[y]=dis[x]^edge[i].w,dfs(y,x);
}
}
namespace Trie{
void insert(int x){
int p=0;
ROF(i,31,0){
int c=(x>>i)&1;
if(!tr[p].son[c]) tr[p].son[c]=++idx;
p=tr[p].son[c];
}
}
int query(int x){
int p=0,res=0;
ROF(i,31,0){
int c=(x>>i)&1;
if(tr[p].son[c^1]) res^=(1<<i),p=tr[p].son[c^1];
else p=tr[p].son[c];
}
return res;
}
}
using namespace Trie;
int main(){
n=rd;FOR(i,1,n-1){int x=rd,y=rd,w=rd;add(x,y,w),add(y,x,w);}
dfs(1,0);
FOR(i,1,n) Trie::insert(dis[i]);
FOR(i,1,n) ans=max(ans,Trie::query(dis[i]));
printf("%d\n",ans);
return 0;
}
20.tarjan 缩点+拓扑排序 dp
非常典。
const int N=1e5+10;
int n,m,head[N],tot,dfn[N],low[N],tim,stk[N],top,vis[N],cnt,scc[N],w[N],dis[N],a[N],deg[N];
vector<int> e[N];
struct node{int to,nxt;}edge[N];
il void add(int x,int y){edge[++tot]={y,head[x]},head[x]=tot;}
void tarjan(int x){
dfn[x]=low[x]=++tim,stk[++top]=x,vis[x]=1;
for(auto y:e[x]){
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y;cnt++;do{
y=stk[top--],scc[y]=cnt,w[cnt]+=a[y],vis[y]=0;
}while(x!=y);
}
}
void toposort(){
int ans=0;queue<int> q;
FOR(i,1,cnt) if(!deg[i]) q.push(i),dis[i]=w[i];
while(!q.empty()){
int t=q.front();q.pop();
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
dis[y]=max(dis[y],dis[t]+w[y]);
if(!--deg[y]) q.push(y);
}
}
FOR(i,1,cnt) ans=max(ans,dis[i]);
printf("%d\n",ans);
}
int main(){
n=rd,m=rd;FOR(i,1,n) a[i]=rd;
FOR(i,1,m){int x=rd,y=rd;e[x].pb(y);}
FOR(i,1,n) if(!dfn[i]) tarjan(i);
FOR(x,1,n) for(auto y:e[x]) if(scc[x]!=scc[y]) add(scc[x],scc[y]),deg[scc[y]]++;
toposort();
return 0;
}
21.点双
void tarjan(int x){
dfn[x]=low[x]=++tim,stk[++top]=x;
if(!head[x]){v[++cnt].pb(x);return;}
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y),low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
int z;cnt++;do{
z=stk[top--],v[cnt].pb(z);
}while(z!=y);
v[cnt].pb(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
22.边双
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++tim,stk[++top]=x,vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]) tarjan(y,i),low[x]=min(low[x],low[y]);
else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y;cnt++;do{
y=stk[top--],vis[y]=0,v[cnt].pb(y);
}while(x!=y);
}
}
23.扫描线求矩形面积并
扫描线的思想真的很常用。
const int N=2e5+10;
int n,lsh[N],tot,len[N<<2],tag[N<<2];
struct node{int x,y1,y2,k;}seg[N];
bool cmp(node a,node b){return a.x<b.x;}
namespace SMT{
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
void pushup(int u,int l,int r){
if(tag[u]) len[u]=lsh[r+1]-lsh[l];
else if(l!=r) len[u]=len[ls]+len[rs];
else len[u]=0;
}
void modify(int u,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){tag[u]+=v;pushup(u,l,r);return;}
if(ql<=mid) modify(ls,l,mid,ql,qr,v);
if(qr>mid) modify(rs,mid+1,r,ql,qr,v);
pushup(u,l,r);
}
#undef mid
#undef ls
#undef rs
}
using namespace SMT;
int main(){
n=rd;
FOR(i,1,n){
int x1=rd,y1=rd,x2=rd,y2=rd;
seg[i]={x1,y1,y2,1},seg[i+n]={x2,y1,y2,-1};
lsh[i]=y1,lsh[i+n]=y2;
}
sort(lsh+1,lsh+1+2*n),tot=unique(lsh+1,lsh+1+2*n)-lsh-1;
sort(seg+1,seg+1+2*n,cmp);ll ans=0;
FOR(i,1,2*n){
if(i>1) ans+=1ll*len[1]*(seg[i].x-seg[i-1].x);
int l=lower_bound(lsh+1,lsh+1+tot,seg[i].y1)-lsh;
int r=lower_bound(lsh+1,lsh+1+tot,seg[i].y2)-lsh;
SMT::modify(1,1,tot,l,r-1,seg[i].k);
}
printf("%lld\n",ans);
return 0;
}
24.欧拉路径
const int N=2e5+10;
int n,m,cnt[2],deg[N][2],st=1,nxt[N],stk[N],top;vector<int> e[N];
void dfs(int x){
for(int i=nxt[x];i<U(e[x]);i=nxt[x]){
nxt[x]=i+1;
dfs(e[x][i]);
}
stk[++top]=x;
}
int main(){
n=rd,m=rd;
FOR(i,1,m){int x=rd,y=rd;e[x].pb(y),deg[x][0]++,deg[y][1]++;}
FOR(i,1,n) sort(e[i].begin(),e[i].end());
bool flag=true;
FOR(i,1,n){
if(deg[i][0]!=deg[i][1]){
flag=false;
if(deg[i][0]-deg[i][1]==1) st=i,cnt[0]++;
else if(deg[i][1]-deg[i][0]==1) cnt[1]++;
else{puts("No");return 0;}
}
}
if(!flag&&cnt[0]!=1&&cnt[1]!=1){puts("No");return 0;}
dfs(st);
ROF(i,top,1) printf("%d ",stk[i]);
return 0;
}