模板集

考虑到作为一名 Oier 有很多需要掌握的模板，所以整合了一下以前的专栏，就变成现在这样了！

有问题请加 qq 3848603482。可以帮你讲解。

给萌新的代码建议

尽量不要写全局变量，容易弄混不方便调试，要用了再创建。没有必要手写栈之类的，STL要了解多一点。不要写#define int long long，大忌。
（当然我有一些远古模版没有遵循以上基本原则，之后会改，请谅解）。

建图

链式前向星。

坏处是容易 MLE，好处是可以按边操作。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=5e5+10;
int n,m,u,v,w;
int cnt,h[N],d[N];
struct node{int nxt,to,dis;
}e[M];
void add(int u,int v,int w){ e[++cnt].nxt=h[u];e[cnt].to=v;e[cnt].dis=w;h[u]=cnt;
}
int main(){cin>>n>>m;while(m--){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}return 0;
}

vector。

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+10;
int n,m,u,v,w;
vector<pair<int,int> >G[M];
#define mp make_pair
int main(){cin>>n>>m;while(m--){cin>>u>>v>>w;G[u].push_back(mp(v,w));G[v].push_back(mp(u,w));}return 0;
}

邻接矩阵。

空间复杂度高，节点数量不能太多。

Spfa

bool spfa(int s){memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;q.push(s);vis[s]=1;cnt[s]++;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<G[u].size();i++){int v=G[u][i].first;int w=G[u][i].second;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!vis[v]){q.push(v);vis[v]=1;cnt[v]++;if(cnt[v]>n)return 0;}}}}return 1;
}

矩阵乘法

B2105 矩阵乘法

#include<bits/stdc++.h>
using namespace std;
int n,m,k; 
int a[110][110];
int b[110][110];
int c[110][110];
int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=m;i++){for(int j=1;j<=k;j++){cin>>b[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){for(int s=1;s<=m;s++){c[i][j]+=a[i][s]*b[s][j];}}}for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){cout<<c[i][j]<<" ";}cout<<"\n";}return 0;
}

Floyd

时间复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
//建变量 
int main(){//输入 //邻接矩阵初始化memset(g,0x3f,sizeof(g));//建图 for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){	 g[i][j]=min(g[i][j],g[i][k]+g[k][j]);} }}//g[a][b]为无穷大则两点不联通，否则表示a->b的最小值 return 0;
} 

拓扑排序

【模板】拓扑排序

这个是用邻接表写的形式，当然也可以用数组。

拓扑排序思路：

• 计算每个点的入度，用数组 in 存下来。
• 入度为 \(0\) 就推入队。
• 循环，当队列不空。
• 输出队首，弹出这个点并遍历它的连边。把连向的每个节点入度减 \(1\)。
• 如果哪个节点入度减 \(1\) 后等于 \(0\) 就再次入队。

#include<bits/stdc++.h>
using namespace std;
vector<int>G[5010];
queue<int>q;
int n,son,in[5010];
void toposort(){for(int i=1;i<=n;i++){if(in[i]==0){cout<<i<<" ";q.push(i);}}while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<G[x].size();i++){int to=G[x][i];in[to]--;if(in[to]==0){cout<<to<<" ";q.push(to);}}}
}
int main(){cin>>n;for(int i=1;i<=n;i++){while(cin>>son&&son!=0){G[i].push_back(son);in[son]++;}}toposort();return 0;
}

LCA

P3379 【模板】最近公共祖先。

倍增。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s;
int x,y,a,b;
const int N=5e5+10;
vector<int>G[N];
int anc[N][25];
void init(){for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){anc[i][j]=anc[anc[i][j-1]][j-1];}}
}
int d[N];
void dfs(int u,int fa){for(int i=0;i<G[u].size();i++){int v=G[u][i];if(v==fa)continue;d[v]=d[u]+1;anc[v][0]=u;dfs(v,u);}
}
int lca(int u,int v){if(d[u]<d[v])swap(u,v);for(int i=20;i>=0;i--){if(d[anc[u][i]]>=d[v]){u=anc[u][i];}}if(u==v)return u;for(int i=20;i>=0;i--){if(anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];}}return anc[u][0];
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}d[s]=1;dfs(s,0);init();while(m--){cin>>a>>b;cout<<lca(a,b)<<"\n";}return 0;
} 

写法2。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,x,y,a,b;
int d[N],anc[N][110];
vector<int>G[N];
void init(){for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){anc[i][j]=anc[anc[i][j-1]][j-1];}}
}
void dfs(int u,int fa){for(int i=0;i<G[u].size();i++){int v=G[u][i];if(v==fa)continue;d[v]=d[u]+1;anc[v][0]=u;dfs(v,u);}
}
int LCA(int u,int v){if(d[u]<d[v])swap(u,v);int t=d[u]-d[v];for(int i=20;i>=0;i--){if(t&(1<<i)){u=anc[u][i];}}if(u==v)return u;for(int i=20;i>=0;i--){if(anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];}}return anc[u][0];
}
int main(){cin>>n>>m>>s;for(int i=1;i<n;i++){cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}d[s]=1;dfs(s,0);init();while(m--){cin>>a>>b;cout<<LCA(a,b)<<"\n";}return 0;
}

树剖。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,x,y,a,b;
int h[N],cnt;
struct node{int to,nxt;
}e[N];
void add(int u,int v){e[++cnt].nxt=h[u];e[cnt].to=v;h[u]=cnt;
}
int d[N],sz[N];
int son[N],wc[N],f[N];
void dfs(int u,int fa){sz[u]=1;d[u]=d[fa]+1;f[u]=fa;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa)continue;dfs(v,u);sz[u]+=sz[v];if(!wc[u]||sz[wc[u]]<sz[wc[v]]){wc[u]=v;}}
}
int tp[N];
void dfs2(int u,int top){tp[u]=top;if(wc[u])dfs2(wc[u],top);for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==f[u]||v==wc[u])continue;dfs2(v,v);}
}
int lca(int a,int b){while(tp[a]!=tp[b]){if(d[tp[a]]>=d[tp[b]])a=f[tp[a]];else b=f[tp[b]];}if(d[a]<d[b])return a;else return b;
}
int main(){cin>>n>>m>>s;for(int i=1;i<n;i++){cin>>x>>y;add(x,y);add(y,x);}dfs(s,0);dfs2(s,s);while(m--){cin>>a>>b;cout<<lca(a,b)<<"\n";}return 0;
}

LCA的tarjan算法

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,u,v,s,fa[N],ans[N];
vector<int>g[N];
vector<pair<int,int> >q[N];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void dfs(int u,int f){for(int v:g[u]){if(v!=f)dfs(v,u);}for(auto[v,id]:q[u]){if(!ans[id])ans[id]=-1;else if(ans[id]==-1)ans[id]=find(v);}fa[u]=f;
}
int main(){cin>>n>>m>>s;for(int i=1;i<n;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}	for(int i=1;i<=m;i++){int u,v;cin>>u>>v;q[u].push_back(v,i);q[v].push_back(u,i);}	for(int i=1;i<=n;i++)fa[i]=i;dfs(s,0);for(int i=1;i<=m;i++)cout<<ans[i]<<" ";return 0;
}

Kruskal

P3366 【模板】最小生成树。

时间复杂度\(O(mlogm)\)，适用于稀疏图。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,cnt,fa[N];
long long ans;
struct node{int u,v,w;
}e[N];
int find(int x){if(x==fa[x])return x;return find(fa[x]);
}
bool cmp(node a,node b){return a.w<b.w;
}
void kruskal(){sort(e+1,e+m+1,cmp);for(int i=1;i<=m;i++){int x=find(e[i].u);int y=find(e[i].v);if(x==y)continue;fa[x]=y;ans+=e[i].w;cnt++;}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;}kruskal();if(cnt==n-1)cout<<ans;else cout<<"orz";return 0;
} 

prim

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
#define p pair<int,int>
struct node{int nxt,to,dis;
}e[N];
int a,b,c;
int n,m,tot,ans;
int h[N],cnt,d[N];
bool vis[N];
priority_queue<p,vector<p>,greater<p> >q; 
void add(int u,int v,int w){e[++cnt].nxt=h[u];e[cnt].to=v;e[cnt].dis=w;h[u]=cnt;
}
void prim(){memset(d,0x3f,sizeof(d));d[1]=0;q.push(make_pair(0,1));while(!q.empty()&&tot<n){int dis=q.top().first;int u=q.top().second;q.pop();if(vis[u])continue;tot++;vis[u]=1;ans+=dis;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;int w=e[i].dis;if(d[v]>w){d[v]=w;q.push(make_pair(d[v],v));}}}
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>a>>b>>c;add(a,b,c);add(b,a,c);}prim();if(tot==n)cout<<ans;else cout<<"orz";return 0;
}

堆优化dijkstra

P4779 【模板】单源最短路径。

https://www.luogu.com.cn/article/coko63s4 。

时间复杂度：\(O(mlogn)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=5e5+10;
priority_queue<pair<int,int> >q; 
int n,m,u,v,w,s,Q,k;
int cnt,h[N],d[N];
bool vis[N];
struct node{int nxt,to,dis;
}e[M];
void add(int u,int v,int w){ e[++cnt].nxt=h[u];e[cnt].to=v;e[cnt].dis=w;h[u]=cnt;
}
void dij(int s){memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;q.push(make_pair(0,s));while(!q.empty()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;int w=e[i].dis;if(d[v]>d[u]+w){d[v]=d[u]+w;q.push(make_pair(-d[v],v));}}   }
}
int main(){cin>>n>>m;while(m--){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}cin>>s>>Q;dij(s);while(Q--){cin>>k;cout<<d[k]<<"\n";}return 0;
}

次短路

https://www.luogu.com.cn/problem/P2865 。
https://www.luogu.com.cn/problem/P2829 。

//我居然切蓝hhhhc
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10,M=5e5+10;
priority_queue<pair<int,int> >q; 
int cnt,h[N],d[N],d2[N];
struct node{int nxt,to,dis;
}e[M];
void add(int u,int v,int w){ e[++cnt].nxt=h[u];e[cnt].to=v;e[cnt].dis=w;h[u]=cnt;
}
void dijkstra(){  memset(d,0x3f,sizeof(d));memset(d2,0x3f,sizeof(d2));q.push(make_pair(0,1));d[1]=0;while(!q.empty()){int u=q.top().second;int dis=-q.top().first;q.pop();if(dis>d2[u])continue;//连次短路都算不上 for(int i=h[u];i;i=e[i].nxt){int v=e[i].to,w=e[i].dis;if(dis+w<d[v]){d2[v]=d[v];//打擂台 d[v]=dis+w;q.push(make_pair(-d[v],v));  }if(dis+w>d[v]&&dis+w<d2[v]){//在两个之间d2[v]=dis+w;q.push(make_pair(-d2[v],v));}}   }
}
int u,v,w;
int main(){cin>>n>>m;while(m--){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}dijkstra();cout<<d2[n];return 0;
}

字典树

P8306 【模板】字典树

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int T,n,q,word[N],ans,tot,trie[N][65];
int num(char x){if(x>='A'&&x<='Z')return x-'A';if(x>='a'&&x<='z')return x-'a'+26;else return x-'0'+52;
} 
void insert(char c[]){int u=0;int len=strlen(c);for(int i=0;i<len;i++){int a=num(c[i]);if(trie[u][a]==0){trie[u][a]=++tot;}u=trie[u][a];word[u]++;}
}
int find(char c[]){int u=0;int len=strlen(c);for(int i=0;i<len;i++){int a=num(c[i]);if(trie[u][a]==0){return 0;}u=trie[u][a];}return word[u];
}
char s[N];
int main(){cin>>T;while(T--){cin>>n>>q;for(int i=0;i<=tot;i++){for(int j=0;j<=100;j++){trie[i][j]=0;} } for(int i=0;i<=tot;i++){word[i]=0;} tot=0;while(n--){scanf("%s",s);insert(s);}while(q--){scanf("%s",s);printf("%d\n",find(s));}}return 0;
}

字典树，一般长这样，但是可以有很多拓展的玩法，比如 01trie。因此需要灵活运用。

void insert(char c[]){int u=0;int len=strlen(c);for(int i=0;i<len;i++){int a=c[i]-'a';if(trie[u][a]==0){trie[u][a]=++tot;}u=trie[u][a];}
}
bool find(char c[]){int u=0;int len=strlen(c);for(int i=0;i<len;i++){int a=c[i]-'a';if(trie[u][a]==0){return 0;}u=trie[u][a];}return 1;
}

字典树合并

int merge(int a,int b){//根分别是a和b if(!a)return b;if(!b)return a;w[a]=w[a]+w[b];xorv[a]^=xorv[b];t[a][0]=merge(t[a][0],t[b][0]);t[a][1]=merge(t[a][1],t[b][1]);return a;
}

字典树维护全局加一

void addall(int u){swap(t[u][0],t[u][1]);if(t[u][0])addall(t[u][0]);maintain(u);//维护原有信息
}

矩阵快速幂

P3390 【模板】矩阵快速幂

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
int n,k;
struct Matrix{int a[110][110];
};
Matrix operator*(const Matrix&a,const Matrix&b){Matrix c;memset(c.a,0,sizeof(c.a));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%p)%p;}}}return c;
}
Matrix qpow(Matrix x,int k){Matrix res;memset(res.a,0,sizeof res.a);for(int i=1;i<=n;i++){res.a[i][i]=1;}while(k){if(k&1)res=res*x;x=x*x;k>>=1;}return res;
}
signed main(){Matrix A;cin>>n>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>A.a[i][j];}}Matrix B=qpow(A,k);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<B.a[i][j]<<" ";}cout<<"\n";}return 0;
}

tarjan

有向图tarjan

P2863 强连通分量个数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//建图 
int n,m,a,b,ans;
int h[N],cnt;
struct node{int nxt,to;}e[N];
void add(int u,int v){e[++cnt].nxt=h[u];e[cnt].to=v;h[u]=cnt;
}
//dfn:时间戳 low:最小时间戳 size:分量大小 
//ins:是否在栈内 tot:当前时间 idx:分量编号 
//st:栈 top:栈顶所在位置 bel:属于哪个分量 
int dfn[N],low[N],size[N];
bool ins[N];
int tot,idx,st[N],top,bel[N]; 
//标准tarjan流程 
void tarjan(int u){low[u]=dfn[u]=++tot;st[++top]=u;ins[u]=1;for(int i=h[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(ins[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){int v;++idx;do{v=st[top--];bel[v]=idx;ins[v]=0;size[idx]++;}while(v!=u);}
}
int main(){cin>>n>>m;while(m--){cin>>a>>b;add(a,b);}//防止原图不联通 for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}//大于1的分量才算入 for(int i=1;i<=idx;i++){if(size[i]<=1){continue;}ans++;}cout<<ans;return 0;
}

无向图tarjan

void tarjan(int u,int fa){low[u]=dfn[u]=++tot;st[++top]=u;ins[u]=1;for(int i=h[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]);}else{low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){int v;++idx;do{v=st[top--];bel[v]=idx;ins[v]=0;}while(v!=u);}
}

缩点

P3387 【模板】缩点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],u,v,ans;
int h[N],cnt;
struct node{int nxt,to;}e[N];
void add(int u,int v){e[++cnt].nxt=h[u];e[cnt].to=v;h[u]=cnt;
}
int dfn[N],low[N],dp[N];
bool ins[N];
int tot,idx,st[N],top,bel[N]; 
void tarjan(int u){low[u]=dfn[u]=++tot;st[++top]=u;ins[u]=1;for(int i=h[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(ins[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){int v;++idx;int sum=0;do{v=st[top--];bel[v]=idx;ins[v]=0;sum+=a[v];for(int i=h[v];i;i=e[i].nxt){dp[idx]=max(dp[idx],dp[bel[e[i].to]]);}}while(v!=u);dp[idx]+=sum;ans=max(ans,dp[idx]);}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}while(m--){cin>>u>>v;add(u,v);}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}cout<<ans;return 0;
}

割点

https://www.luogu.com.cn/problem/P3388 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,m,rt,tim;
const int N=1e5+10;
int dfn[N],low[N];
int ans[N];
vector<int>G[N];
void tarjan(int u,bool rt){low[u]=dfn[u]=++tim;int son=0;for(int v:G[u]){if(!dfn[v]){tarjan(v,0);low[u]=min(low[u],low[v]);if(!rt&&low[v]>=dfn[u])ans[u]=1;if(rt)son++;}else low[u]=min(low[u],dfn[v]);}if(rt&&son>=2)ans[u]=1;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;while(m--){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}For(i,1,n){if(!dfn[i]){tarjan(i,1);}}int num=0;For(i,1,n){if(ans[i])num++;}cout<<num<<"\n";For(i,1,n){if(ans[i])cout<<i<<" ";}return 0;
}

判断字符串的循环节

一种经典的判断方法。找出字符串一对相等的前缀和后缀，此时除后缀外剩下的字符串就是循环节。

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int N=1e6+10;
int n;
string s;
ll h[N],p[N];
ll get(int l,int r){return h[r]-h[l-1]*p[r-l+1];
}
int main(){cin>>n>>s;s=' '+s;p[0]=1;for(int i=1;i<=n;i++){h[i]=h[i-1]*13331+s[i];p[i]=p[i-1]*13331;}for(int i=1;i<=n;i++){if(get(i+1,n)==get(1,n-i)){cout<<i<<"\n";return 0;}}return 0;
}

为什么可以这样？例如：cabcabcabca，循环节是cab。发现可以由 cabcabca 拼接而成。

cabcabcacabcabca 发现新拼接的字符串是由
原来含循环节的字符串再次拼接而成。
把非循环节的部分留到了最后，前面一定是重复的循环节。
又因为1~3的部分与4~6的部分完全相同，
所以循环节就是前面部分。

树链剖分

P3384 【模板】树链剖分

#include<iostream>
#include<vector>
using namespace std;
#define ll long long
const int N=1e5+10;
int u,v,op,x,y,z;
int n,m,r,p,vistime;
int a[N],fa[N],wc[N],sz[N];
int top[N],dfn[N],rdfn[N],d[N];
//dfn[x]=y表示节点y是DFS序的第x个 
//rdfn[x]=y表示DFS序的第x个是节点y
vector<int>G[N];
void dfs1(int u,int f){fa[u]=f;sz[u]=1;d[u]=d[f]+1;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(v==f)continue;dfs1(v,u);sz[u]+=sz[v];if(sz[v]>sz[wc[u]]){wc[u]=v;}}
}
void dfs2(int u,int Top){dfn[u]=++vistime;rdfn[vistime]=u;top[u]=Top;if(wc[u]){dfs2(wc[u],Top);//递归重孩子 for(int i=0;i<G[u].size();i++){int v=G[u][i];if(v==fa[u]||v==wc[u])continue;dfs2(v,v);//递归轻孩子 }}
}
struct node{ll w,tag;
}tree[4*N]; 
void pushup(int u){tree[u].w=(tree[u*2].w+tree[u*2+1].w)%p;
}
void build(int u,int l,int r){if(l==r){tree[u].w=a[rdfn[l]];return;}int mid=(l+r)/2;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);
}
void maketag(int u,int len,ll x){tree[u].tag+=x;tree[u].tag%=p;tree[u].w+=len*x%p;tree[u].w%=p;
} 
void pushdown(int u,int l,int r){int mid=(l+r)/2;maketag(u*2,mid-l+1,tree[u].tag);maketag(u*2+1,r-mid,tree[u].tag);tree[u].tag=0;
}
ll query(int u,int L,int R,int l,int r){if((l<=L)&&(R<=r)){return tree[u].w;} else if(!(L>r||R<l)){int mid=(L+R)/2;pushdown(u,L,R);return (query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r))%p;}else{return 0;}
}
void update(int u,int L,int R,int l,int r,ll x){if((l<=L)&&(R<=r)){maketag(u,R-L+1,x);}else if(!(L>r||R<l)){int mid=(L+R)/2;pushdown(u,L,R);update(u*2,L,mid,l,r,x);update(u*2+1,mid+1,R,l,r,x);pushup(u);}
}
void upd(int x,int y,int z){while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]){swap(x,y);//保证x链头更大 }update(1,1,n,dfn[top[x]],dfn[x],z);//修改区间[dfn[top[x]],dfn[x]] x=fa[top[x]];}//当x和y共链时update(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z); 
}
int qry(int x,int y){ll ans=0;while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]){swap(x,y);//保证x链头更大 }ans+=query(1,1,n,dfn[top[x]],dfn[x]);//查询区间[dfn[top[x]],dfn[x]] ans%=p;x=fa[top[x]];}//当x和y共链时ans+=query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])); ans%=p;return ans;
}
int main(){scanf("%d%d%d%d",&n,&m,&r,&p);for(int i=1;i<=n;i++){scanf("%d",&a[i]);} for(int i=1;i<n;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}dfs1(r,0);dfs2(r,0);build(1,1,n);while(m--){scanf("%d",&op);if(op==1){scanf("%d%d%d",&x,&y,&z);upd(x,y,z);}if(op==2){scanf("%d%d",&x,&y);printf("%lld\n",qry(x,y));}if(op==3){scanf("%d%d",&x,&y);update(1,1,n,dfn[x],dfn[x]+sz[x]-1,y);}if(op==4){scanf("%d",&x);printf("%lld\n",query(1,1,n,dfn[x],dfn[x]+sz[x]-1)%p);}}return 0;
} 

求解方程 \(ax+by=1\):

其中\(gcd(a,b)=1\)。

#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int main(){cin>>a>>b;ll t=exgcd(a,b,x,y);if(t!=1){cout<<"No answer.";return 0;}cout<<x<<" "<<y<<endl;cout<<"gcd("<<a<<","<<b<<")="<<t;
}

求解同余方程组：

P1495 【模板】中国剩余定理。

\[\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases} \]

其中，\(a_1,a_2,...,a_n\)两两互质。

#include<iostream>
#define ll long long
using namespace std;
ll n,b[20],a[20],M[20],mul=1,X;
void exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);int t=x;x=y;y=t-y*(a/b);
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mul*=a[i];cin>>b[i];}for(int i=1;i<=n;i++){ll x=0,y=0;M[i]=mul/a[i];exgcd(M[i],a[i],x,y);X+=b[i]*M[i]*(x<0?x+a[i]:x);}cout<<X%mul;return 0;
}

$ a x \equiv 1 \pmod {b}$的最小整数解。

#include<iostream>
using namespace std;
typedef long long ll;
ll a,b; 
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int main(){cin>>a>>b;ll x=0,y=0;exgcd(a,b,x,y);cout<<(x+b)%b;return 0;
}

\(1\sim n\) 模 \(p\) 意义下的乘法逆元。

P3811 【模板】模意义下的乘法逆元。

这里 \(a\) 模 \(p\) 的乘法逆元定义为 \(ax\equiv1\pmod p\) 的解。

#include<cstdio>
using namespace std;
const int N=3e6+10;
long long n,p,inv[N];
int main(){scanf("%lld%lld",&n,&p);inv[1]=1;printf("%lld\n",inv[1]);for(long long i=2;i<=n;i++){inv[i]=(p-p/i)*inv[p%i]%p;printf("%lld\n",inv[i]);}
}

\(\varphi (n)\)。

别忘了 \(\varphi (1)=1\)，\(\varphi (2)=1\)。

void euler(int n){for(int i=2;i<=n;i++){if(!phi[i]){prime[++tot]=i;phi[i]=i-1;}for(int j=1;j<=tot;j++){if(i*prime[j]>n)break;if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}
}

\(a^b \bmod m\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;
inline ll read(ll m){register ll x=0,f=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch)){x=x*10+ch-'0';if(x>=m)f=1;x%=m;ch=getchar();}return x+(f==1?m:0);
}
ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;
}
ll phi(ll n){ll ans=n;for(ll i=2;i*i<=n;i++){if(n%i==0){ans=ans/i*(i-1);while(n%i==0)n/=i;	}}if(n>1)ans=ans/n*(n-1);return ans;
}
int main(){scanf("%lld%lld",&a,&m);b=read(phi(m));printf("%lld",qpow(a,b,m));return 0;
}

KMP

定义一个字符串 \(s\) 的 border 为 \(s\) 的一个非 \(s\) 本身的子串 \(t\)，满足 \(t\) 既是 \(s\) 的前缀，又是 \(s\) 的后缀。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s1,s2;
int bor[N];
int main(){cin>>s1>>s2;int j=0;for(int i=1;i<s2.size();i++){while(j>0&&s2[i]!=s2[j]){j=bor[j-1];}if(s2[i]==s2[j])j++;bor[i]=j;}j=0;for(int i=0;i<s1.size();i++){while(j>0&&s1[i]!=s2[j]){j=bor[j-1];}if(s1[i]==s2[j])j++;if(j==s2.size()){cout<<i+1-s2.size()+1<<endl;j=bor[j-1];}}for(int i=0;i<s2.size();i++){cout<<bor[i]<<" ";}return 0;
}

快读

inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}return x*f;
}

快速幂

ll qpow(ll a,ll b){  ll res=1;  a=a%p; while(b){  if(b&1)res=(res*a)%p;b>>=1; a=(a*a)%p;  }  return res;  
}

哈希

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
#define ll long long
const int N=1e4+10;
const ll p=998244353;
ll Hash(string s){ll res=0;for(int i=0;i<s.size();i++){res=(133331*res+s[i])%p;}return res;
}
ll h[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>s;h[i]=Hash(s);}sort(h+1,h+n+1);int ans=unique(h+1,h+n+1)-h-1;cout<<ans;return 0;
}

二维哈希（双模数）

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
#define ll unsigned long long
ll a[N][N],b[N][N];
ll h[N],h2[N];
int n,m,q,A,B;
string s;
map<ll,int>v;
ll get(int x,int x2,int y,int y2){ll ans=a[x2][y2]-a[x-1][y2]*h[x2-x+1];ans=ans-a[x2][y-1]*h2[y2-y+1];ans=ans+a[x-1][y-1]*h[x2-x+1]*h2[y2-y+1];return ans;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m>>A>>B;h[0]=h2[0]=1;for(int i=1;i<=max(n,m);i++){h[i]=h[i-1]*1331;h2[i]=h2[i-1]*13331;}for(int i=1;i<=n;i++){cin>>s;for(int j=1;j<=m;j++){a[i][j]=s[j-1]^48;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]+=a[i][j-1]*13331;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]+=a[i-1][j]*1331;}}for(int i=1;i<=n-A+1;i++){for(int j=1;j<=m-B+1;j++){v[get(i,i+A-1,j,j+B-1)]=1;}}cin>>q;while(q--){for(int i=1;i<=A;i++){cin>>s;for(int j=1;j<=B;j++){b[i][j]=s[j-1]^48;}}for(int i=1;i<=A;i++){for(int j=1;j<=B;j++){b[i][j]+=b[i][j-1]*13331;}}for(int i=1;i<=A;i++){for(int j=1;j<=B;j++){b[i][j]+=b[i-1][j]*1331;}}cout<<v[b[A][B]]<<"\n";}return 0;
}

树状数组

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,tree[N];
int sum(int x){int ans=0;for(;x;x-=x&(-x))ans+=tree[x];return ans;
}
void add(int x,int value){for(;x<=n;x+=x&(-x))tree[x]+=value;
}
int main(){//主函数return 0;
} 

此处的sum记录前缀和，复杂度O(logn)，add可以添加数进入某个位置。

修改树状数组的定义可以实现后缀查询。

#include<bits/stdc++.h>
using namespace std;
int n=5,tree[10];
int sum(int x){int ans=0;for(;x<=n;x+=x&(-x))ans+=tree[x];return ans;
}
void add(int x,int value){for(;x;x-=x&(-x))tree[x]+=value;
}
int main(){for(int i=1;i<=n;i++){add(i,i);}cout<<sum(4);//4-5的和return 0;
} 

背包

0\1背包(每个物体使用一次) 
#include<iostream>
using namespace std;
int T,M,t[110],w[110],f[1010]; 
int main(){cin>>T>>M;for(int i=1;i<=M;i++)cin>>t[i]>>w[i];for(int i=1;i<=M;i++)for(int j=T;j>=t[i];j--)f[j]=max(f[j],f[j-t[i]]+w[i]);cout<<f[T];
}
完全背包(每个物品无限使用)
#include<bits/stdc++.h>
using namespace std;
long long T,M,t[10010],w[10010],f[10000010]; 
int main(){cin>>T>>M;for(int i=1;i<=M;i++)cin>>t[i]>>w[i];for(int i=1;i<=M;i++)for(int j=t[i];j<=T;j++)f[j]=max(f[j],f[j-t[i]]+w[i]);cout<<f[T];
} 
多重背包(每个物品规定了可用的次数)
#include<bits/stdc++.h>
using namespace std;
int n,m,n1,v[10001],w[10001],f[6001];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x,y,s,t=1;scanf("%d%d%d",&x,&y,&s);while(s>=t){v[++n1]=x*t;w[n1]=y*t;s-=t;t*=2;}v[++n1]=x*s;w[n1]=y*s;                            }for(int i=1;i<=n1;i++)for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]); printf("%d\n",f[m]);return 0;
} 

线段树模版

#include<iostream>
using namespace std;
#define ll long long
const int N=1e5+10;
int a[N];
//线段树
struct node{ll w,tag;
}tree[4*N]; 
//求和过程
void pushup(int u){tree[u].w=tree[u*2].w+tree[u*2+1].w;
}
//建树
void build(int u,int l,int r){if(l==r){tree[u].w=a[l];return;}int mid=(l+r)/2;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);
}
//单点查询
ll query1(int u,int l,int r,int p){if(l==r)return tree[u].w;int mid=(l+r)/2;if(mid>=p)query1(u*2,l,mid,p);else query1(u*2+1,mid+1,r,p);
}
//单点修改
void update1(int u,int l,int r,int p,ll x){if(l==r){tree[u].w=x;return;}int mid=(l+r)/2;if(mid>=p)update1(u*2,l,mid,p,x);else update1(u*2+1,mid+1,r,p,x);pushup(u);
}
//更新延时标记
void maketag(int u,int len,ll x){tree[u].tag+=x;tree[u].w+=len*x;
} 
//下传延时标记
void pushdown(int u,int l,int r){int mid=(l+r)/2;maketag(u*2,mid-l+1,tree[u].tag);maketag(u*2+1,r-mid,tree[u].tag);tree[u].tag=0;
}
//区间查询
ll query2(int u,int L,int R,int l,int r){if(l<=L&&R<=r)return tree[u].w;else if(!(L>r||R<l)){int mid=(L+R)/2;pushdown(u,L,R);return query2(u*2,L,mid,l,r)+query2(u*2+1,mid+1,R,l,r);}else return 0;
}
//区间修改
void update2(int u,int L,int R,int l,int r,ll x){if(l<=L&&R<=r)maketag(u,R-L+1,x);else if(!(L>r||R<l)){int mid=(L+R)/2;pushdown(u,L,R);update2(u*2,L,mid,l,r,x);update2(u*2+1,mid+1,R,l,r,x);pushup(u);}
}
int main(){return 0;
}

封装写法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
int a[N];
struct Seg{struct node{ll w,tag;}; vector<node>t;int n;Seg(int _n):n(_n),t(4*_n+1){}//求和过程void pushup(int u){t[u].w=t[u*2].w+t[u*2+1].w;}//建树void build(int u,int l,int r){if(l==r){t[u].w=a[l];return;}int m=(l+r)/2;build(u*2,l,m);build(u*2+1,m+1,r);pushup(u);}//单点查询ll qry1(int u,int l,int r,int p){if(l==r)return t[u].w;int m=(l+r)/2;if(m>=p)qry1(u*2,l,m,p);else qry1(u*2+1,m+1,r,p);}//单点修改void upd1(int u,int l,int r,int p,ll x){if(l==r){t[u].w=x;return;}int m=(l+r)/2;if(m>=p)upd1(u*2,l,m,p,x);else upd1(u*2+1,m+1,r,p,x);pushup(u);}//更新延时标记void tag(int u,int len,ll x){t[u].tag+=x;t[u].w+=len*x;} //下传延时标记void pushdown(int u,int l,int r){int m=(l+r)/2;tag(u*2,m-l+1,t[u].tag);tag(u*2+1,r-m,t[u].tag);t[u].tag=0;}//区间查询ll qry2(int u,int L,int R,int l,int r){if(l<=L&&R<=r)return t[u].w;else if(!(L>r||R<l)){int m=(L+R)/2;pushdown(u,L,R);return qry2(u*2,L,m,l,r)+qry2(u*2+1,m+1,R,l,r);}else return 0;}//区间修改void upd2(int u,int L,int R,int l,int r,ll x){if(l<=L&&R<=r)tag(u,R-L+1,x);else if(!(L>r||R<l)){int m=(L+R)/2;pushdown(u,L,R);upd2(u*2,L,m,l,r,x);upd2(u*2+1,m+1,R,l,r,x);pushup(u);}}
};
int main(){return 0;
}

线段树变式

【模板】线段树 2

需要维护乘法和加法的延迟标记，记得先乘后加。

#include<iostream>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,m,p,op,x,y,k;
ll a[N];
struct node{ll w,add,mul;
}tree[4*N]; 
void pushup(int u){tree[u].w=(tree[u*2].w+tree[u*2+1].w)%p;
}
void build(int u,int l,int r){tree[u].mul=1;if(l==r){tree[u].w=a[l];return;}int mid=(l+r)/2;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);
}
void maketag(int u,int len,ll x,int type){if(type==1){(tree[u].add*=x)%=p;(tree[u].mul*=x)%=p;(tree[u].w*=x)%=p;}else{(tree[u].add+=x)%=p;(tree[u].w+=len*x)%=p;}
} 
void pushdown(int u,int l,int r){int mid=(l+r)/2;maketag(u*2,mid-l+1,tree[u].mul,1);maketag(u*2,mid-l+1,tree[u].add,2);maketag(u*2+1,r-mid,tree[u].mul,1);maketag(u*2+1,r-mid,tree[u].add,2);tree[u].mul=1;tree[u].add=0;
}
ll query(int u,int L,int R,int l,int r){if((l<=L)&&(R<=r))return tree[u].w;else if(!((L>r)||(R<l))){int mid=(L+R)/2;pushdown(u,L,R);return (query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r))%p;}else return 0;
}
void update(int u,int L,int R,int l,int r,ll x,int type){if((l<=L)&&(R<=r)){maketag(u,R-L+1,x,type);}else if(!((L>r)||(R<l))){int mid=(L+R)/2;pushdown(u,L,R);update(u*2,L,mid,l,r,x,type);update(u*2+1,mid+1,R,l,r,x,type);pushup(u);}return;
}
int main(){cin>>n>>m>>p;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);while(m--){cin>>op;if(op==1){cin>>x>>y>>k;update(1,1,n,x,y,k,1);}else if(op==2){cin>>x>>y>>k;update(1,1,n,x,y,k,2);}else{cin>>x>>y;cout<<query(1,1,n,x,y)%p<<endl;}}return 0;
}

zkw树

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6+10;
int n,m,k,tree[N],tag[N];
//建树 
void build(int n){for(m=1;m<n+2;m<<=1);for(int i=m+1;i<=m+n;i++){cin>>tree[i];}for(int i=m-1;i;i--){tree[i]=tree[i*2]+tree[i*2+1];}
}
//点修 
void update_node(int x,int v){for(x+=m;x;x>>=1){tree[x]+=v;}
}
//区修 
void update_sum(int x,int y,int v){int len=1,xl=0,yl=0;for(x=x+m-1,y=y+m+1;x^y^1;x/=2,y/=2,len*=2){tree[x]+=xl*v;tree[y]+=yl*v;if(~x&1){tree[x^1]+=v*len;xl+=len;tag[x^1]+=v;}if(y&1){tree[y^1]+=v*len;yl+=len;tag[y^1]+=v;}}while(x){tree[x]+=xl*v;tree[y]+=yl*v;x/=2;y/=2;}
}
//区间和 
int query_sum(int x,int y){int ans=0,len=1,xl=0,yl=0;for(x=x+m-1,y=y+m+1;x^y^1;x/=2,y/=2,len*=2){ans+=xl*tag[x]+yl*tag[y];if(~x&1){ans+=tree[x^1];xl+=len;}if(y&1){ans+=tree[y^1];yl+=len;}}while(x){ans+=xl*tag[x]+yl*tag[y];x/=2;y/=2;}return ans;
}
int main(){cin>>n>>k;build(n);for(int i=1;i<=k;i++){int op,x,y,w;cin>>op>>x>>y;if(op==1){cin>>w;update_sum(x,y,w);}else cout<<query_sum(x,y)<<"\n";}return 0;
}

权值线段树

用数组 \(T\) 统计某个数出现的个数，想要计算 \([l,r]\) 中每个数出现了几次建立关于数组 \(T\) 的线段树再计算区间和即可。

线段树二分

例题：有一个初始为空的可重集合 \(S\)，每次有两种操作：

1.往 \(S\) 中放入一个数。

2.询问第 \(k\) 小的数。

数的范围是 \([0,10^{5}]\)。

令 \(T\) 为集合 \(S\) 的统计数组，即 \(T[x]\) 表示 \(S\) 中有多少个 \(x\) 对于增加 \(x\) 的操作，就相当于 \(T[x]\) ++。对于第 \(k\) 小的询问，就是要找到最小的 \(x\) 使得 \(T[0]\)+\(T[1]\)+…+\(T[x] \ge k\) 。

考虑对这个问题进行二分，假设当前二分的区间为[l,r]
令mid=(l+r)/2，则我们先判断T[l]+T[l+1]+…+T[mid]是否>=k。

如果满足，则说明答案为[l,mid]中的第k小的数。否则，答案为[mid+1,r]中的第k-(T[l]+T[l+1]+…+T[mid])小的数。

而注意我们线段树的结构，如果节点i存的信息是T[l]+T[l+1]+…+T[r] ，则T[l]+T[l+1]+…+T[mid]就是i的左孩子的信息。

也就是说，维护了线段树以后，我们二分时需要查询的信息都是已经存在线段树中的，代码如下。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t[N<<2];
int q,op,k;
void upd(int u,int l,int r,int x){t[u]++;if(l==r){	return;}int mid=(l+r)>>1;if(x<=mid)upd(u*2,l,mid,x);else upd(u*2+1,mid+1,r,x);
}
int qry(int u,int l,int r,int k){if(l==r){return l;}int mid=(l+r)>>1;if(t[u*2]>=k){return qry(u*2,l,mid,k);}else{return qry(u*2+1,mid+1,r,k-t[u*2]);}
}
int main(){cin>>q;while(q--){cin>>op>>k;if(op==1){upd(1,1,N-10,k);}else{cout<<qry(1,1,N-10,k)<<"\n";}}return 0;
}

前缀和和差分

一维前缀和：\(s_{i}=\sum_{i=1}^{n} a_{i}\)。

一维差分：\(c_{i}=a_{i}-a_{i-1}\)。

二维前缀和：\(\sum_{i=1}^{n} \sum_{j=1}^{m} a_{i,j}\)。

求某矩阵和：\(s_{x2,y2}-s_{x2,y1-1}-s_{x1-1,y2}+s_{x1-1,y1-1}\)。

//二维差分//预处理 
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c[i][j]=c[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
//修改区间：
c[x1][y1]+=v;
c[x2+1][y1]-=v;
c[x1][y2+1]-=v;
c[x2+1][y2+1]+=v;

高维前缀和和差分：容斥原理。

离散化

//把形如这样的数组：9999999999 1000 100000000 7382190790247389
//变成：3 1 2 4
//这样减小值域的方法叫离散化

离散化好处：比如需要用桶记录每个数字出现了几次，因为数组空间开 1e9 会爆，所以我们可以离散化把数字变小再来统计。

以下这段代码可以把数组中重复出现的数字只输出一次。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);//一定要先排序,不然去重有误 int cnt=unique(a+1,a+n+1)-a-1;//和sort有点像，标从1-n，括号内要写(a+1,a+n+1)//cnt代表去重后有几个数字for(int i=1;i<=cnt;i++){cout<<a[i]<<" ";}return 0;
} 
//输入:
//10
//1 1 4 4 5 5 1 1 4 4
//输出：
//1 4 5 
//输出(不排序) 
//1 4 5 1 4

如果想知道去重后原数组每个数字分别是第几大。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],t[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t[i]=a[i];//用t数组记录 }sort(t+1,t+n+1);//一定要先排序,不然去重有误 int cnt=unique(t+1,t+n+1)-t-1;//和sort有点像，标从1-n，括号内要写(a+1,a+n+1)//cnt代表去重后有几个数字for(int i=1;i<=n;i++){cout<<lower_bound(t+1,t+cnt+1,a[i])-t<<" ";//查找a[i]是第几大，从而实现重新编号 }return 0;
} 

统计数组每个数字出现几次。

a:999999999 999999999 859835793083488 999999999
原来：i=1:num[999999999]++;i=2:num[999999999]++;i=3:num[859835793083488]++;i=4:num[999999999]++;
值域太大无法实现离散化关键代码：a[i]=lower_bound(t+1,t+cnt+1,a[i])-t; 离散化后：原数组：1 1 2 1 
现在：i=1:num[1]++;i=2:num[1]++;i=3:num[2]++;i=4:num[1]++;

B3694 数列离散化

给定一个长度为 \(n\) 的数列 \(a\)。定义 \(\mathrm{rank}(i)\) 表示数列 \(a\) 中比 \(a_i\) 小的不同数字个数再加一。输出所有 \(\mathrm{rank}(i)\)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],t[N];
void solve(){memset(a,0,sizeof(a));memset(t,0,sizeof(t));cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t[i]=a[i];//用t数组记录 }sort(t+1,t+n+1);//一定要先排序,不然去重有误 int cnt=unique(t+1,t+n+1)-t-1;//和sort有点像，标从1-n，括号内要写(a+1,a+n+1)//cnt代表去重后有几个数字for(int i=1;i<=n;i++){a[i]=lower_bound(t+1,t+cnt+1,a[i])-t;//查找a[i]是第几大，从而实现重新编号 }for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<"\n";
}
int T;
int main(){cin>>T;while(T--){solve();}return 0;
} 

并查集

有启发式合并，实现：比较两个即将合并的并查集的大小，小的合到大的那里，可以提升效率。

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

线性筛

线性筛模板题

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
#define int long long
int n;
int phi[N];
bitset<N>v;
//phi:φ
//v:是否为质数
int mn[N];
//mn:n的最小质因子
int p[N],cnt;
//p:质数集合，p[i]表示第i个质数 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;v[1]=1;mn[1]=1;phi[1]=1;for(int i=2;i<=n;i++){if(!v[i]){p[++cnt]=i;mn[i]=i;phi[i]=i-1; }for(int j=1;j<=cnt&&i*p[j]<=n;j++){v[i*p[j]]=1;mn[i*p[j]]=p[j];if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}phi[i*p[j]]=phi[i]*(p[j]-1);}}if(v[n]==0)cout<<"Yes\n";else cout<<"No\n";cout<<mn[n]<<"\n"<<phi[n];return 0;
}

拓展欧几里得

//ll是long long，这里用了宏定义
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}

ST表

时间复杂度：\(O(nlogn)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
int n,m;
int f[N][30];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>f[i][0];}for(int j=1;(1<<j)<=n;j++){for(int i=1;i<=n-(1<<j)+1;i++){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}while(m--){int l,r;cin>>l>>r;int k=log2(r-l+1);cout<<max(f[l][k],f[r-(1<<k)+1][k])<<"\n";}return 0;
}

扫描线

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
#define ll long long
ll a[N],ans;
ll x,y,x2,y2;
struct node{int num;ll len;
}t[N<<2];
struct line{ll x,x2,y;int tag;
}p[N<<2];
bool cmp(line a,line b){return a.y<b.y;
}
void pushup(int u,int l,int r){if(t[u].num>0){t[u].len=a[r]-a[l];return;}t[u].len=t[u*2].len+t[u*2+1].len;
}
void upd(int u,int L,int R,int l,int r,int tag){if(a[R]<=l||r<=a[L])return;if(l<=a[L]&&a[R]<=r){t[u].num+=tag;pushup(u,L,R);return;}int mid=(L+R)>>1;upd(u*2,L,mid,l,r,tag);upd(u*2+1,mid,R,l,r,tag);pushup(u,L,R);
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>x>>y>>x2>>y2;p[i]=line{x,x2,y,1};p[i+n]=line{x,x2,y2,-1};a[i]=x;a[i+n]=x2;}n<<=1;sort(p+1,p+n+1,cmp);sort(a+1,a+n+1);for(int i=1;i<n;i++){upd(1,1,n,p[i].x,p[i].x2,p[i].tag);ans+=(p[i+1].y-p[i].y)*t[1].len;}cout<<ans;return 0;
}

可持久化线段树

可持久化线段树2

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,sum;
struct node{int l,r,w;
}t[N<<5];
int a[N],h[N];
int T[N],l,r,k;
int build(int u,int l,int r){++sum;if(l==r)return u;int mid=(l+r)>>1;t[u].l=build(u+1,l,mid);t[u].r=build(u+1,mid+1,r);return u;
}
int upd(int u,int l,int r,int x){int p=++sum;t[p].l=t[u].l;t[p].r=t[u].r;t[p].w=t[u].w+1;if(l!=r){int mid=(l+r)>>1;if(x<=mid)t[p].l=upd(t[u].l,l,mid,x);else t[p].r=upd(t[u].r,mid+1,r,x);} return p;
}
int qry(int u,int v,int l,int r,int k){if(l==r)return h[l];int mid=(l+r)>>1;int num=t[t[v].l].w-t[t[u].l].w;if(num>=k)return qry(t[u].l,t[v].l,l,mid,k);else return qry(t[u].r,t[v].r,mid+1,r,k-num);
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];h[i]=a[i];}sort(h+1,h+n+1);int cnt=unique(h+1,h+n+1)-h-1;T[0]=build(1,1,cnt);for(int i=1;i<=n;i++){int x=lower_bound(h+1,h+cnt+1,a[i])-h;T[i]=upd(T[i-1],1,cnt,x);}while(m--){cin>>l>>r>>k;cout<<qry(T[l-1],T[r],1,cnt,k)<<"\n";}return 0;
}

求任意n个数的逆元

时间复杂度：\(O(n+logp)\)。

模板题

#include<iostream>
using namespace std;
#define int long long
const int N=3e6+10;
int n,p;
int qpow(int a,int b){int res=1;while(b){if(b&1)res=res*a%p;b>>=1;a=a*a%p;}return res;
}
int fac[N],invj[N];
int a[N],inv[N];
signed main(){cin>>n>>p;fac[0]=1;for(int i=1;i<=n;i++){cin>>a[i];fac[i]=fac[i-1]*a[i]%p;}invj[n]=qpow(fac[n],p-2)%p;for(int i=n-1;i>=1;i--){invj[i]=a[i+1]%p*invj[i+1]%p;}for(int i=1;i<=n;i++){inv[i]=fac[i-1]*invj[i]%p;cout<<inv[i]<<" ";}return 0;
} 

最小表示法

P1368 【模板】最小表示法

把串复制一遍接在后面，当查找时一个串优于另一个串，我们就用更优的那个替换当前串，因此将指针移到更优串那里，因此当 S[i-i+k] 优于 S[j-j+k] 时，j 移动到 i+k+1 的位置，可以保证 i~i+k 中没有更优解。

#include<bits/stdc++.h>
using namespace std;
int num[600010],n;
int find(){int i=1,j=2,k=0;while(i<=n&&j<=n){while(num[i+k]==num[j+k]&&k<=n)k++;//塞满n个为止，但出现不同就不必再加if(num[i+k]>num[j+k])i=i+k+1;//i串当前位置更大,j串优else j=j+k+1;//j串位置大if(i==j)j++;//i,j是一样的串时,j后移一个k=0;}return min(i,j);
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>num[i];num[i+n]=num[i];}int t=find();for(int i=t;i<t+n;i++){printf("%d ",num[i]);}return 0;
}

无向图三元环计数

P1989 无向图三元环计数。

时间复杂度: \(O(m \sqrt m)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
bool vis[N];
int n,m,d[N];
int u[M],v[M],ans;
vector<int>G[N];
int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>u[i]>>v[i];d[u[i]]++;d[v[i]]++;}for(int i=1;i<=m;i++){if(d[u[i]]>d[v[i]]){swap(u[i],v[i]);}else if(u[i]>v[i]&&d[u[i]]==d[v[i]]){swap(u[i],v[i]);}G[u[i]].push_back(v[i]);}for(int u=1;u<=n;u++){for(int v:G[u]){vis[v]=1;}for(int v:G[u]){for(int x:G[v]){ans+=vis[x];}}	for(int v:G[u]){vis[v]=0;}}cout<<ans;return 0;
}

三维偏序

P3810 【模板】三维偏序。

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
int n,m,cnt,k;
struct node{int a,b,c,cnt,ans;bool operator!=(node x){if(a!=x.a)return 1;if(b!=x.b)return 1;if(c!=x.c)return 1;return 0;}
};
node e[N],f[N];
int ans[N];
int t[M];
void add(int x,int v){for(;x<=k;x+=x&(-x))t[x]+=v;
}
int qry(int x){int ans=0;for(;x;x-=x&(-x)){ans+=t[x];}return ans;
}
bool cmp(node x,node y){if (x.a!=y.a)return x.a<y.a;if (x.b!=y.b)return x.b<y.b;return x.c<y.c;
}
bool cmp2(node x,node y){if (x.b!=y.b)return x.b<y.b;return x.c<y.c;
}
void cdq(int l,int r){if(l==r)return;int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);sort(f+l,f+mid+1,cmp2);sort(f+mid+1,f+r+1,cmp2);int i=l,j=mid+1;while(j<=r){while(i<=mid&&f[i].b<=f[j].b){add(f[i].c,f[i].cnt);i++;}f[j].ans+=qry(f[j].c);j++;}for(int k=l;k<i;k++)add(f[k].c,-f[k].cnt);return;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>e[i].a>>e[i].b>>e[i].c;}sort(e+1,e+n+1,cmp);for(int i=1;i<=n;i++){cnt++;if(e[i]!=e[i+1]){m++;f[m].a=e[i].a;f[m].b=e[i].b;f[m].c=e[i].c;f[m].cnt=cnt;cnt=0;}}cdq(1,m);for(int i=1;i<=m;i++)ans[f[i].ans+f[i].cnt-1]+=f[i].cnt;for(int i=0;i<n;i++)cout<<ans[i]<<"\n";return 0;
}

差分约束

P5960 【模板】差分约束

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,m;
int a,b,c;
#define pii pair<int,int>
vector<pii>G[N];
int d[N],cnt[N];
bool vis[N];
queue<int>q;
bool spfa(int s){memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;q.push(s);vis[s]=1;cnt[s]++;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<G[u].size();i++){int v=G[u][i].first;int w=G[u][i].second;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!vis[v]){q.push(v);vis[v]=1;cnt[v]++;if(cnt[v]>n)return 0;}}}}return 1;
}
int main(){cin>>n>>m;while(m--){cin>>a>>b>>c;G[b].push_back(make_pair(a,c));}for(int i=1;i<=n;i++){G[0].push_back(make_pair(i,0));}if(!spfa(0)){cout<<"NO";return 0;}for(int i=1;i<=n;i++){cout<<d[i]<<" ";}return 0;
}

最长不升子序列长度

P1020 [NOIP1999 提高组] 导弹拦截

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
#define ll long long 
int t,a[N],n;
int f[N],ans;
void pre(){ans=0;for(int i=1;i<=n;i++)f[i]=inf;reverse(a+1,a+n+1);
}
int main(){while(cin>>t&&t!=EOF)a[++n]=t;pre();//初始化 for(int i=1;i<=n;i++){int l=1,r=i;while(l<r){int mid=(l+r)>>1;if(f[mid]>a[i])r=mid;else l=mid+1;}f[l]=min(f[l],a[i]);ans=max(ans,l);}cout<<ans<<"\n";pre();for(int i=1;i<=n;i++){int l=1,r=i;while(l<r){int mid=(l+r)>>1;if(f[mid]>=a[i])r=mid;else l=mid+1;}f[l]=min(f[l],a[i]);ans=max(ans,l);}cout<<ans;return 0;
}

封装写法

把原来要用东西全部塞进一个你命名的 struct 里，源代码 copy 进去然后增加一个构造函数，一些地方可能稍微更改，例如线段树固定长度的数组可以换成可变大小的 vector，下面是构造函数的示例。

Seg(int _n):n(_n),t(4*_n+1){}
/*_n是建立时要传递的量，比如建立线段树需要事先确定
大小，建立方式： Seg 树名字(大小) 
*/

基环树找环

正常 dfs 再判断一个深度就行了，如果儿子深度小于父亲就是环。

pbds

下面展示平衡树的建造和使用方式省流。更详细移步 https://www.luogu.com.cn/article/tk8rh0c9 。

建立方式

#include<bits/extc++.h>
//不可以用万能头替代它,这是pbds专属万能头
//但是devc++用不了
#include<ext/pb_ds/assoc_container.hpp>
//这个可以用，一般写这个头文件
using namespace __gnu_pbds;
template<typename T>
using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//下面需要用的时候就写这一行
//Tree<类型>变量名，例：
Tree<pair<int,int> >a;
Tree<int>b;

假如这棵树名字为 A。

1.插入一个数(会自动去重和排序) 
A.insert(x);2.找到第p个元素
int x=*A.find_by_order(p);
//x为第p个元素的值 
int l=A.find_by_order(p);
//l为第p个元素下标 3.删除值为x的所有数
A.erase(x) 4. 查询数值严格小于x的最大下标
int l=A.order_of_key(x);//以上x皆可以改成 pair 类型5.其他
!A.empty()//可以判断是否为空 

set&multiset

二者唯一区别在于：set 不可重，multiset 可重。

建立方式

set<int>s;
set<int>s{0,x}的作用是创建一个名为s的整数集合，
并且往其中添加两个初始元素，即0和变量x的值

使用

set 提供了以下几种迭代器：
begin() 返回指向首元素的迭代器。
end() 返回指向数组尾端占位符的迭代器，注意是没有元素的。
rbegin() 返回指向逆向数组的首元素的逆向迭代器，
可以理解为正向容器的末元素。insert(x) 当容器中没有等价元素的时候，
将元素 x 插入到 set 中。
erase(x) 删除值为 x 的所有元素，返回删除元素的个数。
erase(pos) 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last) 删除迭代器在 [first,last) 范围
内的所有元素。
clear() 清空 set。
count(x) 返回 set 内键为 x 的元素数量。
find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，
否则返回 end()。
lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。
如果不存在这样的元素，返回 end()。
upper_bound(x) 返回指向首个大于给定键的元素的迭代器。
如果不存在这样的元素，返回 end()。
empty() 返回容器是否为空。
size() 返回容器内元素个数。

高斯消元

https://www.luogu.com.cn/problem/P2455

#include<bits/stdc++.h>
using namespace std;
#define db double
#define For(i,l,r) for(int i=l;i<=r;i++)
const db eps=1e-7; 
int n;
const int N=110;
db a[N][N];
int main(){cin>>n;For(i,1,n)For(j,1,n+1)cin>>a[i][j];int rk=1;For(j,1,n){int mx=0;For(i,rk,n){if(fabs(a[i][j])>fabs(a[mx][j])){mx=i;}}if(fabs(a[mx][j])<eps)continue;For(k,1,n+1)swap(a[rk][k],a[mx][k]); double t=a[rk][j];For(k,j,n+1)a[rk][k]/=t;For(i,1,n){if(i==rk)continue;double t=a[i][j];For(k,j,n+1)a[i][k]-=a[rk][k]*t;}rk++;}For(i,rk,n){ if(fabs(a[i][n+1])>eps){cout<<-1;return 0;}}if(rk<=n){cout<<0;return 0;}for(int i=n;i>=1;i--){For(j,i+1,n){a[i][n+1]-=a[i][j]*a[j][n+1];}}For(i,1,n){cout<<"x"<<i<<"=";cout<<fixed<<setprecision(8)<<a[i][n+1]<<"\n";}return 0;
} 

【模板】离线二维数点

https://www.luogu.com.cn/problem/P10814

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,m;
const int N=2e6+10;
int a[N];
struct node{int x,id,val;
};
vector<node>G[N];
int t[N],ans[N];
void add(int x,int v){for(;x<=n;x+=x&(-x))t[x]+=v;
}
ll qry(int x){int res=0;for(;x;x-=x&(-x))res+=t[x];return res;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;For(i,1,n)cin>>a[i];For(i,1,m){int l,r,x;cin>>l>>r>>x;G[l-1].pb({x,i,-1});G[r].pb({x,i,1});}For(i,1,n){add(a[i],1);For(j,0,(int)G[i].size()-1){node t=G[i][j];ans[t.id]+=t.val*qry(t.x);}}For(i,1,m)cout<<ans[i]<<"\n";return 0;
}