update on 2023.10：

这篇博客的原本意义是 方便直接复制 / 快速复习，但部分原有代码存在本质错误，完全没有起到这个作用，故重构。

由于折叠代码块在某些 markdown 编辑器中不支持，现已全文取消折叠，请善用页面右侧标题 / Ctrl+F 快速跳转。

以下是本人平时的缺省源，所以下文的代码里可能存在部分 inline 缩写为 il。

#include

#define il inline

using namespace std;

il long long read()

{

long long xr=0,F=1; char cr;

while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;

while(cr>='0'&&cr<='9')

xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();

return xr*F;

}

输入输出优化

int 快读

il int read()

{

int xr=0,F=1; char cr;

while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;

while(cr>='0'&&cr<='9')

xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();

return xr*F;

}

double 快读

il double dbread()

{

double X=0,Y=1.0; int F=1; char cr=0;

while(!isdigit(cr)) {if(cr=='-') F=-1;cr=getchar();}

while(isdigit(cr)) X=X*10+(cr^48),cr=getchar();

cr=getchar();

while(isdigit(cr)) X+=(Y/=10)*(cr^48),cr=getchar();

return X*F;

}

int 快写

void write(int x)

{

if(x<0) putchar('-'),x=-x;

if(x>9) write(x/10); putchar(x%10+'0');

}

动态规划

DP 还存在什么板子吗（？

01 背包

for(int i=1;i<=m;i++)

for(int j=t;j;j--)

if(j-w[i]>=0) f[j]=max(f[j],f[j-w[i]]+c[i]);

树形背包

void dfs(int u,int fa)

{

siz[u]=1,f[u][1]=w[u];

for(auto v:e[u]) if(v^fa)

{

dfs(v,u);

for(int j=siz[u];j;j--)

for(int k=0;k<=siz[v];k++)

f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]);

siz[u]+=siz[v];

}

}

多重背包（二进制优化）

#include

using namespace std;

const int N=1e6+5;

int n,t,c[N],w[N];

int f[N],cnt;

int main()

{

scanf("%d%d",&n,&t);

for(int i=1,W,C,m;i<=n;i++)

{

scanf("%d%d%d",&C,&W,&m);

int j;

for(j=0;(1<<(j+1))-1<=m;j++) w[++cnt]=(1<

w[++cnt]=W*(m-((1<

}

for(int i=1;i<=cnt;i++)

for(int j=t;j;j--)

if(j-w[i]>=0) f[j]=max(f[j],f[j-w[i]]+c[i]);

cout<

return 0;

}

图论

平时的习惯是图用链前树用 vector。

最短路

Floyd

循环顺序不能颠倒。

for(int k=1;k<=n;k++) for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

SPFA

queue q;

int in[N],dis[N];

il void spfa(int s)

{

for(int i=1;i<=n;i++) dis[i]=inf;

dis[s]=0,in[s]=1; q.push(s);

while(!q.empty())

{

int u=q.front(); in[u]=0,q.pop();

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(dis[v]>dis[u]+e[i].w)

{

dis[v]=dis[u]+e[i].w;

if(!in[v]) in[v]=1,q.push(v);

}

}

}

}

SPFA 判负环

这里用的是最短路长度判负环，而非入队次数。注意多测清空。

int dis[N],in[N],len[N];

il bool spfa(int s)

{

queue q;

for(int i=1;i<=n;i++) dis[i]=inf,in[i]=0;

dis[s]=0,in[s]=1,len[s]=0; q.push(s);

while(!q.empty())

{

int u=q.front(); in[u]=0,q.pop();

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(dis[v]>dis[u]+e[i].w)

{

len[v]=len[u]+1,dis[v]=dis[u]+e[i].w;

if(len[v]>=n) return 0;

if(!in[v]) in[v]=1,q.push(v);

}

}

}

return 1;

}

Dijkstra

priority_queue,greater >q;

void dij(int s)

{

dis[s]=0;

q.push(pii(0,s));

while(!q.empty())

{

int u=q.top().se,f=q.top().fi; q.pop();

if(f!=dis[u])continue;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to,w=e[i].w;

if(dis[v]>dis[u]+w)

{

dis[v]=dis[u]+w;

q.push(pii(dis[v],v));

}

}

}

}

连通性相关（tarjan 系列）

强连通分量

stack q;

void tarjan(int u)

{

dfn[u]=++tot;low[u]=dfn[u];q.push(u);in[u]=1;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(!dfn[v]) {tarjan(v);low[u]=min(low[u],low[v]);}

else if(in[v]) low[u]=min(low[u],dfn[v]);

}

if(low[u]==dfn[u])

{

num++;

while(!q.empty())

{

if(q.top()==u) {in[u]=0,bel[u]=num,q.pop();break;}

in[q.top()]=0,bel[q.top()]=num,q.pop();

}

}

}

割点

注意根的特判。

int dfn[N],low[N],tot;

bool flag[N];

void tarjan(int u,int rt)

{

dfn[u]=low[u]=++tot;int qwq=0;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(!dfn[v])

{

tarjan(v,rt);

low[u]=min(low[u],low[v]);

if(low[v]>=dfn[u]&&rt!=u) flag[u]=1;

qwq++;

}

else low[u]=min(low[u],dfn[v]);

}

if(qwq>1&&u==rt) flag[u]=1;

}

点双连通分量

特判孤立点。

int dfn[N],low[N],tot,num;

stack q;

vector ans[N];

void tarjan(int u,int fa)

{

dfn[u]=low[u]=++tot; q.push(u);

int son=0;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to; if(v==fa) continue;

if(!dfn[v])

{

son=1;

tarjan(v,u),low[u]=min(low[u],low[v]);

if(low[v]>=dfn[u])

{

num++;

while(q.top()!=u)

{

int x=q.top();

ans[num].push_back(q.top()),q.pop();

if(x==v) break;

}

ans[num].push_back(u);

}

}

else low[u]=min(low[u],dfn[v]);

}

if(!fa&&!son) ans[++num].push_back(u);

}

割边（桥）

upd: 这个要注意是否有重边，有的话应该记录经过的上一条边而非上一个点。

void tarjan(int u,int fa)

{

low[u]=dfn[u]=++tot;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;if(v==fa) continue;

if(!dfn[v])

{

tarjan(v,u);

low[u]=min(low[u],low[v]);

if(low[v]>dfn[u]) flag[(i+1)/2]=1;

}

else low[u]=min(low[u],dfn[v]);

}

}

边双连通分量

int dfn[N],low[N],tot,num;

stack q;

vector ans[N];

void tarjan(int u,int lst)

{

dfn[u]=low[u]=++tot; q.push(u);

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to; if(i==(lst^1)) continue;

if(!dfn[v]) tarjan(v,i),low[u]=min(low[u],low[v]);

else low[u]=min(low[u],dfn[v]);

}

if(dfn[u]==low[u])

{

num++;

while("qwq")

{

int x=q.top(); q.pop(),ans[num].push_back(x);

if(x==u) break;

}

}

}

图的匹配 & 网络流

匈牙利

int f[N][N],vis[N],mat[N];

bool dfs(int u)

{

for(int i=1;i<=m;i++) if(!vis[i]&&f[u][i])

{

vis[i]=1;

if(!mat[i]||dfs(mat[i])) {mat[i]=u;return 1;}

}

return 0;

}

for(int i=1;i<=n;i++) dfs(i),memset(vis,0,sizeof(vis));

EK 最大流

int vis[N],pre[N],dis[N];

bool bfs(int s,int t)

{

for(int i=1;i<=n;i++) vis[i]=0,pre[i]=-1,dis[i]=inf;

queue q;q.push(s);

vis[s]=1;

while(!q.empty())

{

int u=q.front();q.pop();

if(u==t) return 1;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to,w=e[i].w;

if(vis[v]||!w) continue;

vis[v]=1,pre[v]=i;

dis[v]=min(dis[u],w);

q.push(v);

}

}

return 0;

}

void upd(int s,int t)

{

int now=t;

while(now!=s)

{

int i=pre[now];

e[i].w-=dis[t];

e[i^1].w+=dis[t];

now=e[i^1].to;

}

ans+=dis[t];

}

Dinic 最大流

il void add(int u,int v,int w)

{

e[++cnt]={head[u],v,w};head[u]=cnt;

e[++cnt]={head[v],u,0};head[v]=cnt;

}

int dis[N],now[N];

queue q;

il bool bfs()

{

for(int i=1;i<=n;i++) dis[i]=inf,now[i]=head[i];

dis[s]=0;q.push(s);

while(!q.empty())

{

int u=q.front(); q.pop();

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(e[i].w&&dis[v]==inf) dis[v]=dis[u]+1,q.push(v);

}

}

return dis[t]!=inf;

}

int dfs(int u,int sum)

{

int res=0;

if(u==t) return sum;

for(int i=now[u];i&∑i=e[i].nxt)

{

now[u]=i; int v=e[i].to;

if(!e[i].w||dis[v]!=dis[u]+1) continue;

int k=dfs(v,min(sum,e[i].w));

e[i].w-=k,e[i^1].w+=k,sum-=k,res+=k;

}

return res;

}

EK 费用流

bool spfa()

{

queue q;

for(int i=1;i<=n;i++) dis[i]=mn[i]=inf,pre[i]=-1,in[i]=0;

dis[s]=0,in[s]=1;q.push(s);

while(!q.empty())

{

int u=q.front();q.pop();in[u]=0;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to,w=e[i].w;

if(!w) continue;

if(dis[v]>dis[u]+e[i].c)

{

dis[v]=dis[u]+e[i].c;

mn[v]=min(mn[u],e[i].w);

pre[v]=i;

if(!in[v]) in[v]=1,q.push(v);

}

}

}

if(dis[t]==inf) return 0;

else return 1;

}

int ans1,ans2;

void upd()

{

int now=t;

while(now!=s)

{

int i=pre[now];

e[i].w-=mn[t],e[i^1].w+=mn[t];

now=e[i^1].to;

}

ans1+=mn[t];ans2+=dis[t]*mn[t];

}

Dinic 费用流（zkw 费用流）

int dis[N],in[N],now[N];

queue q;

bool spfa()

{

for(int i=1;i<=n;i++) dis[i]=inf,now[i]=head[i];

dis[s]=0,in[s]=1; q.push(s);

while(!q.empty())

{

int u=q.front(); in[u]=0;q.pop();

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(e[i].w&&dis[v]>dis[u]+e[i].c)

{

dis[v]=dis[u]+e[i].c;

if(!in[v]) in[v]=1,q.push(v);

}

}

}

return dis[t]!=inf;

}

int dfs(int u,int sum)

{

if(u==t) return sum;

in[u]=1; int res=0;

for(int i=now[u];i&∑i=e[i].nxt)

{

now[u]=i; int v=e[i].to;

if(e[i].w&&dis[v]==dis[u]+e[i].c&&!in[v])

{

int k=dfs(v,min(e[i].w,sum));

e[i].w-=k,e[i^1].w+=k,sum-=k,res+=k;

}

}

in[u]=0;return res;

}

上下界最大流

const int N=1e5+5,inf=1e9;

struct edge{

int nxt,to,w;

}e[N<<1];

int head[N],cnt=1;

void add(int u,int v,int w)

{

e[++cnt]={head[u],v,w};head[u]=cnt;

e[++cnt]={head[v],u,0};head[v]=cnt;

}

int n,m,s,t;

int dis[N],now[N];

struct qaq{

int u,v,l,r;

}E[N];

bool bfs(int s,int t)

{

queue q;

for(int i=s;i<=t;i++) dis[i]=inf,now[i]=head[i];

dis[s]=0,q.push(s);

while(!q.empty())

{

int u=q.front(); q.pop();

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(dis[v]!=inf||!e[i].w) continue;

dis[v]=dis[u]+1,q.push(v);

}

}

return dis[t]!=inf;

}

int dfs(int u,int t,int sum)

{

if(u==t) return sum;

int res=0;

for(int i=now[u];i&∑i=e[i].nxt)

{

int v=e[i].to; now[u]=i;

if(dis[v]!=dis[u]+1||!e[i].w) continue;

int k=dfs(v,t,min(e[i].w,sum));

e[i].w-=k,e[i^1].w+=k;

sum-=k,res+=k;

}

return res;

}

int W[N];

int calc(int n,int m,int s,int t)

{

memset(head,0,sizeof(head)),cnt=1;

memset(W,0,sizeof(W));

for(int i=1;i<=m;i++)

{

int u=E[i].u,v=E[i].v,l=E[i].l,r=E[i].r;

add(u,v,r-l),W[u]-=l,W[v]+=l;

}

int S=0,T=n+1;int sum=0;

add(t,s,inf);

for(int i=1;i<=n;i++)

{

if(W[i]>0) add(S,i,W[i]),sum+=W[i];

else add(i,T,-W[i]);

}

int res=0,ans=0;

while(bfs(S,T)) res+=dfs(S,T,inf);

if(res!=sum) return -1;

while(bfs(s,t)) ans+=dfs(s,t,inf);

return ans;

}

树上问题

Kruskal

bool cmp(node a,node b) {return a.w

int find(int x)

{

if(fa[x]==x) return x;

return fa[x]=find(fa[x]);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++) fa[i]=i;

for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

sort(e+1,e+m+1,cmp);

for(int i=1;i<=m;i++)

{

if(find(e[i].u)==find(e[i].v)) continue;

ans+=e[i].w;

fa[find(e[i].v)]=find(e[i].u);

if(cnt==n-2) {cnt++;break;}

}

printf("%d",ans);

return 0;

}

堆优化 Prim

int vis[N];

priority_queue,greater >q;

int Prim(int s)

{

int ans=0;

q.push(pii(0,s));

while(!q.empty())

{

int w=q.top().fi,u=q.top().se;q.pop();

if(vis[u]) continue;

ans=max(ans,w);vis[u]=1;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(vis[v]) continue;

q.push(pii(e[i].w,v));

}

}

return ans;

}

倍增 LCA

循环边界不要写 __lg(n)，这样会把 \(\log\) 跑满，常数真的很大。

int f[21][N],dep[N];

void init(int u,int fa)

{

f[0][u]=fa,dep[u]=dep[fa]+1;

for(int i=1;i<=__lg(dep[u]);i++) f[i][u]=f[i-1][f[i-1][u]];

for(auto v:e[u]) if(v^fa) init(v,u);

}

int lca(int x,int y)

{

if(dep[x]

for(int i=__lg(dep[x]);i>=0;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x];

for(int i=__lg(dep[x]);i>=0;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];

return x==y?x:f[0][x];

}

树剖 LCA & k 级祖先

int dfn[N],tot,y[N],dep[N],siz[N],son[N],top[N],fa[N];

void dfs1(int u,int ff)

{

dep[u]=dep[ff]+1,siz[u]=1,fa[u]=ff;

for(auto v:e[u]) if(v^ff)

{

dfs1(v,u),siz[u]+=siz[v];

if(siz[v]>siz[son[u]]) son[u]=v;

}

}

void dfs2(int u,int tp)

{

dfn[u]=++tot,y[tot]=u,top[u]=tp;

if(son[u]) dfs2(son[u],tp);

for(auto v:e[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

}

il int lca(int x,int y)

{

while(top[x]!=top[y])

{

if(dep[top[x]]

x=fa[top[x]];

}

return dep[x]

}

il int kfa(int x,int k)

{

int dp=dep[x]-k;

while(dep[top[x]]>dp) x=fa[top[x]];

return y[dfn[x]-(dep[x]-dp)];

}

dfs 序 LCA

int dfn[N],tot,st[20][N],dep[N];

il int get(int x,int y) {return dep[x]

void dfs(int u,int fa)

{

dfn[u]=++tot,st[0][tot]=fa,dep[u]=dep[fa]+1;

for(auto v:e[u]) if(v^fa) dfs(v,u);

}

void init()

{

dfs(rt,0);

for(int i=1;i<=__lg(n);i++) for(int j=1;j<=n-(1<

st[i][j]=get(st[i-1][j],st[i-1][j+(1<

}

int lca(int x,int y)

{

if(x==y) return x;

if((x=dfn[x])>(y=dfn[y])) swap(x,y);

int len=__lg(y-x);

return get(st[len][x+1],st[len][y-(1<

}

树上 k 级祖先

vector U[N],D[N],e[N];

int dep[N],mxdep[N],son[N],fa[N],top[N];

int f[21][N],highbit[N];

void dfs1(int u,int ff)

{

mxdep[u]=dep[u]=dep[ff]+1,fa[u]=ff,f[0][u]=ff;

for(int i=1;i<=__lg(dep[u]);i++) f[i][u]=f[i-1][f[i-1][u]];

for(auto v:e[u]) if(v^ff)

{

dfs1(v,u);

if(mxdep[v]>mxdep[u]) son[u]=v,mxdep[u]=mxdep[v];

}

}

void dfs2(int u,int tp)

{

top[u]=tp;

if(u==tp)

{

for(int i=0,f=u;i<=mxdep[u]-dep[u];i++) U[u].push_back(f),f=fa[f];

for(int i=0,f=u;i<=mxdep[u]-dep[u];i++) D[u].push_back(f),f=son[f];

}

if(son[u]) dfs2(son[u],tp);

for(auto v:e[u]) if(v!=son[u]) dfs2(v,v);

}

il int kfa(int x,int k)

{

if(!k) return x;

x=f[highbit[k]][x],k^=(1<

assert(abs(k)<=mxdep[x]-dep[x]);

return k>=0?U[x][k]:D[x][-k];

}

树剖维护树链 & 子树权值和

#define int long long

const int N=1e5+5;

int rt,mod;

int n,m,a[N],y[N];

il void add(int &x,int y) {x+=y;if(x>=mod) x-=mod;}

struct segtree

{

#define ls (now<<1)

#define rs (now<<1|1)

#define mid (l+r>>1)

int tr[N<<2],lz[N<<2];

void build(int now,int l,int r)

{

if(l==r) {tr[now]=a[y[l]]%mod;return;}

build(ls,l,mid),build(rs,mid+1,r);

tr[now]=(tr[ls]+tr[rs])%mod;

}

void modify(int now,int l,int r,int ml,int mr,int k)

{

tr[now]+=(mr-ml+1)*k;

if(l==ml&&r==mr) {add(lz[now],k);return;}

if(mr<=mid) modify(ls,l,mid,ml,mr,k);

else if(ml>mid) modify(rs,mid+1,r,ml,mr,k);

else modify(ls,l,mid,ml,mid,k),modify(rs,mid+1,r,mid+1,mr,k);

}

int query(int now,int l,int r,int ml,int mr)

{

if(l==ml&&r==mr) return tr[now];

int res=lz[now]*(mr-ml+1)%mod;

if(mr<=mid) return (res+query(ls,l,mid,ml,mr))%mod;

else if(ml>mid) return (res+query(rs,mid+1,r,ml,mr))%mod;

else return (res+query(ls,l,mid,ml,mid)+query(rs,mid+1,r,mid+1,mr))%mod;

}

}seg;

vector e[N];

int fa[N],dfn[N],tot,siz[N],son[N],top[N],dep[N];

void dfs1(int u,int ff)

{

fa[u]=ff,siz[u]=1,dep[u]=dep[ff]+1;

for(auto v:e[u]) if(v^ff)

{

dfs1(v,u),siz[u]+=siz[v];

if(siz[v]>siz[son[u]]) son[u]=v;

}

}

void dfs2(int u,int tp)

{

dfn[u]=++tot,y[tot]=u,top[u]=tp;

if(son[u]) dfs2(son[u],tp);

for(auto v:e[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

}

il void addline(int x,int y,int k)

{

while(top[x]!=top[y])

{

if(dep[top[x]]

seg.modify(1,1,n,dfn[top[x]],dfn[x],k);

x=fa[top[x]];

}

if(dep[x]>dep[y]) swap(x,y);

seg.modify(1,1,n,dfn[x],dfn[y],k);

}

il int queryline(int x,int y)

{

int res=0;

while(top[x]!=top[y])

{

if(dep[top[x]]

add(res,seg.query(1,1,n,dfn[top[x]],dfn[x]));

x=fa[top[x]];

}

if(dep[x]>dep[y]) swap(x,y);

add(res,seg.query(1,1,n,dfn[x],dfn[y]));

return res;

}

il void addsub(int x,int k) {seg.modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);}

il int querysub(int x) {return seg.query(1,1,n,dfn[x],dfn[x]+siz[x]-1);}

prufer 序列

namespace sub1

{

int fa[N],a[N],son[N];

void solve()

{

for(int i=1;i

for(int i=1,j=1;i<=n-2;i++,j++)

{

while(son[j]) j++;

a[i]=fa[j];

while(i<=n-2&&!(--son[a[i]])&&a[i]

}

int ans=0;

for(int i=1;i<=n-2;i++) ans^=i*a[i];

printf("%lld\n",ans);

}

}

namespace sub2

{

int fa[N],a[N],son[N];

void solve()

{

for(int i=1;i<=n-2;i++) a[i]=read(),son[a[i]]++;

a[n-1]=n;

for(int i=1,j=1;i

{

while(son[j]) j++;

fa[j]=a[i];

while(i

}

int ans=0;

for(int i=1;i

printf("%lld\n",ans);

}

}

其他

欧拉回路

stack q;

void dfs(int u)

{

for(int i=head[u];i;i=head[u])

{

head[u]=e[i].nxt;

int v=e[i].to; dfs(v);

}

q.push(u);

}

数学

线性代数

快速幂

int qpow(int n,int k)

{

int res=1;

for(;k;n=n*n%mod,k>>=1) if(k&1) res=res*n%mod;

return res;

}

矩阵快速幂

il void add(int &x,int y) {x+=y;if(x>=mod) x-=mod;}

struct matrix

{

int f[2][2];

matrix() {memset(f,0,sizeof(f));}

void init() {f[0][0]=f[1][1]=1;}

friend matrix operator *(const matrix &a,const matrix &b)

{

matrix res;

for(int i=0;i<2;i++) for(int k=0;k<2;k++)

for(int j=0;j<2;j++) add(res.f[i][j],a.f[i][k]*b.f[k][j]%mod);

return res;

}

};

matrix qpow(matrix n,int k)

{

matrix res; res.init();

for(;k;n=n*n,k>>=1) if(k&1) res=res*n;

return res;

}

高斯消元

void gauss()

{

for(int j=1;j<=n;j++)

{

for(int i=j;i<=n;i++) if(f[i][j]) {swap(f[i],f[j]);break;}

if(fabs(f[j][j])

for(int i=1;i<=n;i++)

{

if(i==j) continue;

double K=f[i][j]/f[j][j];

for(int k=1;k<=n+1;k++) f[i][k]-=K*f[j][k];

}

}

for(int i=1;i<=n;i++) f[i][n+1]/=f[i][i];

}

行列式

struct matrix

{

int n,m,f[N][N];

matrix() {n=m=0;memset(f,0,sizeof(f));}

int * operator [](const int &x) {return f[x];}

};

int det(matrix f)

{

int res=1;

for(int i=1;i<=n;i++)

for(int j=i+1;j<=n;j++)

{

while(f[i][i])

{

int div=f[j][i]/f[i][i];

for(int k=i;k<=n;k++) f[j][k]=(f[j][k]-1ll*f[i][k]*div%mod+mod)%mod;

swap(f.f[i],f.f[j]),res*=-1;

}

swap(f.f[i],f.f[j]),res*=-1;

}

for(int i=1;i<=n;i++) res=1ll*res*f[i][i]%mod;

return (res+mod)%mod;

}

线性基

贪心法

int n,p[N];

il void ins(int x)

{

for(int i=49;i>=0;i--) if(x>>i&1)

{

if(!p[i]) {p[i]=x;return;}

x^=p[i];

}

}

如果不想写高斯消元，可以在贪心后调整，变成与高斯消元法相同的形式：

for(int i=63;i>=0;i--)

{

if(!p[i]) continue;

for(int j=63;j>i;j--) if((p[j]>>i)&1) p[j]^=p[i];

}

数论

欧拉函数

要复习

int now=m;

for(int i=2;i*i<=m;i++)

{

if(now%i==0)

{

phi=phi*(i-1)/i;

while(now%i==0) now/=i;

}

}

if(now>1) phi=phi*(now-1)/now;

exgcd

void exgcd(int a,int b,int &x,int &y)

{

if(!b) {x=1,y=0;return;}

exgcd(b,a%b,y,x); y-=x*(a/b);

}

Lucas 定理

int c(int n,int m){

if(m>n) return 0;

return jc[n]*qpow(jc[m],mod-2)%mod*qpow(jc[n-m],mod-2)%mod;

}

int lucas(int n,int m){

if(!m) return 1;

return lucas(n/mod,m/mod)*c(n%mod,m%mod)%mod;

}

原根

inline bool check1(int x)//check原根存在性

{

if(x==2||x==4) return 1;

if(x%2==0) x/=2;

if(x%2==0) return 0;

//bool flag=0;

for(int i=2;i*i<=x;i++)

{

if(x%i==0)

{

while(x%i==0) x/=i;

return (x==1);

}

}

return 1;

}

inline bool check2(int x,int n)//判定合法性

{

if(__gcd(x,n)>1) return 0;

int m=phi[n];tot=0;

for(int i=2;i*i<=m;i++)

{

if(m%i==0)

{

fac[++tot]=i;

while(m%i==0) m/=i;

}

}

if(m>1) fac[++tot]=m;

for(int i=1;i<=tot;i++)

if(qpow(x,phi[n]/fac[i],n)==1) return 0;

return 1;

}

BSGS

#define int long long

int p,b,n;

unordered_map mp;

int qpow(int n,int k)

{

int res=1;

for(;k;n=n*n%p,k>>=1)

if(k&1) res=res*n%p;

return res;

}

signed main()

{

p=read(),b=read(),n=read();

int t=sqrt(p); if(t*t

for(int i=0;i<=t;i++) mp[n*qpow(b,i)%p]=i;

for(int i=1;i<=t;i++)

{

if(mp[qpow(b,t*i)])

{

printf("%lld\n",t*i-mp[qpow(b,t*i)]);

return 0;

}

}

printf("no solution\n");

return 0;

}

exBSGS

const int P=1e7-9;

const int N=1e7+5;

struct hsh{

int w,val,nxt;

}e[N];

int head[N],tt;

void ins(int x,int val)

{

for(int i=head[x%P];i;i=e[i].nxt) if(e[i].w==x) {e[i].val=val;return;}

e[++tt]={x,val,head[x%P]};head[x%P]=tt;

}

int find(int x)

{

for(int i=head[x%P];i;i=e[i].nxt) if(e[i].w==x) return e[i].val;

return 0;

}

int BSGS(int a,int n,int p,int ad)

{

int t=ceil(sqrt(p)),s=1;

for(int i=1;i<=t;i++) s=1ll*s*a%p,ins(1ll*s*n%p,i);

int qwq=s;s=ad;

for(int i=0;i<=t;i++,s=1ll*s*qwq%p)

{

if(find(s)&&1ll*i*t-find(s)>0)

{

int res=1ll*i*t-find(s),ss=1;tt=0;

for(int i=1;i<=t;i++) ss=1ll*ss*a%p,head[(1ll*ss*n%p)%P]=0;

return res;

}

}

s=1;tt=0;

for(int i=1;i<=t;i++) s=1ll*s*a%p,head[(1ll*s*n%p)%P]=0;

return -1;

}

int exBSGS(int a,int n,int p)

{

a%=p,n%=p;

if(n==1||p==1) return 0;

int cnt=0,ad=1;

while("qwq")

{

int d=__gcd(a,p);

if(d==1) break;

if(n%d) return -1;

cnt++;n/=d,p/=d;

ad=(1ll*ad*a/d)%p;

if(ad==n) return cnt;

}

int ans=BSGS(a,n,p,ad);

return ans==-1?-1:ans+cnt;

}

signed main()

{

while("pap")

{

int a=read(),p=read(),n=read();

if(!a) return 0;

int ans=exBSGS(a,n,p);

if(ans==-1) printf("No Solution\n");

else printf("%d\n",ans);

}

return 0;

}

类欧几里得

#include

#define int long long

using namespace std;

const int mod=998244353,inv2=499122177,inv6=166374059;

int T,n,a,b,c;

struct node{

int f=0,g=0,h=0;

};

node solve(int a,int b,int c,int n)

{

node d;

if(!a)

{

d.f=(b/c)*(n+1)%mod;

d.g=n*(n+1)%mod*inv2%mod*(b/c)%mod;

d.h=(b/c)*(b/c)%mod*(n+1)%mod;

}

else if(a>=c||b>=c)

{

node q=solve(a%c,b%c,c,n);

d.f=((n*(n+1)%mod*inv2%mod*(a/c)%mod+(n+1)*(b/c)%mod+q.f)+mod)%mod;

d.g=((a/c)*n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod+(b/c)*n%mod*(n+1)%mod*inv2%mod+q.g)%mod;

d.h=(2*(b/c)%mod*q.f%mod+2*(a/c)%mod*q.g%mod+(a/c)*(a/c)%mod*n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod+(b/c)*(b/c)%mod*(n+1)%mod+(a/c)*(b/c)%mod*n%mod*(n+1)%mod+q.h)%mod;

}

else

{

int m=(a*n+b)/c;

node q=solve(c,c-b-1,a,m-1);

d.f=(n*m%mod-q.f+mod)%mod;

d.g=(((m*n%mod*(n+1)%mod-q.h-q.f)%mod)+mod)%mod*inv2%mod;

d.h=((n*m%mod*(m+1)%mod-2*q.g%mod-2*q.f%mod-d.f)%mod+mod)%mod;

}

//cout<

return d;

}

signed main()

{

scanf("%lld",&T);

while(T--)

{

scanf("%lld%lld%lld%lld",&n,&a,&b,&c);

node ans=solve(a,b,c,n);

cout<

}

return 0;

}

筛法

Eratosthenes 筛

bool flag[N];

void Eratosthenes(int n)

{

for(int i=2;i<=n;i++)

{

if(flag[i])continue;

for(int j=2;j*i<=n;j++) flag[j*i]=1;

}

}

Euler 筛

for(int i=2;i<=n;i++)

{

if(!flag[i]) p[++cnt]=i;

for(int j=1;j<=cnt&&i*p[j]<=n;j++)

{

flag[i*p[j]]=1;

if(!i%p[j]) break;

}

}

线性筛欧拉函数

phi[1]=1;

for(int i=2;i<=n;i++)

{

if(!flag[i]) {p[++cnt]=i;phi[i]=i-1;}

for(int j=1;j<=cnt&&i*p[j]<=n;j++)

{

flag[i*p[j]]=1;

if(!(i%p[j])) {phi[i*p[j]]=phi[i]*p[j];break;}

else phi[i*p[j]]=phi[i]*(p[j]-1);

}

}

线性筛莫比乌斯函数

mu[1]=1;

for(int i=2;i<=mx;i++)

{

if(!flag[i]) p[++cnt]=i,mu[i]=-1;

for(int j=1;j<=cnt&&i*p[j]<=mx;j++)

{

flag[i*p[j]]=1;

if(i%p[j]) mu[i*p[j]]=mu[i]*mu[p[j]];

else {mu[i*p[j]]=0;break;}

}

}

杜教筛

int getmu(int n)

{

if(n<=5e6) return mu[n];

else if(mpmu[n]) return mpmu[n];

int res=1;

for(int l=2,r;l<=n;l=r+1)

{

r=min(n,n/(n/l));

res-=(r-l+1)*getmu(n/l);

}

return mpmu[n]=res;

}

int getphi(int n)

{

if(n<=5e6) return phi[n];

else if(mpphi[n]) return mpphi[n];

int res=(n+1)*n/2;

for(int l=2,r;l<=n;l=r+1)

{

r=min(n,n/(n/l));

res-=(r-l+1)*getphi(n/l);

}

return mpphi[n]=res;

}

多项式

FFT

递归实现（常数较大，慎用）

void FFT(int limit,Complex a[],int op)

{

if(limit==1) return;

Complex a1[(limit>>1)+5],a2[(limit>>1)+5];

for(int i=0;i<=limit;i+=2) a1[i>>1]=a[i],a2[i>>1]=a[i+1];

FFT(limit>>1,a1,op),FFT(limit>>1,a2,op);

Complex Wn={cos(2.0*pai/limit),sin(2.0*pai/limit)*op},w={1,0};

for(int i=0;i<(limit>>1);i++,w=w*Wn)

{

a[i]=a1[i]+w*a2[i];

a[i+(limit>>1)]=a1[i]-w*a2[i];

}

}

int main()

{

n=read(),m=read();

for(int i=0;i<=n;i++) a[i].x=read();

for(int i=0;i<=m;i++) b[i].x=read();

int w=1;while(w<=m+n) w<<=1;

FFT(w,a,1),FFT(w,b,1);

for(int i=0;i<=w;i++) a[i]=a[i]*b[i];

FFT(w,a,-1);

for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].x/w+0.5));

return 0;

}

迭代实现

const int N=4e6+5;

const double pi=acos(-1);

int n,m,limit=1;

struct Complex {double x,y;}a[N],b[N];

il Complex operator +(Complex a,Complex b) {return {a.x+b.x,a.y+b.y};}

il Complex operator -(Complex a,Complex b) {return {a.x-b.x,a.y-b.y};}

il Complex operator *(Complex a,Complex b) {return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}

int to[N];

void FFT(Complex *a,int tp)

{

for(int i=0;i

for(int len=1;len

{

Complex Wn={cos(pi/len),sin(pi/len)*tp};

for(int i=0;i

{

Complex w={1,0};

for(int j=0;j

{

Complex x=a[i+j],y=w*a[i+len+j];

a[i+j]=x+y,a[i+len+j]=x-y;

}

}

}

}

int main()

{

n=read(),m=read();

for(int i=0;i<=n;i++) a[i].x=read();

for(int i=0;i<=m;i++) b[i].x=read();

int k=0; while(limit<=n+m) limit<<=1,k++;

for(int i=0;i>1]>>1)|((i&1)<<(k-1));

FFT(a,1),FFT(b,1);

for(int i=0;i

FFT(a,-1);

for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].x/limit+0.5));

return 0;

}

NTT

#define int long long

const int N=4e6+5,mod=998244353;

il int qpow(int n,int k=mod-2)

{

int res=1;

for(;k;n=n*n%mod,k>>=1) if(k&1) res=res*n%mod;

return res;

}

int n,m,a[N],b[N],inv=qpow(3),limit=1,to[N];

il void NTT(int *a,int tp)

{

for(int i=0;i

for(int len=1;len

{

int Wn=qpow(tp>0?3:inv,(mod-1)/(len<<1));

for(int i=0;i

for(int j=0,w=1;j

{

int x=a[i+j],y=w*a[i+len+j]%mod;

a[i+j]=(x+y)%mod,a[i+len+j]=(x-y+mod)%mod;

}

}

}

signed main()

{

n=read(),m=read();

for(int i=0;i<=n;i++) a[i]=read();

for(int i=0;i<=m;i++) b[i]=read();

int k=0; while(limit<=m+n) limit<<=1,k++;

for(int i=0;i>1]>>1)|((i&1)<<(k-1));

NTT(a,1),NTT(b,1);

for(int i=0;i

NTT(a,-1);

for(int i=0;i<=n+m;i++) printf("%lld ",a[i]*qpow(limit)%mod);

return 0;

}

FWT

void Or(int *a,int tp)

{

for(int len=1;len<(1<

for(int i=0;i<(1<

for(int j=0;j

}

void And(int *a,int tp)

{

for(int len=1;len<(1<

for(int i=0;i<(1<

for(int j=0;j

}

void Xor(int *a,int tp)

{

for(int len=1;len<(1<

for(int i=0;i<(1<

for(int j=0;j

{

int x=a[i+j],y=a[i+j+len];

a[i+j]=(x+y)*tp%mod,a[i+j+len]=(x-y+mod)%mod*tp%mod;

}

}

数据结构

路径压缩并查集

int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

il void merge(int x,int y)

{

if((x=find(x))==(y=find(y))) return;

fa[x]=y;

}

单调栈

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

q.push(n);

for(int i=n-1;i;i--)

{

//cout<

if(!q.empty())

{

while(!q.empty()&&a[i]>=a[q.top()]) q.pop();

if(!q.empty()) ans[i]=q.top();

}

q.push(i);

}

for(int i=1;i<=n;i++) cout<

单调队列

求的是区间最小值，最大值同理

st=1,ed=0;

for(int i=1;i<=n;i++)

{

while(st<=ed&&q[st]<=i-k) st++;

while(st<=ed&&a[q[ed]]>a[i]) ed--;

q[++ed]=i;

if(i>=k) printf("%d ",a[q[st]]);

}

printf("\n");

ST 表

for(int i=1;i<=n;i++) a[i]=read(),st[0][i]=a[i];

for(int i=1;i<=__lg(n);i++)

for(int j=1;j<=n-(1<

while(m--)

{

int l=read(),r=read();

int len=__lg(r-l+1);

printf("%d\n",max(st[len][l],st[len][r-(1<

}

树状数组

单点加区间求和的经典应用

struct BIT

{

int tr[N];

il void add(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}

il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}

il int ask(int l,int r) {return query(r)-query(l-1);}

}tr;

区间加单点求和

struct BIT

{

int tr[N];

il void modify(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}

il void add(int l,int r,int k) {modify(l,k),modify(r+1,-k);}

il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}

}tr;

线段树相关

线段树

区间加区间求和

int tr[N<<2],lz[N<<2];

#define ls (now<<1)

#define rs (now<<1|1)

#define mid (l+r>>1)

il void pushup(int now) {tr[now]=tr[ls]+tr[rs];}

il void pushdown(int now,int l,int r)

{

tr[ls]+=lz[now]*(mid-l+1),tr[rs]+=lz[now]*(r-mid);

lz[ls]+=lz[now],lz[rs]+=lz[now];

lz[now]=0;

}

void build(int now,int l,int r)

{

if(l==r) {tr[now]=a[l];return;}

build(ls,l,mid),build(rs,mid+1,r);

pushup(now);

}

void modify(int now,int l,int r,int ml,int mr,int k)

{

if(l==ml&&r==mr) {tr[now]+=(r-l+1)*k,lz[now]+=k;return;}

pushdown(now,l,r);

if(mr<=mid) modify(ls,l,mid,ml,mr,k);

else if(ml>mid) modify(rs,mid+1,r,ml,mr,k);

else modify(ls,l,mid,ml,mid,k),modify(rs,mid+1,r,mid+1,mr,k);

pushup(now);

}

int query(int now,int l,int r,int ml,int mr)

{

if(l==ml&&r==mr) return tr[now];

pushdown(now,l,r);

if(mr<=mid) return query(ls,l,mid,ml,mr);

else if(ml>mid) return query(rs,mid+1,r,ml,mr);

else return query(ls,l,mid,ml,mid)+query(rs,mid+1,r,mid+1,mr);

}

同上，但是标记永久化版

int tr[N<<2],lz[N<<2];

void build(int now,int l,int r)

{

if(l==r) {tr[now]=a[l];return;}

build(ls,l,mid),build(rs,mid+1,r);

tr[now]=tr[ls]+tr[rs];

}

void modify(int now,int l,int r,int ml,int mr,int k)

{

tr[now]+=(mr-ml+1)*k;

if(l==ml&&r==mr) {lz[now]+=k;return;}

if(mr<=mid) modify(ls,l,mid,ml,mr,k);

else if(ml>mid) modify(rs,mid+1,r,ml,mr,k);

else modify(ls,l,mid,ml,mid,k),modify(rs,mid+1,r,mid+1,mr,k);

}

int query(int now,int l,int r,int ml,int mr)

{

if(l==ml&&r==mr) return tr[now];

int res=lz[now]*(mr-ml+1);

if(mr<=mid) return res+query(ls,l,mid,ml,mr);

else if(ml>mid) return res+query(rs,mid+1,r,ml,mr);

else return res+query(ls,l,mid,ml,mid)+query(rs,mid+1,r,mid+1,mr);

}

区间加区间乘区间求和（线段树 2）

int tr[N<<2],lza[N<<2],lzm[N<<2];

#define ls (now<<1)

#define rs (now<<1|1)

#define mid (l+r>>1)

il void add(int &x,int y) {x+=y;x%=mod;}

il void pushup(int now) {tr[now]=(tr[ls]+tr[rs])%mod;}

il void pushdown(int now,int l,int r)

{

(tr[ls]*=lzm[now])%=mod,(tr[rs]*=lzm[now])%=mod;

(lzm[ls]*=lzm[now])%=mod,(lzm[rs]*=lzm[now])%=mod;

(lza[ls]*=lzm[now])%=mod,(lza[rs]*=lzm[now])%=mod;

lzm[now]=1;

add(tr[ls],(mid-l+1)*lza[now]%mod),add(tr[rs],(r-mid)*lza[now]%mod);

add(lza[ls],lza[now]),add(lza[rs],lza[now]);

lza[now]=0;

}

il void build(int now,int l,int r)

{

lzm[now]=1;

if(l==r) {tr[now]=a[l];return;}

build(ls,l,mid),build(rs,mid+1,r);

pushup(now);

}

void modify1(int now,int l,int r,int ml,int mr,int k)

{

if(l==ml&&r==mr) {(tr[now]*=k)%=mod,(lzm[now]*=k)%=mod,(lza[now]*=k)%=mod;return;}

pushdown(now,l,r);

if(mr<=mid) modify1(ls,l,mid,ml,mr,k);

else if(ml>mid) modify1(rs,mid+1,r,ml,mr,k);

else modify1(ls,l,mid,ml,mid,k),modify1(rs,mid+1,r,mid+1,mr,k);

pushup(now);

}

void modify2(int now,int l,int r,int ml,int mr,int k)

{

if(l==ml&&r==mr) {add(tr[now],(r-l+1)*k%mod),add(lza[now],k);return;}

pushdown(now,l,r);

if(mr<=mid) modify2(ls,l,mid,ml,mr,k);

else if(ml>mid) modify2(rs,mid+1,r,ml,mr,k);

else modify2(ls,l,mid,ml,mid,k),modify2(rs,mid+1,r,mid+1,mr,k);

pushup(now);

}

int query(int now,int l,int r,int ml,int mr)

{

if(l==ml&&r==mr) return tr[now];

pushdown(now,l,r);

if(mr<=mid) return query(ls,l,mid,ml,mr);

else if(ml>mid) return query(rs,mid+1,r,ml,mr);

else return (query(ls,l,mid,ml,mid)+query(rs,mid+1,r,mid+1,mr))%mod;

}

主席树

#include

#define ls (tr[now].l)

#define rs (tr[now].r)

using namespace std;

const int N=1e6+5;

int n,m,cnt;

int a[N],rt[N];

struct node{

int l,r,v;

}tr[N<<5];

int add(int now)

{

tr[++cnt]=tr[now];

return cnt;

}

int build(int now,int l,int r)

{

now=++cnt;

if(l==r)

{

tr[now].v=a[l];

return now;

}

int mid=(l+r)>>1;

tr[now].l=build(ls,l,mid);

tr[now].r=build(rs,mid+1,r);

return now;

}

int modify(int now,int l,int r,int x,int k)

{

now=add(now);

if(l==r)

{

tr[now].v=k;

return now;

}

int mid=(l+r)>>1;

if(x<=mid) tr[now].l=modify(ls,l,mid,x,k);

else tr[now].r=modify(rs,mid+1,r,x,k);

return now;

}

int query(int now,int l,int r,int x)

{

if(l==r) return tr[now].v;

int mid=(l+r)>>1;

if(x<=mid) return query(ls,l,mid,x);

else return query(rs,mid+1,r,x);

}

signed main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

rt[0]=build(0,1,n);

for(int i=1;i<=m;i++)

{

int v,op,x,k;

scanf("%d%d%d",&v,&op,&x);

if(op==1)

{

scanf("%d",&k);

rt[i]=modify(rt[v],1,n,x,k);

}

else

{

cout<

rt[i]=rt[v];

}

}

return 0;

}

可持久化权值线段树（主席树 2）

求的是静态区间 \(k\) 小值。

#include

using namespace std;

const int N=2e5+5;

int n,m,a[N],t[N],rt[N],cnt;

struct node{

int l,r,w;

}tr[N<<5];

int add(int now)

{

tr[++cnt]=tr[now];

return cnt;

}

int build(int now,int l,int r)

{

now=++cnt;

if(l==r) return now;

int mid=(l+r)>>1;

tr[now].l=build(tr[now].l,l,mid);

tr[now].r=build(tr[now].r,mid+1,r);

return now;

}

int modify(int now,int l,int r,int x)

{

now=add(now);

if(l==r)

{

tr[now].w++;

return now;

}

tr[now].w++;

int mid=(l+r)>>1;

if(x<=mid) tr[now].l=modify(tr[now].l,l,mid,x);

else tr[now].r=modify(tr[now].r,mid+1,r,x);

return now;

}

int query(int vl,int vr,int l,int r,int x)

{

if(l==r) return l;

int mid=(l+r)>>1;

int k=tr[tr[vr].l].w-tr[tr[vl].l].w;

if(k>=x) return query(tr[vl].l,tr[vr].l,l,mid,x);

else return query(tr[vl].r,tr[vr].r,mid+1,r,x-k);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++) {scanf("%d",&a[i]);t[i]=a[i];}

sort(t+1,t+n+1);

int ll=unique(t+1,t+n+1)-t-1;

rt[0]=build(0,1,ll);

for(int i=1;i<=n;i++)

{

a[i]=lower_bound(t+1,t+ll+1,a[i])-t;

rt[i]=modify(rt[i-1],1,ll,a[i]);

}

for(int i=1;i<=m;i++)

{

int l,r,k;

scanf("%d%d%d",&l,&r,&k);

cout<

}

return 0;

}

线段树合并

#include

using namespace std;

const int N=5e6+5;

int x[N],y[N],z[N];

int n,m,head[N],cnt,mx,rt[N],tot,ans[N];

int sum[N],dep[N],fa[N],son[N],top[N];

struct node{

int nxt,to;

}e[N];

struct node1{

int tim,mx,l,r;

}tr[N];

void add(int u,int v){

e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

void dfs1(int x,int f)

{

dep[x]=dep[f]+1;fa[x]=f;sum[x]=1;

for(int i=head[x];i;i=e[i].nxt)

{

int v=e[i].to;

if(v==f) continue;

dfs1(v,x);

if(sum[v]>sum[son[x]]) son[x]=v;

sum[x]+=sum[v];

}

}

void dfs2(int x)

{

if(son[fa[x]]==x) top[x]=top[fa[x]];

else top[x]=x;

for(int i=head[x];i;i=e[i].nxt)

{

int v=e[i].to;

if(v==fa[x]) continue;

dfs2(v);

}

}

int lca(int x,int y)

{

while(top[x]!=top[y])

{

if(dep[top[x]]

x=fa[top[x]];

}

if(dep[x]

else return y;

}

int modify(int now,int l,int r,int x,int k)

{

if(!now) now=++tot;

if(l==r)

{

tr[now].tim+=k;

tr[now].mx=x;

//cout<<"qwq "<

return now;

}

int mid=(l+r)>>1;

if(x<=mid) tr[now].l=modify(tr[now].l,l,mid,x,k);

else tr[now].r=modify(tr[now].r,mid+1,r,x,k);

if(tr[tr[now].l].tim>=tr[tr[now].r].tim) {tr[now].tim=tr[tr[now].l].tim;tr[now].mx=tr[tr[now].l].mx;}

else {tr[now].tim=tr[tr[now].r].tim;tr[now].mx=tr[tr[now].r].mx;}

return now;

}

int merge(int a,int b,int l,int r)

{

if((!a)) return b;if((!b)) return a;

int mid=(l+r)>>1;

if(l==r)

{

tr[a].tim+=tr[b].tim;tr[a].mx=l;

return a;

}

tr[a].l=merge(tr[a].l,tr[b].l,l,mid);

tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);

if(tr[tr[a].l].tim>=tr[tr[a].r].tim) {tr[a].tim=tr[tr[a].l].tim;tr[a].mx=tr[tr[a].l].mx;}

else {tr[a].tim=tr[tr[a].r].tim;tr[a].mx=tr[tr[a].r].mx;}

return a;

}

void dfs3(int x)

{

for(int i=head[x];i;i=e[i].nxt)

{

int v=e[i].to;

if(v==fa[x]) continue;

dfs3(v);

rt[x]=merge(rt[x],rt[v],1,mx);

}

if(tr[rt[x]].tim) ans[x]=tr[rt[x]].mx;

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1,u,v;i

{

scanf("%d%d",&u,&v);

add(u,v);add(v,u);

}

for(int i=1;i<=m;i++)

{

scanf("%d%d%d",&x[i],&y[i],&z[i]);

mx=max(mx,z[i]);

}

dfs1(1,0);dfs2(1);

//for(int i=1;i<=n;i++) cout<

for(int i=1;i<=m;i++)

{

int l=lca(x[i],y[i]);

//cout<

rt[x[i]]=modify(rt[x[i]],1,mx,z[i],1);

rt[y[i]]=modify(rt[y[i]],1,mx,z[i],1);

rt[l]=modify(rt[l],1,mx,z[i],-1);

if(fa[l]) rt[fa[l]]=modify(rt[fa[l]],1,mx,z[i],-1);

}

dfs3(1);

for(int i=1;i<=n;i++) cout<

return 0;

}

李超线段树

#include

#define ls (now<<1)

#define rs (now<<1|1)

using namespace std;

typedef double db;

const int N=1e5+5;

const db eps=1e-9;

int n,lastans=0,cnt;

int tr[N<<2],ans;

db maxn;

struct node {db k,b;}a[N];

db gety(int id,db x){

if(id==0) return 0;

return a[id].k*x+a[id].b;

}

int readx(int x) {return (x+lastans-1)%39989+1;}

int ready(int x) {return (x+lastans-1)%1000000000+1;}

void modify(int now,int l,int r,int ml,int mr,int id)

{

int mid=(l+r)>>1;

if(l==ml&&r==mr)

{

int trw=tr[now];

if(gety(id,mid)>gety(tr[now],mid)) tr[now]=id;

if(gety(id,l)-gety(trw,l)>-eps&&gety(id,r)-gety(trw,r)>-eps) return;

else if(gety(id,l)-gety(trw,l)

if(gety(id,mid)>gety(trw,mid)) {modify(ls,l,mid,ml,mid,trw);modify(rs,mid+1,r,mid+1,mr,trw);}

else {modify(ls,l,mid,ml,mid,id);modify(rs,mid+1,r,mid+1,mr,id);}

}

if(mr<=mid) modify(ls,l,mid,ml,mr,id);

else if(ml>mid) modify(rs,mid+1,r,ml,mr,id);

else {modify(ls,l,mid,ml,mid,id);modify(rs,mid+1,r,mid+1,mr,id);}

}

void query(int now,int l,int r,int x)

{

int mid=(l+r)>>1;

if(gety(tr[now],x)>maxn||(gety(tr[now],x)==maxn&&tr[now]

if(l==r) return;

if(x<=mid) query(ls,l,mid,x);

else query(rs,mid+1,r,x);

}

int main()

{

scanf("%d",&n);

for(int i=1,op,xa,ya,xb,yb;i<=n;i++)

{

scanf("%d",&op);

if(op==0)

{

scanf("%d",&xa);xa=readx(xa);

maxn=0.0,ans=0;

query(1,1,40000,xa);

cout<

lastans=ans;

}

else

{

scanf("%d%d%d%d",&xa,&ya,&xb,&yb);

xa=readx(xa);xb=readx(xb);ya=ready(ya);yb=ready(yb);

if(xa>xb) {swap(xa,xb);swap(ya,yb);}

db k=0.0,b=0.0;

if(xa==xb) k=0.0,b=yb;

else

{

k=(db)(yb-ya)/(db)(xb-xa);

b=(db)yb-k*(db)xb;

}

a[++cnt]={k,b};

modify(1,1,40000,xa,xb,cnt);

}

}

return 0;

}

哈夫曼树

#include

#define int long long

#define pii pair

#define fi first

#define se second

using namespace std;

const int N=1e5+5;

int n,k,w[N],ans;

priority_queue,greater > q;

signed main()

{

scanf("%lld%lld",&n,&k);

for(int i=1;i<=n;i++)

{

scanf("%lld",&w[i]);

q.push(pii(w[i],0));

}

while((q.size()-1)%(k-1)) q.push(pii(0,0));

while(q.size()>1)

{

int sum=0,maxn=0;

for(int i=1;i<=k;i++)

{

if(q.empty()) break;

sum+=q.top().fi;

maxn=max(maxn,q.top().se);

q.pop();

}

ans+=sum;

q.push(pii(sum,maxn+1));

}

cout<

return 0;

}

笛卡尔树

#include

#define ll long long

using namespace std;

const int N=1e7+5;

inline int read()

{

int xr=0;char cr;

cr=getchar();

while(cr<'0'||cr>'9') cr=getchar();

while(cr>='0'&&cr<='9') xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();

return xr;

}

struct node{

int l,r;

}tr[N];

int n,a[N],w[N];

int q[N],st;

inline void build()

{

for(int i=1;i<=n;i++)

{

int x=a[i],now=0;

while(st&&a[q[st]]>x) now=q[st],st--;

if(st) tr[q[st]].r=i;

if(now) tr[i].l=now;

q[++st]=i;

}

}

signed main()

{

n=read();

for(int i=1;i<=n;i++) a[i]=read(),w[a[i]]=i;

build();

ll ansl=0,ansr=0;

for(int i=1;i<=n;i++)

{

ansl^=1ll*i*(tr[i].l+1);

ansr^=1ll*i*(tr[i].r+1);

//cout<

}

printf("%lld %lld",ansl,ansr);

//cout<

return 0;

}

左偏树（可并堆）

#define ls(x) tr[(x)].l

#define rs(x) tr[(x)].r

const int N=1e5+5;

int n,m;

struct node{

int val,id,dist;

int fa,l,r;

}tr[N];

int find(int x)

{

if(tr[x].fa==x) return x;

else return tr[x].fa=find(tr[x].fa);

}

int merge(int x,int y)

{

if(!x||!y) return x+y;

if(tr[x].val>tr[y].val||(tr[x].val==tr[y].val&&tr[x].id>tr[y].id)) swap(x,y);

rs(x)=merge(rs(x),y);

if(tr[ls(x)].dist

tr[x].dist=tr[rs(x)].dist+1;

return x;

}

bool flag[N];

int main()

{

n=read(),m=read();

for(int i=1;i<=n;i++) tr[i]={read(),i,1,i,0,0};

while(m--)

{

int op=read(),x=read();

if(op==1)

{

int y=read();

if(flag[x]||flag[y]) continue;

x=find(x),y=find(y);

if(x!=y) tr[x].fa=tr[y].fa=merge(x,y);

}

else

{

if(flag[x]) {printf("-1\n");continue;}

x=find(x),flag[x]=1;

printf("%d\n",tr[x].val);

tr[x].fa=tr[ls(x)].fa=tr[rs(x)].fa=merge(ls(x),rs(x));

}

}

return 0;

}

平衡树

Splay

const int N=1e5+5;

struct tree

{

int s[2],siz,fa,key;

tree(){s[0]=s[1]=siz=fa=key=0;}

}tr[N];

#define ls(x) tr[(x)].s[0]

#define rs(x) tr[(x)].s[1]

#define fa(x) tr[(x)].fa

int rt,idx;

il int newnode(int key) {tr[++idx].key=key,tr[idx].siz=1;return idx;}

il void maintain(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}

il void clear(int x) {ls(x)=rs(x)=fa(x)=tr[x].siz=tr[x].key=0;}

il bool get(int x) {return x==rs(fa(x));}

il void rotate(int x)

{

int y=fa(x),z=fa(y); int c=get(x);

if(tr[x].s[c^1]) fa(tr[x].s[c^1])=y;

tr[y].s[c]=tr[x].s[c^1],tr[x].s[c^1]=y,fa(y)=x,fa(x)=z;

if(z) tr[z].s[y==tr[z].s[1]]=x; //not get(y)!

maintain(y),maintain(x);

}

il void splay(int x)

{

for(int f=fa(x);f=fa(x),f;rotate(x))

if(fa(f)) rotate(get(f)==get(x)?f:x);

rt=x;

}

il void ins(int key)

{

int now=rt,f=0;

while(now) f=now,now=tr[now].s[key>tr[now].key];

now=newnode(key),fa(now)=f,tr[f].s[key>tr[f].key]=now,splay(now);

}

il void del(int key)

{

int now=rt,p=0;

while(tr[now].key!=key&&now) p=now,now=tr[now].s[key>tr[now].key];

if(!now) {splay(p);return;}

splay(now); int cur=ls(now);

if(!cur) {rt=rs(now),fa(rs(now))=0,clear(now);return;}

while(rs(cur)) cur=rs(cur);

rs(cur)=rs(now),fa(rs(now))=cur,fa(ls(now))=0,clear(now);

maintain(cur),splay(cur);

}

il int pre(int key)

{

int now=rt,ans=0,p;

while(now)

if(p=now,tr[now].key>=key) now=ls(now);

else ans=tr[now].key,now=rs(now);

return splay(p),ans;

}

il int nxt(int key)

{

int now=rt,ans=0,p;

while(now)

if(p=now,tr[now].key<=key) now=rs(now);

else ans=tr[now].key,now=ls(now);

return splay(p),ans;

}

il int rnk(int key)

{

int res=1,now=rt,p;

while(now)

if(p=now,tr[now].key

else now=ls(now);

return splay(p),res;

}

il int kth(int rk)

{

int now=rt;

while(now)

{

int sz=tr[ls(now)].siz+1;

if(sz>rk) now=ls(now);

else if(sz==rk) break;

else rk-=sz,now=rs(now);

}

return splay(now),tr[now].key;

}

Splay 区间翻转

const int N=1e5+5,inf=2e9;

struct tree

{

int s[2],siz,fa,key,lz;

tree(){s[0]=s[1]=siz=fa=key=lz=0;}

}tr[N];

#define ls(x) tr[(x)].s[0]

#define rs(x) tr[(x)].s[1]

#define fa(x) tr[(x)].fa

int rt,idx,a[N];

il int newnode(int key) {tr[++idx].key=key,tr[idx].siz=1;return idx;}

il void maintain(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}

il void clear(int x) {ls(x)=rs(x)=fa(x)=tr[x].siz=tr[x].key=0;}

il bool get(int x) {return x==rs(fa(x));}

il void rotate(int x)

{

int y=fa(x),z=fa(y); int c=get(x);

if(tr[x].s[c^1]) fa(tr[x].s[c^1])=y;

tr[y].s[c]=tr[x].s[c^1],tr[x].s[c^1]=y,fa(y)=x,fa(x)=z;

if(z) tr[z].s[y==tr[z].s[1]]=x; //not get(y)!

maintain(y),maintain(x);

}

il void splay(int x,int y)

{

for(int f=fa(x);f=fa(x),f!=y;rotate(x))

if(fa(f)!=y) rotate(get(f)==get(x)?f:x);

if(!y) rt=x;

}

il void pushdown(int x)

{

if(!tr[x].lz) return;

swap(ls(x),rs(x)),tr[ls(x)].lz^=1,tr[rs(x)].lz^=1;

tr[x].lz=0; return;

}

il int find(int x)

{

int now=rt; x++;

while(now)

{

pushdown(now); int sz=tr[ls(now)].siz+1;

if(sz==x) break;

else if(sz>x) now=ls(now);

else now=rs(now),x-=sz;

}

return now;

}

il void reverse(int l,int r)

{

int x=find(l-1); splay(x,0);

int y=find(r+1); splay(y,x);

tr[ls(y)].lz^=1;

}

void write(int now)

{

pushdown(now);

if(ls(now)) write(ls(now));

if(tr[now].key) printf("%d ",tr[now].key);

if(rs(now)) write(rs(now));

}

int n,m;

il void build()

{

rt=newnode(0); int now=rt;

for(int i=1;i<=n+1;i++)

tr[now].siz=n+3-i,rs(now)=newnode(a[i]),fa(rs(now))=now,now=rs(now);

}

int main()

{

n=read(),m=read();

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

build();

while(m--)

{

int l=read(),r=read();

reverse(l,r);

}

write(rt);

return 0;

}

FHQ Treap

#define ls(x) tr[(x)].l

#define rs(x) tr[(x)].r

const int N=1e5+5;

struct node {int l,r,key,val,siz;} tr[N];

int rt,idx,x,y,z;

il int add(int key) {tr[++idx]={0,0,key,rand(),1};return idx;}

il void upd(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}

void split(int now,int key,int &x,int &y)

{

if(!now) {x=y=0;return;}

if(tr[now].key<=key) x=now,split(rs(x),key,rs(x),y),upd(x);

else y=now,split(ls(y),key,x,ls(y)),upd(y);

}

int merge(int x,int y)

{

if(!x||!y) return x+y;

if(tr[x].val

else {ls(y)=merge(x,ls(y)),upd(y);return y;}

}

il void ins(int key) {split(rt,key,x,y),rt=merge(merge(x,add(key)),y);}

il void del(int key)

{

split(rt,key,y,z),split(y,key-1,x,y);

y=merge(ls(y),rs(y)),rt=merge(merge(x,y),z);

}

il int rnk(int key)

{

split(rt,key-1,x,y); int res=tr[x].siz+1;

rt=merge(x,y); return res;

}

il int kth(int rk)

{

int now=rt;

while(now)

{

int sz=tr[ls(now)].siz+1;

if(sz

else if(sz==rk) return tr[now].key;

else now=ls(now);

}

assert(false); return 0;

}

il int pre(int key)

{

split(rt,key-1,x,y); int now=x;

while(rs(now)) now=rs(now);

rt=merge(x,y); return tr[now].key;

}

il int nxt(int key)

{

split(rt,key,x,y); int now=y;

while(ls(now)) now=ls(now);

rt=merge(x,y); return tr[now].key;

}

FHQ Treap 区间翻转

#define ls(x) tr[(x)].l

#define rs(x) tr[(x)].r

const int N=1e5+5;

struct node{int l,r,val,key,siz,lz;} tr[N];

int rt,tot,x,y,z;

il void upd(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}

il void push_down(int now)

{

if(!tr[now].lz) return;

tr[now].lz=0,swap(ls(now),rs(now));

if(ls(now)) tr[ls(now)].lz^=1;

if(rs(now)) tr[rs(now)].lz^=1;

}

void split(int now,int rk,int &x,int &y)

{

if(!now) {x=y=0;return;}

push_down(now);

int qwq=tr[ls(now)].siz+1;

if(qwq<=rk) x=now,split(rs(now),rk-qwq,rs(x),y),upd(x);

else y=now,split(ls(now),rk,x,ls(y)),upd(y);

}

int merge(int x,int y)

{

push_down(x),push_down(y);

if(!x||!y) return x+y;

if(tr[x].val

else {ls(y)=merge(x,ls(y)),upd(y);return y;}

}

void print(int now)

{

push_down(now);

if(ls(now)) print(ls(now));

printf("%d ",tr[now].key);

if(rs(now)) print(rs(now));

}

void rev(int l,int r)

{

split(rt,r,y,z),split(y,l-1,x,y);

tr[y].lz=1;

rt=merge(merge(x,y),z);

}

Link Cut Tree

const int N=3e5+5;

struct node

{

int key,sum,fa,lz;

int s[2];

node() {key=sum=fa=lz=s[0]=s[1]=0;}

}tr[N];

#define ls(x) tr[(x)].s[0]

#define rs(x) tr[(x)].s[1]

#define fa(x) tr[(x)].fa

il bool get(int x) {return rs(fa(x))==x;}

il bool isroot(int x) {return ls(fa(x))!=x&&rs(fa(x))!=x;}

il void pushup(int x) {tr[x].sum=tr[ls(x)].sum^tr[rs(x)].sum^tr[x].key;}

il void pushdown(int x)

{

if(!tr[x].lz) return;

swap(ls(x),rs(x)),tr[ls(x)].lz^=1,tr[rs(x)].lz^=1;

tr[x].lz=0;

}

il void update(int x)

{

if(!isroot(x)) update(fa(x));

pushdown(x);

}

il void rotate(int x)

{

int y=fa(x),z=fa(y),c=get(x);

if(!isroot(y)) tr[z].s[get(y)]=x;

fa(tr[x].s[c^1])=y,tr[y].s[c]=tr[x].s[c^1],tr[x].s[c^1]=y;

fa(y)=x,fa(x)=z; pushup(y),pushup(x);

}

il void splay(int x)

{

update(x);

for(int f=fa(x);f=fa(x),!isroot(x);rotate(x))

if(!isroot(f)) rotate(get(f)==get(x)?f:x);

}

il void access(int x) {for(int p=0;x;p=x,x=fa(x)) splay(x),rs(x)=p,pushup(x);}

il void makeroot(int x) {access(x),splay(x),tr[x].lz^=1;}

il int find(int x)

{

access(x),splay(x);

while(pushdown(x),ls(x)) x=ls(x);

return splay(x),x;

}

il void link(int x,int y) {makeroot(x);if(find(y)!=x) fa(x)=y;}

il void split(int x,int y) {makeroot(x),access(y),splay(y);}

il void cut(int x,int y)

{

makeroot(x);

if(find(y)==x&&fa(y)==x&&!ls(y)) fa(y)=rs(x)=0;

}

字符串

Hash

const int p=131;

ull n,a[10005],ans;

string s;

ull hash(string x)

{

int l=x.size();

ull res=0;

for(int i=0;i<=l;i++) res=res*p+x[i];

return res;

}

Trie

struct trie{int nxt,s[26];} tr[N];

void ins(char *s)

{

int len=strlen(s+1),now=0;

for(int i=1;i<=len;i++)

{

int &to=tr[now].s[s[i]-'a'];

if(!to) to=++tot; now=to;

}

}

KMP

scanf("%s%s",t+1,s+1);

n=strlen(t+1),m=strlen(s+1);

for(int now=0,i=2;i<=m;i++)

{

while(now&&s[i]!=s[now+1]) now=nxt[now];

if(s[i]==s[now+1]) now++;

nxt[i]=now;

}

for(int now=0,i=1;i<=n;i++)

{

while(now&&s[now+1]!=t[i]) now=nxt[now];

if(s[now+1]==t[i]) now++;

if(now==m) printf("%d\n",i-m+1);

}

AC 自动机 (ACAM)

solve 函数省略，看具体题目

char s[N];

struct trie{int nxt,s[26];} d[N];

void ins(char *s)

{

int len=strlen(s+1),now=0;

for(int i=1;i<=len;i++)

{

int &to=d[now].s[s[i]-'a'];

if(!to) to=++tot; now=to;

}

}

void getfail()

{

queue q;

for(int i=0;i<26;i++) if(d[0].s[i]) q.push(d[0].s[i]);

while(!q.empty())

{

int u=q.front(); q.pop();

for(int i=0;i<26;i++)

{

if(!d[u].s[i]) d[u].s[i]=d[d[u].nxt].s[i];

else d[d[u].s[i]].nxt=d[d[u].nxt].s[i],q.push(d[u].s[i]);

}

}

}

Manacher

#include

using namespace std;

const int N=2.2e7+5;

int cnt=1,r[N],mid=1,R,maxn;

char s[N],c;

int main()

{

s[0]='~';s[1]='#';

c=getchar();

while(c<'a'||c>'z') c=getchar();

while(c>='a'&&c<='z') s[++cnt]=c,s[++cnt]='#',c=getchar();

for(int i=1;i<=cnt;i++)

{

if(i

while(s[i-r[i]]==s[i+r[i]]) r[i]++;

if(i+r[i]-1>=R) R=i+r[i]-1,mid=i;

maxn=max(maxn,r[i]-1);

}

cout<

return 0;

}

回文自动机 (PAM)

const int N=5e5+5;

int n,tot=1;

struct node

{

int len,fa,dep;

int s[26];

}d[N];

char s[N];

il int getfail(int u,int i)

{

while(i-d[u].len-1<=0||s[i-d[u].len-1]!=s[i]) u=d[u].fa;

return u;

}

int main()

{

scanf("%s",s+1); n=strlen(s+1);

d[0].fa=1,d[1].len=-1;

int now=0,lst=0;

for(int i=1;i<=n;i++)

{

s[i]=(s[i]-'a'+lst)%26+'a';

int pos=getfail(now,i); int c=s[i]-'a';

if(!d[pos].s[c])

{

d[++tot].fa=d[getfail(d[pos].fa,i)].s[c];

d[pos].s[c]=tot,d[tot].len=d[pos].len+2;

d[tot].dep=d[d[tot].fa].dep+1;

}

now=d[pos].s[c];

printf("%d ",lst=d[now].dep);

}

return 0;

}

后缀数组 (SA)

int n,m,sa[N],rk[N],sum[N],tp[N];

int hgt[N];

void qsort()

{

for(int i=1;i<=m;i++) sum[i]=0;

for(int i=1;i<=n;i++) sum[rk[i]]++;

for(int i=1;i<=m;i++) sum[i]+=sum[i-1];

for(int i=n;i;i--) sa[sum[rk[tp[i]]]--]=tp[i];

}

void SA()

{

for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;

m=200,qsort();

for(int w=1,tot=0;w<=n&&tot

{

tot=0;

for(int i=n-w+1;i<=n;i++) tp[++tot]=i;

for(int i=1;i<=n;i++)

if(sa[i]>w) tp[++tot]=sa[i]-w;

qsort(); swap(rk,tp);

tot=rk[sa[1]]=1;

for(int i=2;i<=n;i++)

rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?tot:++tot;

}

}

void get_hgt()

{

for(int i=1,now=0;i<=n;i++)

{

if(now) now--;

while(s[i+now]==s[sa[rk[i]-1]+now]) now++;

hgt[rk[i]]=now;

}

}

后缀自动机 (SAM)

void add(int c)

{

int p=lst,np=lst=++tot;f[tot]=1;

d[np].len=d[p].len+1;

for(;p&&!d[p].ch[c];p=d[p].fa) d[p].ch[c]=np;

if(!p) d[np].fa=1;

else

{

int q=d[p].ch[c];

if(d[q].len==d[p].len+1) d[np].fa=q;

else

{

int nq=++tot;

d[nq]=d[q];d[nq].len=d[p].len+1;

d[q].fa=d[np].fa=nq;

for(;p&&d[p].ch[c]==q;p=d[p].fa) d[p].ch[c]=nq;

}

}

}

广义 SAM

离线 bfs

struct trie{int fa,c,s[26];} tr[N];

int idx=1;

il void ins(char *s)

{

int len=strlen(s+1),now=1;

for(int i=1;i<=len;i++)

{

int &to=tr[now].s[s[i]-'a'];

if(!to) to=++idx,tr[to].fa=now,tr[to].c=s[i]-'a'; now=to;

}

}

struct SAM{int fa,len,s[26];} d[N];

int tot=1;

il int insert(int c,int lst)

{

int p=lst,np=lst=++tot; d[np].len=d[p].len+1;

for(;p&&!d[p].s[c];p=d[p].fa) d[p].s[c]=np;

if(!p) {d[np].fa=1;return np;}

int q=d[p].s[c];

if(d[q].len==d[p].len+1) {d[np].fa=q;return np;}

int nq=++tot; d[nq]=d[q],d[nq].len=d[p].len+1;

d[q].fa=d[np].fa=nq;

for(;p&&d[p].s[c]==q;p=d[p].fa) d[p].s[c]=nq;

return np;

}

int pos[N];

il void build()

{

queue q;

for(int i=0;i<26;i++) if(tr[1].s[i]) q.push(tr[1].s[i]);

pos[1]=1;

while(!q.empty())

{

int u=q.front(); q.pop();

pos[u]=insert(tr[u].c,pos[tr[u].fa]);

for(int i=0;i<26;i++) if(tr[u].s[i]) q.push(tr[u].s[i]);

}

}

在线构造

struct SAM{int fa,len,s[26];} d[N];

int tot=1,pos[N];

il int insert(int c,int lst)

{

if(d[lst].s[c]&&d[d[lst].s[c]].len==d[lst].len+1) {return d[lst].s[c];}

int p=lst,np=++tot,flag=0; d[np].len=d[p].len+1;

for(;p&&!d[p].s[c];p=d[p].fa) d[p].s[c]=np;

if(!p) {d[np].fa=1;return np;}

int q=d[p].s[c];

if(d[q].len==d[p].len+1) {d[np].fa=q;return np;}

if(p==lst) flag=1,np=0,tot--;

int nq=++tot; d[nq]=d[q],d[nq].len=d[p].len+1;

d[q].fa=d[np].fa=nq;

for(;p&&d[p].s[c]==q;p=d[p].fa) d[p].s[c]=nq;

return flag?nq:np;

}

计算几何

扫描线

#include

#define int long long

#define ls (now<<1)

#define rs (now<<1|1)

using namespace std;

const int N=3e5+5;

int n;

struct node{

int x,l,r,op;

}a[N];

int cnt,num,b[N],lz[N<<2];

struct node1{

int mn,cnt,l;

}tr[N<<2];

bool cmp(node x,node y){

return x.x

}

void push_down(int now)

{

tr[ls].mn+=lz[now];tr[rs].mn+=lz[now];

lz[ls]+=lz[now];lz[rs]+=lz[now];

lz[now]=0;

}

void build(int now,int l,int r)

{

tr[now].l=tr[now].cnt=b[r+1]-b[l];

if(l==r) return;

int mid=(l+r)>>1;

build(ls,l,mid);build(rs,mid+1,r);

}

void modify(int now,int l,int r,int ml,int mr,int op)

{

if(l==ml&&r==mr) tr[now].mn+=op,lz[now]+=op;return;}

int mid=(l+r)>>1;

push_down(now);

if(mr<=mid) modify(ls,l,mid,ml,mr,op);

else if(ml>mid) modify(rs,mid+1,r,ml,mr,op);

else

{

modify(ls,l,mid,ml,mid,op);

modify(rs,mid+1,r,mid+1,mr,op);

}

tr[now].mn=min(tr[ls].mn,tr[rs].mn);

tr[now].cnt=0;

if(tr[ls].mn==tr[now].mn) tr[now].cnt+=tr[ls].cnt;

if(tr[rs].mn==tr[now].mn) tr[now].cnt+=tr[rs].cnt;

}

int query(int now,int l,int r,int ml,int mr)

{

if(tr[now].mn!=0) return tr[now].l;

else return tr[now].l-tr[now].cnt;

}

signed main()

{

scanf("%lld",&n);

for(int i=1,xa,xb,ya,yb;i<=n;i++)

{

scanf("%lld%lld%lld%lld",&xa,&ya,&xb,&yb);

a[++cnt].x=xa,a[cnt].l=ya,a[cnt].r=yb,a[cnt].op=1;

a[++cnt].x=xb,a[cnt].l=ya,a[cnt].r=yb,a[cnt].op=-1;

b[++num]=ya,b[++num]=yb;

}

sort(b+1,b+num+1);

int len=unique(b+1,b+num+1)-b-1;

for(int i=1;i<=cnt;i++)

{

a[i].l=lower_bound(b+1,b+len+1,a[i].l)-b;

a[i].r=lower_bound(b+1,b+len+1,a[i].r)-b;

}

sort(a+1,a+cnt+1,cmp);

build(1,1,len-1);

int ans=0;

for(int i=1;i

{

modify(1,1,len-1,a[i].l,a[i].r-1,a[i].op);

ans+=query(1,1,len-1,1,len-1)*(a[i+1].x-a[i].x);

}

cout<

return 0;

}

平面最近点对

#include

#define int long long

using namespace std;

const int N=4e5+5;

typedef double db;

int n;db ans=1e18;

struct node{

db x,y;

}a[N],t[N];

bool cmpx(node c,node d)

{

if(c.x==d.x) return c.y

else return c.x

}

bool cmpy(node c,node d){

return c.y

}

db dis(node c,node d){

return (c.x-d.x)*(c.x-d.x)+(c.y-d.y)*(c.y-d.y);

}

void solve(int l,int r)

{

if(l==r) return;

int mid=(l+r)>>1;

db m=a[mid].x;

solve(l,mid);solve(mid+1,r);

int cnt=0;

for(int i=l;i<=r;i++)

{

if(a[i].x>=m-sqrt(ans)&&a[i].x<=m+sqrt(ans)) t[++cnt]=a[i];

}

sort(t+1,t+cnt+1,cmpy);

for(int i=1;i<=cnt;i++)

{

for(int j=i+1;j<=cnt;j++)

{

if(t[j].y>t[i].y+sqrt(ans)) break;

ans=min(ans,dis(t[j],t[i]));

}

}

}

signed main()

{

scanf("%lld",&n);

for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);

sort(a+1,a+n+1,cmpx);

solve(1,n);

cout<<(long long)ans<

return 0;

}

全家桶

typedef double db;

const db eps=1e-10;

struct V{

db x,y;

};

#define il inline

/*向量之间运算*/

il bool operator ==(const V &a,const V &b) {return fabs(a.x-b.x)<=eps&&fabs(a.y-b.y)<=eps;}

il bool operator !=(const V &a,const V &b) {return !(a==b);}

il V operator +(const V &a,const V &b) {return {a.x+b.x,a.y+b.y};}

il V operator -(const V &a,const V &b) {return {a.x-b.x,a.y-b.y};}

il V operator *(const V &a,const db &x) {return {a.x*x,a.y*x};}

il V operator *(const db &x,const V &a) {return {a.x*x,a.y*x};}

il V operator /(const V &a,const db &x) {return {a.x/x,a.y/x};}

il db operator *(const V &a,const V &b) {return a.x*b.x+a.y*b.y;}

il db operator ^(const V &a,const V &b) {return a.x*b.y-a.y*b.x;}

il db len(const V &a) {return sqrt(a*a);}

il V mid(const V &a,const V &b) {return {(a.x+b.x)/2,(a.y+b.y)/2};}

il V cui(const V &a) {return {a.y,-a.x};}

il V dw(const V &a) {return a/len(a);}

/*角度*/

il db tri_S(const V &a,const V &b,const V &c) {return fabs((a-c)^(b-c))/2;}

il db angle(const V &a,const V &b) {return acos(a*b/len(a)/len(b));}

//以下均为角 BAC.

il bool zhi(const V &a,const V &v,const V &c) {return fabs((b-a)*(c-a))<=eps;}

il bool dun(const V &a,const V &b,const V &c) {return (b-a)*(c-a)<-eps;}

il bool rui(const V &a,const V &b,const V &c) {return (b-a)*(c-a)>eps;}

il V turn(const V &a,db t){

db s=sin(t),c=cos(t);

return {a.x*c-a.y*s,a.x*s+a.y*c};

}

/*线*/

struct line{

V d,a,b;

};

inline line trans(db a,db b,db c,db d)

{

V dd={c-a,d-b},x={a,b},y={c,d};

dd=dw(dd);

return {dd,x,y};

}

inline line trans(const V &a,const V &b)

{

V dd={b.x-a.x,b.y-a.y};dd=dw(dd);

return {dd,a,b};

}

/*点和线的关系*/

il V cui(const V &o,const line &l) {return ((o-l.a)*l.d)*l.d+l.a;}

il V duichen(const V &o,const line &l)

{

V qwq=cui(o,l);

return {2*qwq.x-o.x,2*qwq.y-o.y};

}

il db dis(const V &o,const line &l,int op=0)

{

if(op&&(dun(l.a,o,l.b)||dun(l.b,o,l.a))) return min(len(l.a-o),len(l.b-o));

else return fabs((l.a-o)^(l.b-o))/len(l.b-l.a);

}

il bool on_line(const line &l,const V &o) {return fabs((o-l.a)^(l.b-l.a))

il bool on_seg(const line &l,const V &o) {return fabs(len(o-l.a)+len(o-l.b)-len(l.b-l.a))

il int pos(const line &l,const V &o)

{

if(!on_line(l,o))

{

if((o-l.a)^l.d<-eps) return 1;//clockwise

else return 2;//counter clockwise

}

if((o-l.a)*(o-l.b)<-eps) return 5;//on

else if(len(o-l.a)>len(o-l.b)) return 3;//front

else return 4;//back

}

/*线和线*/

//线和线

il bool gongxian(const line &a,const line &b) {return fabs(a.d^b.d)

il bool cuizhi (const line &a,const line &b) {return fabs(a.d*b.d)

il bool xdjiao(const line &u,const line &v)//拼音太长缩写了>_<

{

if(min(u.a.x,u.b.x)>max(v.a.x,v.b.x)+eps||max(u.a.x,u.b.x)

if(min(u.a.y,u.b.y)>max(v.a.y,v.b.y)+eps||max(u.a.y,u.b.y)

return ((u.a-v.a)^v.d)*((u.b-v.a)^v.d)

}

il V jiaodian(const line &u,const line &v)

{

double k=((v.a-u.a)^v.d)/(u.d^v.d);

return k*u.d+u.a;

}

il line pingfen(const V &a,const V &b,const V &c)//角 BAC

{

int d1=dw(b-a),d2=dw(c-a);

int d=(d1+d2)/2;

return (line){d,a,a+d};

}

/*多边形*/

il int in_poly(V *a,int n,V o)

{

int res=0;a[n+1]=a[1];

for(int i=1;i<=n;i++)

{

V u=a[i],v=a[i+1];

if(on_seg(trans(u,v),o)) return 1;

if(abs(u.y-v.y)

if(max(u.y,v.y)

if(min(u.y,v.y)>o.y-eps) continue;

double x=u.x+(o.y-u.y)/(v.y-u.y)*(v.x-u.x);

if(x

}

return res?2:0;

}

il double S(V *a,int n)

{

db res=0;

for(int i=1;i<=n;i++) res+=(a[i]^a[i%n+1]);

return res/2;

}

il int is_convex(V *a,int n)

{

a[0]=a[n],a[n+1]=a[1];

int op=0;

for(int i=1;i<=n;i++)

{

V x=a[i]-a[i-1],y=a[i+1]-a[i];

if(abs(x^y)

int np=((x^y)>0)?1:-1;

if(!op) op=np;

else if(op!=np) return 0;

}

return 1;

}

/*凸包*/

V Q[N];int tp;

bool cmp(V a,V b)

{

if(a.x==b.x) return a.y

else return a.x

}

void andrew(V *a,int n)

{

sort(a+1,a+n+1,cmp);

Q[++tp]=a[1];

for(int i=2;i<=n;Q[++tp]=a[i],i++)

while(tp>1&&((Q[tp]-Q[tp-1])^(a[i]-Q[tp]))

int pos=tp;

for(int i=n-1;i;Q[++tp]=a[i],i--)

while(tp>pos&&((Q[tp]-Q[tp-1])^(a[i]-Q[tp]))

tp--;

}

/*旋转卡壳*/

int ans;

void find()

{

int now=2;

for(int i=1;i<=tp;i++)

{

V a=Q[i],b=Q[i%tp+1];

while(Dis(a,b,Q[now%tp+1])>Dis(a,b,Q[now])) now=now%tp+1;

ans=max(ans,dis(a,Q[now]));

ans=max(ans,dis(b,Q[now]));

}

}

/*半平面交*/

struct line

{

V a,b,d;

double angle;

}a[N];

line trans(V a,V b)

{

double res=atan2((b-a).y,(b-a).x);V d=(b-a)/len(b-a);

return {a,b,d,res};

}

V jiaodian(line a,line b)

{

double k=((b.a-a.a)^(b.d))/(a.d^b.d);

return a.a+(k*a.d);

}

bool cmp(line x,line y)

{

if(fabs(x.angle-y.angle)>eps) return x.angle

else return ((y.a-x.a)^(y.b-x.a))>eps;

}

bool check(line a,line b,line c)

{

V p=jiaodian(b,c);

return (a.d^(p-a.a))<-eps;

}

line Q[N];

int h=1,t=0,tot;

V ans[N];

void solve()

{

sort(a+1,a+tot+1,cmp);

int cnt=1;

for(int i=2;i<=tot;i++)

if(fabs(a[i].angle-a[i-1].angle)>eps) a[++cnt]=a[i];

tot=cnt;

Q[++t]=a[1],Q[++t]=a[2];

for(int i=3;i<=tot;i++)

{

while(h

while(h

Q[++t]=a[i];

}

while(h

while(h

int qwq=0;

for(int i=h;i

if(t-h>1) ans[++qwq]=jiaodian(Q[h],Q[t]);

tot=qwq;

}

int main()

{

int n=read();tot=0;

for(int i=1;i<=n;i++)

{

int m=read();

for(int j=1;j<=m;j++)

b[j].x=read(),b[j].y=read();

for(int j=1;j<=m;j++) a[++tot]=trans(b[j],b[j%m+1]);

}

solve();

double res=0;

for(int i=1;i<=tot;i++) res+=(ans[i]^ans[i%tot+1]);

printf("%.3lf\n",res/2);

return 0;

}

更新日志

2020/04/19 一代初稿

2021/01/29 二代初稿

2022/08/15 几乎重构了整篇文章。

2023/02/14 重构了一些数据结构板子。

2023/10/19 再次重构，优化模板代码的可迁移性，删除了部分过于基础的模板。

重写了几乎所有的代码，现在应该能保证正确性，且码风差不多统一了。

缺什么东西可以评论区把 yxcat 抓回来加。