当前位置: 首页 > news >正文

OI 模板合集

输入输出优化

int 快读

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 快读

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<bits/stdc++.h>
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<<j)*W,c[cnt]=(1<<j)*C;w[++cnt]=W*(m-((1<<j)-1)),c[cnt]=C*(m-((1<<j)-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<<f[t]<<endl;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<int> q;
int in[N],dis[N];
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];
bool spfa(int s)
{queue<int> 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<pii,vector<pii>,greater<pii> >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<int> 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<int> q;
vector<int> 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<int> q;
vector<int> 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<int> 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 最大流

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<int> q;
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&&sum;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<int> 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<int> 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&&sum;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<int> 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&&sum;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<b.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<pii,vector<pii>,greater<pii> >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]<dep[y]) swap(x,y);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);
}
int lca(int x,int y)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);x=fa[top[x]];}return dep[x]<dep[y]?x:y;
}
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];
int get(int x,int y) {return dep[x]<dep[y]?x:y;}
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<<i)+1;j++) st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-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<<len)+1]);
}

树上 k 级祖先

vector<int> 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);
}
int kfa(int x,int k)
{if(!k) return x;x=f[highbit[k]][x],k^=(1<<highbit[k]),k-=dep[x]-dep[top[x]],x=top[x];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];
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<int> 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);
}
void addline(int x,int y,int k)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);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);
}
int queryline(int x,int y)
{int res=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);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;
}
void addsub(int x,int k) {seg.modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);}
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<n;i++) fa[i]=read(),son[fa[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]<j) a[i+1]=fa[a[i]],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<n;i++,j++){while(son[j]) j++;fa[j]=a[i];while(i<n&&!(--son[a[i]])&&a[i]<j) fa[a[i]]=a[i+1],i++;}int ans=0;for(int i=1;i<n;i++) ans^=i*fa[i];printf("%lld\n",ans);}
}

其他

欧拉回路

stack<int> 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;
}

矩阵快速幂

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])<eps) {printf("No Solution\n");exit(0);}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];
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)
{if(x==2||x==4) return 1;if(x%2==0) x/=2;if(x%2==0) return 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<int,int> 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<p) 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<bits/stdc++.h>
#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;}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<<ans.f%mod<<" "<<ans.h%mod<<" "<<ans.g%mod<<endl;}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];
Complex operator +(Complex a,Complex b) {return {a.x+b.x,a.y+b.y};}
Complex operator -(Complex a,Complex b) {return {a.x-b.x,a.y-b.y};}
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<limit;i++) if(i<to[i]) swap(a[i],a[to[i]]);for(int len=1;len<limit;len<<=1){Complex Wn={cos(pi/len),sin(pi/len)*tp};for(int i=0;i<limit;i+=(len<<1)){Complex w={1,0};for(int j=0;j<len;j++,w=w*Wn){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<limit;i++) to[i]=(to[i>>1]>>1)|((i&1)<<(k-1));FFT(a,1),FFT(b,1);for(int i=0;i<limit;i++) a[i]=a[i]*b[i];FFT(a,-1);for(int i=0;i<=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;
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];
void NTT(int *a,int tp)
{for(int i=0;i<limit;i++) if(i<to[i]) swap(a[i],a[to[i]]);for(int len=1;len<limit;len<<=1){int Wn=qpow(tp>0?3:inv,(mod-1)/(len<<1));for(int i=0;i<limit;i+=(len<<1))for(int j=0,w=1;j<len;j++,w=w*Wn%mod){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<limit;i++) to[i]=(to[i>>1]>>1)|((i&1)<<(k-1));NTT(a,1),NTT(b,1);for(int i=0;i<limit;i++) a[i]=a[i]*b[i]%mod;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<<n);len<<=1)for(int i=0;i<(1<<n);i+=(len<<1))for(int j=0;j<len;j++) add(a[i+j+len],a[i+j]*tp);
}
void And(int *a,int tp)
{for(int len=1;len<(1<<n);len<<=1)for(int i=0;i<(1<<n);i+=(len<<1))for(int j=0;j<len;j++) add(a[i+j],a[i+j+len]*tp);
}
void Xor(int *a,int tp)
{for(int len=1;len<(1<<n);len<<=1)for(int i=0;i<(1<<n);i+=(len<<1))for(int j=0;j<len;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]);}
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--)
{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<<ans[i]<<" ";

单调队列

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

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<<i)+1;j++) st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-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<<len)+1]));
}

树状数组

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

struct BIT
{int tr[N];void add(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}int ask(int l,int r) {return query(r)-query(l-1);}
}tr;

区间加单点求和

struct BIT
{int tr[N];void modify(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}void add(int l,int r,int k) {modify(l,k),modify(r+1,-k);} 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)
void pushup(int now) {tr[now]=tr[ls]+tr[rs];}
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)
void add(int &x,int y) {x+=y;x%=mod;}
void pushup(int now) {tr[now]=(tr[ls]+tr[rs])%mod;}
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;
}
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<bits/stdc++.h>
#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<<query(rt[v],1,n,x)<<endl;rt[i]=rt[v];}}return 0;
}

可持久化权值线段树(主席树 2)

求的是静态区间 k 小值。

#include<bits/stdc++.h>
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<<t[query(rt[l-1],rt[r],1,ll,k)]<<endl;}return 0;
}

线段树合并

#include<bits/stdc++.h>
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]]<dep[top[y]]) swap(x,y);x=fa[top[x]];}if(dep[x]<dep[y]) return 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;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<n;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<=m;i++){int l=lca(x[i],y[i]);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<<ans[i]<<"\n";return 0;
}

李超线段树

#include<bits/stdc++.h>
#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)<eps&&gety(id,r)-gety(trw,r)<eps) return;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]<ans)) ans=tr[now],maxn=gety(tr[now],x);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<<ans<<endl;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<bits/stdc++.h>
#define int long long
#define pii pair<long long,long long>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,k,w[N],ans;
priority_queue<pii,vector<pii>,greater<pii> > 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<<ans<<"\n"<<q.top().se<<endl;return 0;
}

笛卡尔树

#include<bits/stdc++.h>
#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);}printf("%lld %lld",ansl,ansr);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[rs(x)].dist) swap(ls(x),rs(x));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;
int newnode(int key) {tr[++idx].key=key,tr[idx].siz=1;return idx;}
void maintain(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
void clear(int x) {ls(x)=rs(x)=fa(x)=tr[x].siz=tr[x].key=0;}
bool get(int x) {return x==rs(fa(x));}
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; maintain(y),maintain(x);
}
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;
}
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);
}
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);
}
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;
}
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;
}
int rnk(int key)
{int res=1,now=rt,p;while(now)if(p=now,tr[now].key<key) res+=tr[ls(now)].siz+1,now=rs(now);else now=ls(now);return splay(p),res;
}
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];
int newnode(int key) {tr[++idx].key=key,tr[idx].siz=1;return idx;}
void maintain(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
void clear(int x) {ls(x)=rs(x)=fa(x)=tr[x].siz=tr[x].key=0;}
bool get(int x) {return x==rs(fa(x));}
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; maintain(y),maintain(x);
}
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;
}
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;
}
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;
}
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;
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;
int add(int key) {tr[++idx]={0,0,key,rand(),1};return idx;}
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<tr[y].val) {rs(x)=merge(rs(x),y),upd(x);return x;}else {ls(y)=merge(x,ls(y)),upd(y);return y;}
}
void ins(int key) {split(rt,key,x,y),rt=merge(merge(x,add(key)),y);}
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);
}
int rnk(int key)
{split(rt,key-1,x,y); int res=tr[x].siz+1;rt=merge(x,y); return res;
}
int kth(int rk)
{int now=rt;while(now){int sz=tr[ls(now)].siz+1;if(sz<rk) rk-=sz,now=rs(now);else if(sz==rk) return tr[now].key;else now=ls(now);}assert(false); return 0;
}
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;
}
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;
void upd(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
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<tr[y].val) {rs(x)=merge(rs(x),y),upd(x);return x;}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);
}
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
bool get(int x) {return rs(fa(x))==x;}
bool isroot(int x) {return ls(fa(x))!=x&&rs(fa(x))!=x;}
void pushup(int x) {tr[x].sum=tr[ls(x)].sum^tr[rs(x)].sum^tr[x].key;}
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;
}
void update(int x)
{if(!isroot(x)) update(fa(x));pushdown(x);
}
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);
}
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);
}
void access(int x) {for(int p=0;x;p=x,x=fa(x)) splay(x),rs(x)=p,pushup(x);}
void makeroot(int x) {access(x),splay(x),tr[x].lz^=1;}
int find(int x)
{access(x),splay(x);while(pushdown(x),ls(x)) x=ls(x);return splay(x),x;
}
void link(int x,int y) {makeroot(x);if(find(y)!=x) fa(x)=y;}
void split(int x,int y) {makeroot(x),access(y),splay(y);}
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<int> 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<bits/stdc++.h>
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<R) r[i]=min(R-i+1,r[2*mid-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<<maxn<<endl;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];
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<n;w<<=1,m=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;
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;
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];
void build()
{queue<int> 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];
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<bits/stdc++.h>
#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<y.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<cnt;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<<ans<<endl;return 0;
}

平面最近点对

#include<bits/stdc++.h>
#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<d.y;else return c.x<d.x;
}
bool cmpy(node c,node d){return c.y<d.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<<endl;return 0;
}

全家桶

typedef double db;
const db eps=1e-10;
struct V{db x,y;
};
#define inlinebool operator ==(const V &a,const V &b) {return fabs(a.x-b.x)<=eps&&fabs(a.y-b.y)<=eps;}  
bool operator !=(const V &a,const V &b) {return !(a==b);}V operator +(const V &a,const V &b) {return {a.x+b.x,a.y+b.y};}
V operator -(const V &a,const V &b) {return {a.x-b.x,a.y-b.y};}
V operator *(const V &a,const db &x) {return {a.x*x,a.y*x};}
V operator *(const db &x,const V &a) {return {a.x*x,a.y*x};}
V operator /(const V &a,const db &x) {return {a.x/x,a.y/x};}db operator *(const V &a,const V &b) {return a.x*b.x+a.y*b.y;} 
db operator ^(const V &a,const V &b) {return a.x*b.y-a.y*b.x;}db len(const V &a) {return sqrt(a*a);}
V  mid(const V &a,const V &b) {return {(a.x+b.x)/2,(a.y+b.y)/2};}
V  cui(const V &a) {return {a.y,-a.x};}
V   dw(const V &a) {return a/len(a);}db tri_S(const V &a,const V &b,const V &c) {return fabs((a-c)^(b-c))/2;}
db angle(const V &a,const V &b) {return acos(a*b/len(a)/len(b));}bool zhi(const V &a,const V &v,const V &c) {return fabs((b-a)*(c-a))<=eps;} 
bool dun(const V &a,const V &b,const V &c) {return (b-a)*(c-a)<-eps;}
bool rui(const V &a,const V &b,const V &c) {return (b-a)*(c-a)>eps;}
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};
}V cui(const V &o,const line &l) {return ((o-l.a)*l.d)*l.d+l.a;}
V duichen(const V &o,const line &l)
{V qwq=cui(o,l);return {2*qwq.x-o.x,2*qwq.y-o.y};
}
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);
}
bool on_line(const line &l,const V &o) {return fabs((o-l.a)^(l.b-l.a))<eps;}
bool on_seg(const line &l,const V &o) {return fabs(len(o-l.a)+len(o-l.b)-len(l.b-l.a))<eps;}
int pos(const line &l,const V &o)
{if(!on_line(l,o)) {if((o-l.a)^l.d<-eps) return 1;else return 2;}if((o-l.a)*(o-l.b)<-eps) return 5;else if(len(o-l.a)>len(o-l.b)) return 3;else return 4;
}bool gongxian(const line &a,const line &b) {return fabs(a.d^b.d)<eps;}
bool cuizhi  (const line &a,const line &b) {return fabs(a.d*b.d)<eps;} 
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)<min(v.a.x,v.b.x)-eps) return 0;if(min(u.a.y,u.b.y)>max(v.a.y,v.b.y)+eps||max(u.a.y,u.b.y)<min(v.a.y,v.b.y)-eps) return 0;return ((u.a-v.a)^v.d)*((u.b-v.a)^v.d)<eps&&((v.a-u.a)^u.d)*((v.b-u.a)^u.d)<eps;
}
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;
}
line pingfen(const V &a,const V &b,const V &c)
{int d1=dw(b-a),d2=dw(c-a);int d=(d1+d2)/2;return (line){d,a,a+d};
}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)<eps) continue;if(max(u.y,v.y)<o.y-eps) continue;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<o.x) res^=1;}return res?2:0;
}
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;
}
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)<eps) continue;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<b.y;else return a.x<b.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]))<eps) 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]))<eps) 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<y.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<t&&check(a[i],Q[t],Q[t-1])) t--;while(h<t&&check(a[i],Q[h],Q[h+1])) h++;Q[++t]=a[i];}while(h<t&&check(Q[h],Q[t],Q[t-1])) t--;while(h<t&&check(Q[t],Q[h],Q[h+1])) h++;int qwq=0;for(int i=h;i<t;i++) ans[++qwq]=jiaodian(Q[i],Q[i+1]);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;
}
http://www.hskmm.com/?act=detail&tid=19860

相关文章:

  • 实用指南:【分布式】分布式事务方案:两阶段、TCC、SEATA
  • Storm-0501威胁组织利用云技术实施勒索攻击的技术分析
  • 模型插入 NV12 预处理节点精度问题排查流程
  • 【ARM Cache与 MMU 系列文章 7 – ARMv8v9 MMU 页表配置 01 】
  • 完整教程:【开题答辩过程】以《SpringMVC在筑原平面设计定制管理信息系统的应用与实践》为例,不会开题答辩的可以进来看看
  • 接雨水
  • 非线性规划、最优控制与多目标优化
  • 记录,结构,枚举,ref,in和out 元组
  • Gitee企业版MCP Server:开启AI驱动的企业研发新时代
  • Flutter - dart 语言从入门到精通 - 教程
  • 哈夫曼编码例题
  • Deepoc具身智能模型:为传统电厂巡检机器人注入“灵魂”与“智慧” - 实践
  • Win11共享打印0x0000bc4,三步解决共享难题
  • kafka-日志收集高效的平台部署任务
  • python第三天
  • iOS Xcode16 中删除描述文件 Provisioning Profiles
  • git仓库管理memo
  • 全国主要城市温度舒适度榜:谁在天堂,谁在蒸笼
  • 电桥采集模块 24位ADC+128倍可调增益 高精度测量支持多接口输出
  • ubuntu 系统启动服务及服务依赖
  • Jira停售Data Center尘埃落定!中国企业迁移需落实的6大关键项目管理工具清单
  • 【Cursor/Vscode】SSH免密登录 - 教程
  • python 超长代码行如何换行,符合PEP 8规范?
  • Gitee崛起:中国开发者迎来本土化研发平台新纪元
  • 关键领域软件研发知识管理的范式革命:从静态文档到智能图谱的跃迁
  • 【IEEE出版、曾获中国科协认证】第六届机械工程、智能制造与自动化技术国际学术会议 (MEMAT 2025)
  • 时间同步NTP服务
  • 【WCH蓝牙系列芯片】-基于CH585开发板—IO口(GPIO)外部中断唤醒蓝牙睡眠模式
  • 【2025-09-26】奋斗逻辑
  • 【Linux基础知识系列:第一百四十篇】理解SELinux与系统安全 - 教程