Anby_の模板题集

洛谷版。
博客备份版。

普及-

B3647 【模板】Floyd

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,dp[N][N];
int main(){cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) dp[i][j]=inf;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dp[u][v]=dp[v][u]=min(dp[u][v],w);}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){		dp[i][j]=dp[j][i]=min(dp[i][j],dp[i][k]+dp[k][j]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cout<<dp[i][j]<<" ";cout<<endl;}return 0;
}

B3614 【模板】栈

#include<bits/stdc++.h>
#define int unsigned long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/int t,x,n,head,q[N];
string op;
signed main(){cin.tie(0);ios::sync_with_stdio(false);cin>>t;while(t--){cin>>n;head=0;while(n--){cin>>op;if(op=="push"){cin>>x;q[++head]=x;}if(op=="pop"){if(!head) cout<<"Empty\n";else head--;}if(op=="query"){if(!head) cout<<"Anguei!\n";else cout<<q[head]<<endl;}if(op=="size") cout<<head<<endl;}}return 0;
}

P1177 【模板】排序

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int a[N],n;
void quickSort(int l,int r){if(l>=r) return;int x=a[l],i=l,j=r;while(i<j){while(a[j]>=x&&i<j) j--;while(a[i]<=x&&i<j) i++;swap(a[i],a[j]);}a[l]=a[i],a[i]=x;quickSort(l,i-1);quickSort(i+1,r);
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=n;i++) cout<<a[i]<<" ";return 0;
}

P3383 【模板】线性筛素数

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1e8+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int primes[N],cnt,m,T;
bool vis[N];
void init(int n){for(int i=2;i<=n;i++){if(!vis[i]) primes[++cnt]=i;for(int j=1;j<=cnt&&i*primes[j]<=n;j++){vis[i*primes[j]]=1;if(i%primes[j]==0) break;}}
} 
int main(){cin>>m>>T;init(m);while(T--){cin>>m;cout<<primes[m]<<endl;}return 0;
}

P1226 【模板】快速幂

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int a,b,p;
ll quickMi(int a,int b){ll ans=1,bit=a;while(b>0){if(b&1) ans=(ans*bit)%p;bit=(bit*bit)%p;b>>=1;}return ans%p;
}
int main(){cin>>a>>b>>p;printf("%d^%d mod %d=%lld",a,b,p,quickMi(a,b));return 0;
}

P3370 【模板】字符串哈希

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e6+10,M=105,inf=0x3f3f3f3f;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
ull mod=212370440130137957ll,prime=117517,base=131,ans=1,a[N];
string s;
ull hashl(string s){int size=s.size();ull ans=0;for(int i=0;i<size;i++) ans=(ans*base+(ull)s[i])%mod+prime;return ans;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>s;a[i]=hashl(s);}sort(a+1,a+n+1);for(int i=1;i<n;i++) if(a[i]!=a[i+1]) ans++;cout<<ans;return 0;
}

B3644 【模板】拓扑排序 / 家谱树

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int deg[N],n,head[N],edge[N],last[N],idx;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
void kahn(){queue<int> q;for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);while(!q.empty()){int t=q.front(); q.pop();cout<<t<<" ";for(int i=head[t];i;i=last[i]){int v=edge[i]; deg[v]--;if(!deg[v]) q.push(v);}}
}
int main(){cin>>n;for(int i=1;i<=n;i++){int c=0;while(cin>>c&&c){deg[c]++;add(i,c);}}kahn();return 0;
}

普及/提高-

P3378 【模板】堆

#include<bits/stdc++.h>
#define f(x) ((x)/2)
#define l(x) (x*2)
#define r(x) (x*2+1)
#define x first
#define y second
using namespace std;
const int N=1e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int cnt,heap[N];
void push(int x){int pos=++cnt;while(pos>1){if(heap[f(pos)]<=x) break;heap[pos]=heap[f(pos)],pos=f(pos);}heap[pos]=x;
}
void pop(){int pos=1,x=heap[cnt--];while(l(pos)<=cnt){int son=(heap[l(pos)]<heap[r(pos)]?l(pos):r(pos));if(heap[son]>=x) break;heap[pos]=heap[son],pos=son;}heap[pos]=x;
}
void op() {cout<<heap[1]<<endl;}
int main(){int n;cin>>n;while(n--){int opt,v1;cin>>opt;if(opt==1) cin>>v1,push(v1);else if(opt==3) pop();else op();}return 0;
}

P3865 【模板】ST 表 && RMQ 问题

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int lg2[N];
int n,q,a[N];
int f[N][30];
signed main(){cin>>n>>q;for(int i=1;i<=n;i++) scanf("%lld",a+i);for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;for(int i=1;i<=n;i++) f[i][0]=a[i];for(int j=1;j<=30;j++)for(int i=1;i<=n-(1<<j)+1;i++)f[i][j]=max(f[i][j-1],f[i+(1ll<<(j-1))][j-1]);while(q--){int l,r;scanf("%lld%lld",&l,&r);int lg=lg2[r-l+1];int mx=max(f[l][lg],f[r-(1ll<<lg)+1][lg]);cout<<mx<<"\n";}return 0;
}

B3611 【模板】传递闭包

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,dp[N][N];
int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>dp[i][j];for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){		dp[i][j]|=dp[i][k]&dp[k][j];}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cout<<dp[i][j]<<" ";cout<<endl;}return 0;
}

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

怎么还卡常捏？？？

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=3e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int inv[N],n,p;
void Pre(){inv[1]=1;for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
}
signed main(){cin>>n>>p;Pre();for(int i=1;i<=n;i++) printf("%d\n",inv[i]);return 0;
}

P3367 【模板】并查集

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,t,F[N];
int find(int x){if(F[x]==x) return x;return F[x]=find(F[x]);
}
int main(){cin>>n>>t;for(int i=1;i<=n;i++) F[i]=i;while(t--){int v1,v2,v3;cin>>v1>>v2>>v3;if(v1==1) F[find(v2)]=F[find(v3)];else cout<<(F[find(v2)]==F[find(v3)]?"Y":"N")<<endl;}return 0;
}

P5788 【模板】单调栈

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=3e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,a[N],stk[N],x,top,xiabiao[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>x;while(stk[top]<x) a[xiabiao[top]]=i,top--;stk[++top]=x,xiabiao[top]=i;}for(int i=1;i<=n;i++) cout<<a[i]<<" ";return 0;
}

P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=-1+(1<<31),mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],W[N],idx;
void add(int u,int v,int w){W[++idx]=w;edge[idx]=v;last[idx]=head[u];head[u]=idx;
}
int inq[N],d[N],n,m,s;
void SPFA(int st){for(int i=1;i<=n;i++) d[i]=inf;queue<int> q;d[st]=0,inq[st]=1; q.push(st);while(!q.empty()){int u=q.front(); q.pop(); inq[u]=0;for(int i=head[u],v;i;i=last[i]){v=edge[i];if (d[v]>d[u]+W[i]){d[v]=d[u]+W[i];if(!inq[v]) q.push(v);inq[v]=1;}}}
}
int main(){cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}SPFA(s);for(int i=1;i<=n;i++) cout<<d[i]<<" ";return 0;
}

P3366 【模板】最小生成树

#include<bits/stdc++.h>
#define int long long 
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct Node{int u,v,w;}edge[N];
bool cmp(Node x,Node y){return x.w<y.w;}
int n,m,f[N];
int find(int x){if(x==f[x]) return x;return f[x]=find(f[x]);
}
void kruskal(){sort(edge+1,edge+m+1,cmp);for(int i=1;i<=n;i++) f[i]=i;int ans=0,cnt=0;for(int i=1;i<=m;i++){if(cnt==n-1) break;int u=find(edge[i].u),v=find(edge[i].v);if(u==v) continue;ans+=edge[i].w,cnt++,f[u]=v;}if(cnt==n-1) cout<<ans;else cout<<"orz";
}
signed main(){cin>>n>>m;for(int i=1;i<=m;i++) cin>>edge[i].u>>edge[i].v>>edge[i].w;kruskal();return 0;
}

P4779 【模板】单源最短路径（标准版）

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=2147483647,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int W[N],head[N],edge[N],last[N],idx,d[N];
void add(int u,int v,int w){W[++idx]=w;edge[idx]=v;last[idx]=head[u];head[u]=idx;
}
int n,m,s;
bool vis[N];
void dijsktra(int st){priority_queue<pii,vector<pii>,greater<pii> > q;q.push({0,st});for(int i=1;i<=n;i++) d[i]=inf;d[st]=0;while(!q.empty()){pii t=q.top(); q.pop();if(vis[t.y]) continue;vis[t.y]=1;for(int i=head[t.y];i;i=last[i]){int v=edge[i];if(d[v]>d[t.y]+W[i]) d[v]=d[t.y]+W[i],q.push({d[v],v});}}
}
int main(){cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}dijsktra(s);for(int i=1;i<=n;i++) cout<<d[i]<<" ";return 0;
}

P3379 【模板】最近公共祖先（LCA）

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int fa[N][20],deep[N],head[2*N],edge[2*N],last[2*N],idx,n,m,root;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
void dfs(int x,int father){deep[x]=deep[father]+1;fa[x][0]=father;for(int i=1;(1<<i)<=deep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(int i=head[x];i;i=last[i]) if(edge[i]!=father) dfs(edge[i],x);
}
int LCA(int x,int y){if(deep[x]<deep[y]) swap(x,y);for(int i=19;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=fa[x][i];if(x==y) return x;for(int i=19;i>=0;i--){if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];}return fa[x][0];
}
int main(){cin>>n>>m>>root;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs(root,0);for(int i=1;i<=m;i++){int u,v;cin>>u>>v;cout<<LCA(u,v)<<endl;}return 0;
}

P3385 【模板】负环

多测不清空，爆零两行泪。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],W[N],idx;
void add(int u,int v,int w){W[++idx]=w;edge[idx]=v;last[idx]=head[u];head[u]=idx;
}
int inq[N],len[N],d[N],n,m,s;
bool SPFA(int st){for(int i=1;i<=n;i++) d[i]=inf;queue<int> q;d[st]=0,inq[st]=1; q.push(st);while(!q.empty()){int u=q.front(); q.pop(); inq[u]=0;for(int i=head[u],v;i;i=last[i]){v=edge[i];if (d[v]>d[u]+W[i]){d[v]=d[u]+W[i];len[v]=len[u]+1;if(len[v]>=n) return 1;if(!inq[v]) q.push(v);inq[v]=1;}}}return 0;
}
void init(){memset(head,0,sizeof(head));memset(edge,0,sizeof(edge));memset(last,0,sizeof(last));memset(inq,0,sizeof(inq));memset(len,0,sizeof(len));memset(W,0,sizeof(W));idx=0;
}
int main(){int T;cin>>T;while(T--){init();cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);if(w>=0) add(v,u,w);}cout<<(SPFA(1)?"YES":"NO")<<"\n";}return 0;
}

普及+/提高

P3388 【模板】割点（割顶）

#include<bits/stdc++.h> 
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],idx;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
int low[N],dfn[N],prt[N],mark[N],tot,sonCount,rt;
void Tarjan(int u){low[u]=dfn[u]=++tot;for(int i=head[u];i;i=last[i]){int v=edge[i];if(prt[u]==v) continue;//printf("            %d -> %d \n- dfn[u]=%d   low[u]=%d   prt[u]=%d\n- dfn[v]=%d   low[v]=%d   prt[v]=%d\n\n\n",u,v,dfn[u],low[u],prt[u],dfn[v],low[v],prt[v]);if(!dfn[v]){prt[v]=u;Tarjan(v);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){//cout<<u<<endl;mark[u]=1;if(u==rt) sonCount++;}}else low[u]=min(low[u],dfn[v]);}if(sonCount==1) mark[rt]=0;
}
int n,m;
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}for(int i=1;i<=n;i++) if(!dfn[i]) rt=i,sonCount=0,Tarjan(i);int ans=0;for(int i=1;i<=n;i++) if(mark[i]) ans++;cout<<ans<<endl;for(int i=1;i<=n;i++) if(mark[i]) cout<<i<<" ";return 0;
}

P3387 【模板】缩点

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
pii edge[N];
int U[N],V[N],p[N],d[N];
struct Graph{int head[N*2],edge[N*2],last[N*2],inq[N*2],W[N*2],idx;void add(int u,int v){inq[v]++;edge[++idx]=v;last[idx]=head[u];head[u]=idx;}void add(int u,int v,int w){W[idx+1]=w,add(u,v);}
}g1,g2;
stack<int> s;
int dfn[N],low[N],ins[N],bel[N],cnt[N],Ot[N],a[N],SCC,tot;
void Tarjan(int u){dfn[u]=low[u]=++tot;s.push(u);ins[u]=1;for(int i=g1.head[u];i;i=g1.last[i]){int v=g1.edge[i];if(dfn[v]==0){Tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){SCC++;while(true){int t=s.top();s.pop();bel[t]=SCC;p[SCC]+=a[t];ins[t]=0;if(t==u)break;}}
}
int n,m;
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){cin>>U[i]>>V[i];g1.add(U[i],V[i]);}for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);for(int i=1;i<=m;i++) edge[i]={bel[U[i]],bel[V[i]]};sort(edge+1,edge+m+1);for(int i=1;i<=m;i++){int u=edge[i].x,v=edge[i].y;if(u==v||edge[i]==edge[i-1]) continue;g2.add(u,v);}queue<int> q;for(int i=1;i<=SCC;i++) if(!g2.inq[i]) q.push(i);while(!q.empty()){int u=q.front(); q.pop();d[u]+=p[u];for(int i=g2.head[u];i;i=g2.last[i]){int v=g2.edge[i]; g2.inq[v]--;d[v]=max(d[v],d[u]);if(!g2.inq[v]) q.push(v);}}int ans=0; for(int i=1;i<=SCC;i++) ans=max(ans,d[i]);cout<<ans;return 0;
}

P3374 【模板】树状数组 1

#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int tree[N]={0};
void update(int x,int d){while(x<=N){tree[x]+=d;x+=lowbit(x);}
}
int sum(int x){int ans=0;while(x>0){ans+=tree[x];x-=lowbit(x);}return ans;
}
int a[N];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i]);}while(m--){int op,x,y;cin>>op>>x>>y;if(op==1) update(x,y);else cout<<sum(y)-sum(x-1)<<endl;}return 0;
}

P2197 【模板】Nim 游戏

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int x,sum,t,n;
int main(){cin>>t;while(t--){cin>>n;sum=0;for(int i=1;i<=n;i++){cin>>x;sum^=x;}cout<<(sum?"Yes":"No")<<endl;}return 0;
}

P3372 【模板】线段树 1

#include<bits/stdc++.h>
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
ll a[N],tree[N<<2],tag[N<<2];
void push_up(ll p){tree[p]=tree[ls(p)]+tree[rs(p)];//(-  ^  -)/
}
void build(ll p,ll pl,ll pr){tag[p]=0;if(pl==pr){tree[p]=a[pl];return;}ll mid=(pl+pr)>>1;build(ls(p),pl,mid);build(rs(p),mid+1,pr);push_up(p);
}
void addtag(ll p,ll pl,ll pr,ll d){ //lazy_tagtag[p]+=d;tree[p]+=d*(pr-pl+1);
} 
void push_down(ll p,ll pl,ll pr){if(tag[p]){ll mid=(pl+pr)>>1;addtag(ls(p),pl,mid,tag[p]);addtag(rs(p),mid+1,pr,tag[p]);tag[p]=0;}
}
void update(ll l,ll r,ll p,ll pl,ll pr,ll d){if(l<=pl&&pr<=r){addtag(p,pl,pr,d);return;}push_down(p,pl,pr);ll mid=(pl+pr)>>1;if(l<=mid) update(l,r,ls(p),pl,mid,d);if(r>mid) update(l,r,rs(p),mid+1,pr,d);push_up(p);
}
ll query(ll l,ll r,ll p,ll pl,ll pr){if(pl>=l&&r>=pr) return tree[p];push_down(p,pl,pr);ll res=0,mid=(pl+pr)>>1;if(l<=mid) res+=query(l,r,ls(p),pl,mid);if(r>mid) res+=query(l,r,rs(p),mid+1,pr);return res;
}
int main(){ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(m--){ll q,l,r,d;cin>>q;if(q==1){cin>>l>>r>>d;update(l,r,1,1,n,d);}else{cin>>l>>r;cout<<query(l,r,1,1,n)<<endl;}}return 0;
}

P3373 【模板】线段树 2

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int m; 
struct SEG{int tree[N*4],tgp[N*4],tgm[N*4],a[N];void pu(int x) {tree[x]=(tree[x<<1]+tree[x<<1|1])%m;}void pd(int x,int l,int r){if(tgm[x]!=1){tree[x<<1]=tree[x<<1]*tgm[x]%m,tree[x<<1|1]=tree[x<<1|1]*tgm[x]%m;tgp[x<<1]=tgp[x<<1]*tgm[x]%m,tgp[x<<1|1]=tgp[x<<1|1]*tgm[x]%m;tgm[x<<1]=tgm[x<<1]*tgm[x]%m,tgm[x<<1|1]=tgm[x<<1|1]*tgm[x]%m;tgm[x]=1;}if(tgp[x]){int mid=(l+r)>>1;tree[x<<1]+=(mid-l+1)*tgp[x];tree[x<<1|1]+=(r-mid)*tgp[x];tgp[x<<1]+=tgp[x],tgp[x<<1|1]+=tgp[x];tgp[x]=0;}}void bld(int x,int l,int r){if(l>r) return; tgm[x]=1;if(l==r) return tree[x]=a[l],void();int mid=(l+r)>>1;bld(x<<1,l,mid);bld(x<<1|1,mid+1,r);pu(x);}void updp(int x,int l,int r,int ql,int qr,int d){if(l>r) return; pd(x,l,r);if(ql<=l&&r<=qr) return tree[x]+=(r-l+1)*d,tgp[x]+=d,void();int mid=(l+r)>>1;if(ql<=mid) updp(x<<1,l,mid,ql,qr,d);if(mid<qr)  updp(x<<1|1,mid+1,r,ql,qr,d);pu(x);}void updm(int x,int l,int r,int ql,int qr,int d){if(l>r) return;pd(x,l,r);if(ql<=l&&r<=qr) return tree[x]=tree[x]*d%m,tgm[x]*=d,void(); int mid=(l+r)>>1;if(ql<=mid) updm(x<<1,l,mid,ql,qr,d);if(mid<qr)  updm(x<<1|1,mid+1,r,ql,qr,d);pu(x);}int qry(int x,int l,int r,int ql,int qr){if(l>r) return 0;if(ql<=l&&r<=qr) return tree[x];pd(x,l,r);int mid=(l+r)>>1,res=0;if(ql<=mid) res+=qry(x<<1,l,mid,ql,qr);if(mid<qr)  res+=qry(x<<1|1,mid+1,r,ql,qr);return res%m;}
}tr;
int n,q; 
signed main(){cin>>n>>q>>m;for(int i=1;i<=n;i++) cin>>tr.a[i];tr.bld(1,1,n);while(q--){int opt,x,y,k;cin>>opt>>x>>y;if(opt==3) cout<<tr.qry(1,1,n,x,y)<<"\n";if(opt==1) cin>>k,tr.updm(1,1,n,x,y,k);if(opt==2) cin>>k,tr.updp(1,1,n,x,y,k);}return 0;
}

P5905 【模板】全源最短路（Johnson）

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=1e9,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],W[N],idx;
void add(int u,int v,int w){W[++idx]=w;edge[idx]=v;last[idx]=head[u];head[u]=idx;
}int check[N],n,m;
bool vis[N],book[N];
int inq[N],len[N],d[N],dist[N];
bool spfa(int st){for(int i=1;i<=n;i++) d[i]=inf;queue<int> q;d[st]=0,inq[st]=1; q.push(st);while(!q.empty()){int u=q.front(); q.pop(); inq[u]=0;for(int i=head[u],v;i;i=last[i]){v=edge[i];if (d[v]>d[u]+W[i]){d[v]=d[u]+W[i];len[v]=len[u]+1;if(len[v]>n) return 1;if(!inq[v]) q.push(v);inq[v]=1;}}}return 0;
}
void dijsktra(int st){priority_queue<pii,vector<pii>,greater<pii> > pq;for(int i=1;i<=n;i++) dist[i]=inf;memset(vis,0,sizeof(vis));dist[st]=0;pq.push({0,st});while(!pq.empty()){pii top=pq.top(); pq.pop();int u=top.y,d=top.x;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=last[i]){int v=edge[i],w=W[i];if(dist[v]<=dist[u]+w) continue;dist[v]=dist[u]+w;pq.push({dist[v],v});}}
}
signed main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}for(int i=1;i<=n;i++) add(0,i,0);if(spfa(0)) return cout<<-1,0;for(int u=1;u<=n;u++) for(int i=head[u];i;i=last[i]) W[i]=W[i]+d[u]-d[edge[i]];for(int u=1;u<=n;u++){dijsktra(u);int ans=0;for(int v=1;v<=n;v++) ans+=v*(dist[v]==inf?inf:dist[v]+d[v]-d[u]);cout<<ans<<endl;}return 0;
}

P3390 【模板】矩阵快速幂

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=110,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct Node{ll v[N][N];
}ans,a,b,c;
ll n=2,m=2,k=2,l,p;
Node mul(Node a,Node b){Node c;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c.v[i][j]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int l=1;l<=n;l++) c.v[i][j]=(c.v[i][j]+a.v[i][l]*b.v[l][j]%mod)%mod;}}return c;
}
Node quickMi(Node a,ll l){Node ans;for(int i=1;i<=n;i++) ans.v[i][i]=1;while(l){if(l&1) ans=mul(ans,a);a=mul(a,a),l>>=1;	}return ans;
}
int main(){cin>>n>>l;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a.v[i][j];for(int i=1;i<=n;i++) ans.v[i][i]=1;ans=quickMi(a,l);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<ans.v[i][j]<<" ";}cout<<endl;}return 0;
} 

P1939 矩阵加速（数列）

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=110,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/*
[1 0 1]
[1 0 0]
[0 1 0]
*/
struct Node{ll v[N][N];
}a;
ll n=3,m=3,k=3,l,p;
Node mul(Node a,Node b){Node c;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c.v[i][j]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int l=1;l<=n;l++) c.v[i][j]=(c.v[i][j]+a.v[i][l]*b.v[l][j]%mod)%mod;}}return c;
}
Node quickMi(Node a,ll l){Node ans;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans.v[i][j]=0;for(int i=1;i<=n;i++) ans.v[i][i]=1;while(l){if(l&1) ans=mul(ans,a);a=mul(a,a),l>>=1;	}return ans;
}
int main(){int t;cin>>t;a.v[1][1]=a.v[1][2]=a.v[2][3]=a.v[3][1]=1;while(t--){cin>>l;Node ans=quickMi(a,l);cout<<ans.v[1][2]<<endl;}return 0;
} 

P1439 【模板】最长公共子序列

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,f[N],a[N],b[N],mp[N],len;
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]=i;for(int i=1;i<=n;i++) cin>>b[i],f[i]=inf;for(int i=1;i<=n;i++){if(mp[b[i]]>f[len]) f[++len]=mp[b[i]];else{int l=1,r=len,ans;while(l<=r){int mid=(l+r)>>1;if(f[mid]>mp[b[i]]) r=mid-1,ans=mid;else l=mid+1;}f[ans]=min(mp[b[i]],f[ans]);}}cout<<len;return 0;
}

P5960 【模板】差分约束

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],W[N],idx;
void add(int u,int v,int w){W[++idx]=w;edge[idx]=v;last[idx]=head[u];head[u]=idx;
}
int inq[N],len[N],d[N],n,m,s,C,flag;
ll ans;
bool SPFA(){queue<int> q;for(int i=1;i<=n;i++){inq[i]=1;q.push(i);}while(!q.empty()){int u=q.front(); q.pop(); inq[u]=0;for(int i=head[u],v;i;i=last[i]){v=edge[i];if (d[v]<d[u]+W[i]){d[v]=d[u]+W[i];C=min(C,d[v]);len[v]=len[u]+1;if(len[v]>=n) return 1;if(!inq[v]) q.push(v);inq[v]=1;}}}return 0;
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,-w);}if(flag||SPFA()) return cout<<"NO",0;for(int i=1;i<=n;i++) cout<<d[i]-C<<" ";return 0;
}

P3386 【模板】二分图最大匹配

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,e;
int head[N],edge[N],last[N],idx;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
bool vis[N];
int match[N];
bool fndpth(int u){for(int i=head[u],v;i;i=last[i]){v=edge[i];if(!vis[v]){vis[v]=1;if(!match[v]||fndpth(match[v])){match[v]=u;return 1;}}}return 0;
}
int mxMtch(){int ans=0;memset(match,0,sizeof match);for(int u=1;u<=n;u++){memset(vis,0,sizeof vis);if(fndpth(u)) ans++;}return ans;
}
int main(){cin>>n>>m>>e;for(int i=1;i<=e;i++){int u,v;cin>>u>>v;add(u,v+n);add(v+n,u);}cout<<mxMtch();return 0;
}

P3375 【模板】KMP

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
string a,b;
int nxt[N],n,m,cur;
void prepare(){nxt[1]=0; cur=0;for(int i=2;i<=n;i++){while(cur&&a[cur+1]!=a[i]) cur=nxt[cur];if(a[cur+1]==a[i]) nxt[i]=++cur;else nxt[i]=0;}
}
int main(){cin>>b>>a; n=a.size(),m=b.size();a=' '+a; b=' '+b;prepare();cur=0;for(int i=1;i<=m;i++){while(cur>0&&a[cur+1]!=b[i]) cur=nxt[cur];if(a[cur+1]==b[i]) cur++;if(cur==n) cout<<i-n+1<<endl;}for(int i=1;i<=n;i++) cout<<nxt[i]<<" ";return 0;
}

P1962 斐波那契数列

只是想存一下好看的代码。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct Matrix
{int row , col;ll ml [N][N];void init (){for ( int i = 1; i <= row; i++)for( int j = 1; j <= col; j++)ml [i][j] = 0;}void SetUnit ( int l ){row = col = l;for ( int i = 1; i <= l; i++)ml[i][i] = 1;}void SetFib (){row = col = 2;ml [2][2] = 0;ml [1][1] = ml [1][2] = ml [2][1] =1;}void output (){printf("row = %d ; col = %d ;\n",row ,col);for ( int i = 1; i <= row; i++){for( int j = 1; j <= col; j++)cout << ml [i][j] << " ";cout << endl;}}Matrix operator * ( const Matrix & a ) const{Matrix ans;ans .row = a. row;ans .col =    col;ans .init ();for (int i = 1; i <= a .row; i++)for (int j = 1; j <=    col; j++)for (int k = 1; k <= a .col; k++) ans .ml [i][j] = ( ans .ml [i][j] + ( a .ml [i][k] * ml [k][j] ) % mod ) % mod;return ans;}};Matrix operator ^ ( const Matrix & Ma , const ll & Mb)
{Matrix ans , a = Ma;ans .row = a .row;ans .col = a .col;ans .SetUnit (2); ll b = Mb;while ( b ){if ( b & 1 ) ans = a * ans;a = a * a , b >>= 1;}return ans;
}
Matrix tot;
int main ()
{tot .SetFib();ll l;cin >> l;tot = tot ^ l;cout << tot .ml[1][2];return 0;
}

提高+/省选-

P3812 【模板】线性基

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int ans;
int n,m=60,a[N],p[N];
void insert(int x){for(int i=m;~i;i--){if(!((x>>i)&1ll)) continue;if(!p[i]) return p[i]=x,void();x^=p[i]; }return;
}
signed main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],insert(a[i]);for(int i=m;~i;i--) ans=max(ans,ans^p[i]);cout<<ans;return 0;
}

P4782 【模板】2-SAT

#include<bits/stdc++.h>
#define nx(x) ((((x)-1)^1)+1)
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int head[N],edge[N],last[N],idx;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
int dfn[N],low[N],ins[N],bel[N],cnt[N],Ot[N],SCC,tot;
stack<int> s;
void Tarjan(int u){dfn[u]=low[u]=++tot;s.push(u);ins[u]=1;for(int i=head[u];i;i=last[i]){int v=edge[i];if(dfn[v]==0){Tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){SCC++;while(true){int t=s.top();s.pop();bel[t]=SCC;cnt[SCC]++;ins[t]=0;if(t==u)break;}}
}
int n,m;
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,a,b;cin>>u>>a>>v>>b;add(u*2-a,v*2-1+b);add(v*2-b,u*2-1+a);}for(int i=1;i<=n*2;i++) if(!dfn[i]) Tarjan(i);for(int i=1;i<=n;i++) if(bel[i*2]==bel[i*2-1]) return cout<<"IMPOSSIBLE",0;cout<<"POSSIBLE\n";for(int i=1;i<=n;i++){if(bel[i*2-1]>bel[i*2]) cout<<1<<" ";else cout<<0<<" ";}return 0;
}

P5490 【模板】扫描线&&矩形面积并

#include<bits/stdc++.h>
#define int long long
#define lc (x<<1)
#define rc (x<<1|1)
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int tot,n,Ls[N],Lsn;
struct seg{ll l,r,mn,cnt,add;
}t[N*8];
void pushUp(ll x){t[x].mn=min(t[lc].mn,t[rc].mn);t[x].cnt=0;if(t[x].mn==t[lc].mn)t[x].cnt+=t[lc].cnt;if(t[x].mn==t[rc].mn)t[x].cnt+=t[rc].cnt;
}void pushAdd(ll x,ll add){t[x].mn+=add;t[x].add+=add;
}void pushDown(ll x){if(t[x].add!=0){pushAdd(lc,t[x].add);pushAdd(rc,t[x].add);t[x].add=0;}
}
void Build(ll x,ll l,ll r){t[x].l=l;t[x].r=r;if(l==r){t[x].cnt=Ls[l+1]-Ls[l];t[x].mn=0;return;}ll mid=(l+r)>>1;Build(lc,l,mid);Build(rc,mid+1,r);pushUp(x);
}
void Add(ll x,ll l,ll r,ll add){if(l<=t[x].l&&t[x].r<=r){pushAdd(x,add);return;}pushDown(x);ll mid=(t[x].l+t[x].r)>>1;if(l<=mid)Add(lc,l,r,add);if(r>mid)Add(rc,l,r,add);pushUp(x);
}
ll Sum(){if(t[1].mn==0)return Ls[Lsn]-Ls[1]-t[1].cnt;return Ls[Lsn]-Ls[1];
}
struct Real{int x1,y1,x2,y2;
}r[N];
struct Bound{int flag,h,l,r;
}B[N];
bool cmp(Bound x,Bound y){return x.h<y.h;}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>r[i].x1;cin>>r[i].y1;cin>>r[i].x2;cin>>r[i].y2;Ls[++Lsn]=r[i].x1;Ls[++Lsn]=r[i].x2;}sort(Ls+1,Ls+Lsn+1);Lsn=unique(Ls+1,Ls+Lsn+1)-Ls-1;for(ll i=1;i<=n;i++){r[i].x1=lower_bound(Ls+1,Ls+Lsn+1,r[i].x1)-Ls;r[i].x2=lower_bound(Ls+1,Ls+Lsn+1,r[i].x2)-Ls;B[++tot]=(Bound){1,r[i].y1,r[i].x1,r[i].x2};B[++tot]=(Bound){-1,r[i].y2,r[i].x1,r[i].x2};}sort(B+1,B+tot+1,cmp);Build(1,1,Lsn-1);ll ans=0;for(ll i=1;i<=tot;i++){if(i>1) ans+=(B[i].h-B[i-1].h)*Sum();Add(1,B[i].l,B[i].r-1,B[i].flag);}cout<<ans;return 0;
}

P3389 【模板】高斯消元法

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=1e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
const double eps=1e-7;
struct Mat{int n,m;double mx[N][N];void chk(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<<mx[i][j]<<" ";cout<<"\n";}cout<<"\n";}void gk(int i,double k) {for(int x=1;x<=m;x++) mx[i][x]/=k;} void sw(int i,int j) {if(i==j) return;for(int x=1;x<=m;x++) swap(mx[i][x],mx[j][x]);}void ad(int i,int j,double k) {if(!i||!j||i==j) return;for(int x=1;x<=m;x++) mx[j][x]+=k*mx[i][x];}void gs(){for(int i=1,l=1;i<=m&&l<=n;i++){double f=0; int ans=0;for(int j=l;j<=n;j++) if(fabs(mx[j][i])>fabs(f)) ans=j,f=mx[j][i];if(fabs(f)<eps) continue; sw(l,ans);gk(l,f);for(int j=1;j<=n;j++) ad(l,j,-mx[j][i]);++l;}}
}M;
int n;
signed main(){cin>>n; M.n=n,M.m=n+1;for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)cin>>M.mx[i][j];M.gs();if(fabs(M.mx[n][n])<eps) return cout<<"No Solution",0;for(int i=1;i<=n;i++) printf("%.2lf\n",M.mx[i][n+1]); return 0;
}

P3919 【模板】可持久化线段树 1（可持久化数组）

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,a[N];
struct seg{int lc,rc,v;
}t[N*30];
int tot,rt[N];
void build(int &x,int l,int r){x=++tot;if(l==r) {t[x].v=a[l];return;};int mid=(l+r)>>1;build(t[x].lc,l,mid);build(t[x].rc,mid+1,r);
}
int query(int x,int l,int r,int pos){if(l==r) return t[x].v;int mid=(l+r)>>1;if(pos<=mid) return query(t[x].lc,l,mid,pos);else return         query(t[x].rc,mid+1,r,pos);
}
void insert(int &x,int lastx,int l,int r,int p,int v){t[x=++tot]=t[lastx];if(l==r) {t[x].v=v;return;}int mid=(l+r)>>1;if(p<=mid) insert(t[x].lc,t[lastx].lc,l,mid,p,v);else       insert(t[x].rc,t[lastx].rc,mid+1,r,p,v);
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",a+i);build(rt[0],1,n);for(int i=1,ver,op,p,v;i<=m;i++){scanf("%d%d",&ver,&op);if(op==1){scanf("%d%d",&p,&v);insert(rt[i],rt[ver],1,n,p,v);}else{scanf("%d",&p);cout<<query(rt[ver],1,n,p)<<endl;rt[i]=rt[ver];}}return 0;
}

P3834 【模板】可持久化线段树 2

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,a[N];
struct seg{int lc,rc,v,siz;
}t[N*30];
int tot,rt[N];
void build(int &x,int l,int r){x=++tot;if(l==r) {t[x].v=a[l];return;};int mid=(l+r)>>1;build(t[x].lc,l,mid);build(t[x].rc,mid+1,r);
}
int nodeSize(int xl,int xr){return t[xr].siz-t[xl].siz;}
int query(int xl,int xr,int l,int r,int k){if(l==r) return l;int mid=(l+r)>>1,siz=nodeSize(t[xl].lc,t[xr].lc);if(k<=siz) return query(t[xl].lc,t[xr].lc,l,mid,k);else return query(t[xl].rc,t[xr].rc,mid+1,r,k-siz);
}
void insert(int &x,int lastx,int l,int r,int p){t[x=++tot]=t[lastx],t[x].siz++;if(l==r) return;int mid=(l+r)>>1;if(p<=mid) insert(t[x].lc,t[lastx].lc,l,mid,p);else       insert(t[x].rc,t[lastx].rc,mid+1,r,p);
}
int mna=INT_MAX,mxa=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],mna=min(mna,a[i]),mxa=max(mxa,a[i]);for(int i=1;i<=n;i++) insert(rt[i],rt[i-1],mna,mxa,a[i]);for(int i=1,l,r,k;i<=m;i++){cin>>l>>r>>k;cout<<query(rt[l-1],rt[r],mna,mxa,k)<<endl;}return 0;
}

P5787 二分图 /【模板】线段树分治

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
stack<pii> stk;
int f[N*2],sz[N*2];
struct Edg{int u,v;}edg[N];
int find(int x) {return x==f[x]?x:find(f[x]);}
void merge(int u,int v){u=find(u),v=find(v);if(u==v) return;if(sz[u]>sz[v]) swap(u,v);f[u]=v,sz[v]+=sz[u],stk.push({u,v});
}
void undo(){pii top=stk.top(); stk.pop();int u=top.x,v=top.y;f[u]=u,sz[v]-=sz[u];
}
vector<int> tree[N*4];
void upd(int x,int l,int r,int ql,int qr,int d){if(ql<=l&&r<=qr) return tree[x].push_back(d),void();int mid=(l+r)>>1;if(ql<=mid) upd(x<<1,l,mid,ql,qr,d);if(mid<qr)  upd(x<<1|1,mid+1,r,ql,qr,d);
}
int n,m,k;
void Solve(int x,int l,int r){int lt=stk.size(),ans=1;for(int e:tree[x]){int u=edg[e].u,v=edg[e].v;if(find(u)==find(v)){for(int i=l;i<=r;i++) cout<<"No\n";ans=0; break; }merge(u+n,v),merge(u,v+n);}if(ans){if(l==r) return puts("Yes"),void();int mid=(l+r)>>1;Solve(x<<1,l,mid);Solve(x<<1|1,mid+1,r);}while(stk.size()!=lt) undo();
}
signed main(){cin>>n>>m>>k;while(m--){int u,v,l,r;cin>>u>>v>>l>>r;edg[m]={u,v};upd(1,1,k,l+1,r,m);}for(int i=1;i<=n*2;i++) f[i]=i,sz[i]=1;Solve(1,1,k);return 0;
}

P3369 【模板】普通平衡树

这并不普通。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int ch[N][2],fa[N],val[N],siz[N],num[N];
int tot,rt,n;void visitVal(int x){if(ch[x][0])visitVal(ch[x][0]);if(val[x]!=inf&&val[x]!=-inf){cout<<val[x];if(num[x]>1) cout<<"("<<num[x]<<")";cout<<" ";}else if(val[x]==inf)           cout<<"+inf\n";else                           cout<<"-inf ";if(ch[x][1])visitVal(ch[x][1]);
}void visitNum(int x){if(ch[x][0])visitNum(ch[x][0]);cout<<num[x]<<" ";if(ch[x][1])visitNum(ch[x][1]);
}void pushUp(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+num[x];
}void rotate(int x,int &f){int y=fa[x],z=fa[y],L=(ch[y][0]!=x),R=(L^1);if(y==f)f=x;else if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;fa[x]=z;fa[y]=x;fa[ch[x][R]]=y;ch[y][L]=ch[x][R];ch[x][R]=y;pushUp(y);pushUp(x);
}void Splay(int x,int &f){while(x!=f){int y=fa[x],z=fa[y];if(y!=f){if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,f);else rotate(y,f);}rotate(x,f);}
}
void init(){rt=1;tot=2;fa[2]=1;ch[1][1]=2;val[1]=-inf;val[2]=+inf;siz[2]=1;num[1]=1;siz[1]=2;num[2]=1;
}int insert(int& x,int f,int v){if(!x){x=++tot;val[x]=v;siz[x]=num[x]=1;fa[x]=f;return x;}if(val[x]==v){num[x]++;return x;}else if(val[x]<v)return insert(ch[x][1],x,v);else return insert(ch[x][0],x,v);
}void insert(int v){int x=insert(rt,0,v);Splay(x,rt);
}int findPrev(){int x=ch[rt][0];while(ch[x][1])x=ch[x][1];return x;
}int findNext(){int x=ch[rt][1];while(ch[x][0])x=ch[x][0];return x;
}int find(int x,int v){if(val[x]==v)return x;if(val[x]>v)return find(ch[x][0],v);return find(ch[x][1],v);
}void remove(int v){int x=find(rt,v);Splay(x,rt);if(num[x]>1){num[x]--;return;}int prev=findPrev();int next=findNext();Splay(prev,rt);Splay(next,ch[rt][1]);ch[next][0]=fa[x]=0;pushUp(next);pushUp(prev);
}int queryRank(int v){insert(v);int x=find(rt,v);Splay(x,rt);int ans=siz[ch[x][0]];remove(v);return ans;
}int findKth(int x,int k){if(siz[ch[x][0]]>=k)return findKth(ch[x][0],k);if(siz[ch[x][0]]+num[x]>=k)return x;return findKth(ch[x][1],k-siz[ch[x][0]]-num[x]);
}
int findKth(int k){return val[findKth(rt,k+1)];
}int findPre(int v){insert(v);int prev=findPrev();int ans=val[prev];remove(v);return ans;
}int findNxt(int v){insert(v);int next=findNext();int ans=val[next];remove(v);return ans;
}int main(){init();scanf("%d",&n);while(n--){int opt,x;scanf("%d%d",&opt,&x);if(opt==1) insert(x);if(opt==2) remove(x);if(opt==3) cout<<queryRank(x)<<endl;if(opt==4) cout<<findKth(x)<<endl;if(opt==5) cout<<findPre(x)<<endl;if(opt==6) cout<<findNxt(x)<<endl;}return 0;
}

P6136 【模板】普通平衡树（数据加强版）

FHQ

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=2e9,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,tot,rt,lst,t,ans;
struct Node {int val,key,siz,ls,rs;}tr[N];
int nw(int x) {tr[++tot]={x,rand(),1}; return tot;}
void pushUp(int x) {tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+1;}
void Split(int p,int &x,int &y,int k){if(!p) return x=y=0,void();if(tr[p].val<=k) x=p,Split(tr[p].rs,tr[p].rs,y,k);else y=p,Split(tr[p].ls,x,tr[p].ls,k);pushUp(p);
}
int merge(int u,int v){if(!u||!v) return u+v;if(tr[u].key<tr[v].key) return tr[u].rs=merge(tr[u].rs,v),pushUp(u),u;return tr[v].ls=merge(u,tr[v].ls),pushUp(v),v;
}
void insert(int k){int x,y;Split(rt,x,y,k);rt=merge(merge(x,nw(k)),y);
}
void remove(int v){int x,y,z;Split(rt,x,y,v);Split(x,x,z,v-1);z=merge(tr[z].ls,tr[z].rs);rt=merge(merge(x,z),y);
}
int find(int v){int x,y,ans;Split(rt,x,y,v-1);ans=tr[x].siz+1;merge(x,y);return ans;
}
int findKth(int x,int v){if(tr[tr[x].ls].siz==v-1) return tr[x].val;if(tr[tr[x].ls].siz>v-1) return findKth(tr[x].ls,v);return findKth(tr[x].rs,v-1-tr[tr[x].ls].siz);
}
int findPre(int v){int x,y,ans;Split(rt,x,y,v-1);ans=findKth(x,tr[x].siz);merge(x,y);return ans;
}
int findNxt(int v){int x,y,ans;Split(rt,x,y,v);ans=findKth(y,1);merge(x,y);return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&t),insert(t);while(m--){int opt,x;scanf("%d%d",&opt,&x);x=x^lst;if(opt==1) insert(x);else if(opt==2) remove(x);else if(opt==3) lst=find(x);else if(opt==4) lst=findKth(rt,x);else if(opt==5) lst=findPre(x);else if(opt==6) lst=findNxt(x);if(opt>2) ans^=lst;}printf("%d",ans);return 0;
}

P3391 【模板】文艺平衡树

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1e6+10,inf=2e9,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,tot,rt,lst,t,ans;
struct Node {int val,key,siz,ls,rs,lazy;}tr[N];
int nw(int x) {tr[++tot]={x,rand(),1}; return tot;}
void pushDn(int x) {if(tr[x].lazy) swap(tr[x].ls,tr[x].rs),tr[tr[x].ls].lazy^=1,tr[tr[x].rs].lazy^=1,tr[x].lazy=0;}
void pushUp(int x) {tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+1;}
void Split(int p,int &x,int &y,int k){if(!p) return x=y=0,void(); pushDn(p);if(tr[tr[p].ls].siz+1<=k) x=p,Split(tr[p].rs,tr[p].rs,y,k-tr[tr[p].ls].siz-1);else y=p,Split(tr[p].ls,x,tr[p].ls,k);pushUp(p);
}
int merge(int u,int v){if(!u||!v) return u+v;if(tr[u].key<tr[v].key) return pushDn(u),tr[u].rs=merge(tr[u].rs,v),pushUp(u),u;return pushDn(v),tr[v].ls=merge(u,tr[v].ls),pushUp(v),v;
}
void insert(int k){int x,y;Split(rt,x,y,k);rt=merge(merge(x,nw(k)),y);
}
void print(int x){if(!x) return;pushDn(x);print(tr[x].ls);cout<<tr[x].val<<" ";print(tr[x].rs);
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) insert(i);while(m--){int l,r,p,x,y;cin>>x>>y;Split(rt,l,r,y);Split(l,l,p,x-1);tr[p].lazy^=1;rt=merge(merge(l,p),r);}print(rt);return 0;
}

P5829 【模板】失配树

从 1 开始啊啊啊啊啊啊aaaa！！！！！
KMP+LCA

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
string a,b;
int nxt[N],n,m,cur;
int fa[N][25],deep[N],head[2*N],edge[2*N],last[2*N],idx,root;
void add(int u,int v){edge[++idx]=v;last[idx]=head[u];head[u]=idx;
}
int LCA(int x,int y){if(deep[x]<deep[y]) swap(x,y);for(int i=19;~i;i--) if(deep[x]-(1<<i)>=deep[y]) x=fa[x][i];if(x==y) return x;for(int i=19;~i;i--)if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0];
}
void prepare(){nxt[1]=0; cur=0;for(int i=2;i<=n;i++){while(cur&&a[cur+1]!=a[i]) cur=nxt[cur];if(a[cur+1]==a[i]) nxt[i]=++cur;else nxt[i]=0;}for(int u=1;u<=n;u++){fa[u][0]=nxt[u];deep[u]=deep[nxt[u]]+1;for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];}
}
int main(){cin>>a; n=a.size();a=" "+a;prepare();cin>>m;while(m--){int u,v;cin>>u>>v;cout<<LCA(fa[u][0],fa[v][0])<<endl;}return 0;
}

P4525 【模板】自适应辛普森法 1

我是积分大佬。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
double a,b,c,d,l,r,ans;
signed main(){cin>>a>>b>>c>>d>>l>>r; if(a==0) ans=c/2/b*(r*r-l*l)+d/b*(r-l);else ans=c*(r-l)/a+(-c*b/a+d)*log((a*r+b)/(a*l+b))/a;printf("%.6lf",ans);return 0;
}

P7112 【模板】行列式求值

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=8e2+10,inf=0x3f3f3f3f;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int mod;
int qm(int a,int b){int res=1;while(b){if(b&1) res=(res*a)%mod;a=a*a%mod,b>>=1;} return res;
}
const double eps=1e-7;
struct Mat{int n,m,res=1,a[N][N];int det(){int l=1,w=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){while(a[i][i]){int div=a[j][i]/a[i][i];for(int k=i;k<=n;k++) a[j][k]=(a[j][k]-div*a[i][k]%mod+mod)%mod;swap(a[i],a[j]),w=-w;}swap(a[i],a[j]); w=-w;}}for(int i=1;i<=n;i++) res=(res*a[i][i])%mod;return (res*w+mod)%mod;}
}M;
int n;
signed main(){cin>>n>>mod; M.n=n,M.m=n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>M.a[i][j];cout<<M.det();return 0;
}

P3384 【模板】重链剖分/树链剖分

#include<bits/stdc++.h>
#define int long long
#define ls(x) (x)<<1
#define rs(x) (x)<<1|1
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct Graph{int head[N*2],edge[N*2],last[N*2],inq[N*2],W[N*2],idx;void add(int u,int v){inq[v]++;edge[++idx]=v;last[idx]=head[u];head[u]=idx;}void add(int u,int v,int w){W[idx+1]=w,add(u,v);}
}g;
struct SEG{int tree[N*4],a[N],tag[N*4];void pushup(int x) {tree[x]=tree[ls(x)]+tree[rs(x)];}void addtag(int x,int l,int r,int v) {tag[x]+=v,tree[x]+=v*(r-l+1);}void build(int p,int pl,int pr){if(pl==pr) return tree[p]=a[pl],void();int mid=(pl+pr)>>1;build(ls(p),pl,mid);build(rs(p),mid+1,pr);pushup(p);}void pushdn(int x,int l,int r){if(tag[x]){int mid=(l+r)>>1;addtag(ls(x),l,mid,tag[x]);addtag(rs(x),mid+1,r,tag[x]);tag[x]=0;}}void upd(int l,int r,int pl,int pr,int p,int v){if(pr<l||pl>r) return;if(l<=pl&&pr<=r) return addtag(p,pl,pr,v),void();int mid=(pl+pr)>>1;pushdn(p,pl,pr);upd(l,r,pl,mid,ls(p),v);upd(l,r,mid+1,pr,rs(p),v);pushup(p);}int qry(int l,int r,int pl,int pr,int p){if(l<=pl&&pr<=r) return tree[p];pushdn(p,pl,pr);int mid=(pl+pr)>>1,res=0;if(l<=mid) res+=qry(l,r,pl,mid,ls(p));if(mid<r)  res+=qry(l,r,mid+1,pr,rs(p));return res;}
}tr;
int n,m,r,p,wt[N];
int mson[N],dep[N],f[N],siz[N];
void dfs1(int u,int fa){dep[u]=dep[fa]+1;f[u]=fa,siz[u]=1;int ms=-1;for(int i=g.head[u];i;i=g.last[i]){int v=g.edge[i];if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>ms) ms=siz[v],mson[u]=v;}
}
int top[N],id[N],cnt;
void dfs2(int u,int tf){id[u]=++cnt;top[u]=tf;tr.a[cnt]=wt[u];if(!mson[u]) return; dfs2(mson[u],tf);for(int i=g.head[u];i;i=g.last[i]){int v=g.edge[i];if(v==f[u]||v==mson[u]) continue;dfs2(v,v);}
}
int qr(int x,int y){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans=(ans+tr.qry(id[top[x]],id[x],1,n,1))%p;//cout<<ans<<" "<<x<<"->"<<f[top[x]]<<"\n";x=f[top[x]]; }if(dep[x]>dep[y]) swap(x,y);return (ans+tr.qry(id[x],id[y],1,n,1))%p; 
}
void ur(int x,int y,int v){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);tr.upd(id[top[x]],id[x],1,n,1,v%p);x=f[top[x]];}if(dep[x]>dep[y]) swap(x,y);tr.upd(id[x],id[y],1,n,1,v%p);
}
int qs(int u) {return tr.qry(id[u],id[u]+siz[u]-1,1,n,1)%p;}
void us(int u,int v) {tr.upd(id[u],id[u]+siz[u]-1,1,n,1,v%p);}
signed main(){cin>>n>>m>>r>>p;for(int i=1;i<=n;i++) cin>>wt[i];for(int i=1;i<n;i++){int u,v;cin>>u>>v;g.add(u,v);g.add(v,u);}dfs1(r,0);dfs2(r,r);tr.build(1,1,n);while(m--){int opt,x,y,v;cin>>opt>>x;if(opt<3) cin>>y;if(opt==1||opt==3) cin>>v;if(opt==1) ur(x,y,v);if(opt==2) cout<<qr(x,y)<<"\n";if(opt==3) us(x,v);if(opt==4) cout<<qs(x)<<"\n";}return 0;
}

P4783 【模板】矩阵求逆

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=8e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int qm(int a,int b){int res=1;while(b){if(b&1) res=(res*a)%mod;a=a*a%mod,b>>=1;} return res;
}
const double eps=1e-7;
struct Mat{int n,m,ck=0,mx[N][N];void chk(int lx,int rx,int ly,int ry){for(int i=lx;i<=rx;i++){for(int j=ly;j<=ry;j++)cout<<(mx[i][j]+mod)%mod<<" ";cout<<"\n";}cout<<"\n";}void gk(int i,int k) {for(int x=1;x<=m;x++) mx[i][x]=mx[i][x]*qm(k,mod-2)%mod;} void sw(int i,int j) {if(i==j) return;for(int x=1;x<=m;x++) swap(mx[i][x],mx[j][x]);}void ad(int i,int j,int k) {if(!i||!j||i==j) return;for(int x=1;x<=m;x++) mx[j][x]=((mx[j][x]+k*mx[i][x])%mod+mod)%mod;}void gs(){int l=1;for(int i=1;i<=n&&l<=n;i++){double f=0; int ans=0;for(int j=l;j<=n;j++) if(fabs(mx[j][i])>fabs(f)) ans=j,f=mx[j][i];if(fabs(f)<eps) continue; sw(l,ans);gk(l,f);for(int j=1;j<=n;j++) ad(l,j,-mx[j][i]);++l;}}
}M;
int n;
signed main(){cin>>n; M.n=n,M.m=n*2;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>M.mx[i][j];for(int i=1;i<=n;i++)M.mx[i][i+n]=1;M.gs();if(fabs(M.mx[n][n])<eps) return cout<<"No Solution",0;M.chk(1,n,n+1,n*2);return 0;
}

P3377 【模板】左偏树/可并堆

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct TSB{int lc,rc,d,val;
}tr[N];
int n,m,a[N],f[N],del[N];
int find(int x) {return x==f[x]?x:f[x]=find(f[x]);} 
int merge(int x,int y){if(!x||!y) return x+y;if(tr[x].val>tr[y].val) swap(x,y);tr[x].rc=merge(tr[x].rc,y);if(tr[tr[x].lc].d<tr[tr[x].rc].d) swap(tr[x].rc,tr[x].lc);tr[x].d=tr[tr[x].rc].d+1;return x;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>tr[i].val,f[i]=i;while(m--){int opt,x,y;cin>>opt>>x;if(opt==1){cin>>y;if(del[x]||del[y]) continue; x=find(x),y=find(y);if(x!=y) f[x]=f[y]=merge(x,y);}if(opt==2){if(del[x]) {cout<<"-1\n";continue;}x=find(x);cout<<tr[x].val<<"\n"; del[x]=1; int l=tr[x].lc,r=tr[x].rc;f[l]=f[r]=f[x]=merge(l,r);tr[x]={0,0,0,0}; }}return 0;
}

省选/NOI-

P3380 【模板】树套树

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10,inf=2147483647;
int n,m,op,x,y,k,tot=2,rt[N],a[N];  //rt：每个区间的根
struct A{int cnt,sz,fa,vl,s[2];  //数量、size、father、val、son
}tr[N];
void psu(int x){tr[x].sz=tr[tr[x].s[0]].sz+tr[tr[x].s[1]].sz+tr[x].cnt;}
int nw(int k,int fa){  //新建++tot;tr[tot].vl=k,tr[tot].fa=fa,tr[tot].cnt=tr[tot].sz=1;return tot;
}
void rot(int x){  //转int y=tr[x].fa,z=tr[y].fa,k=(tr[y].s[0]==x);tr[z].s[tr[z].s[1]==y]=x,tr[x].fa=z;tr[y].s[!k]=tr[x].s[k],tr[tr[x].s[k]].fa=y;tr[x].s[k]=y,tr[y].fa=x;psu(y),psu(x);
}
void spl(int &rt,int x,int k){  //转（Splay）for(int y;(y=tr[x].fa)!=k;rot(x))if(tr[y].fa!=k) rot((tr[y].s[1]==x)^(tr[tr[y].fa].s[1]==y)?x:y);if(!k) rt=x;
}
void ins(int &rt,int k){int x=rt,fa=0;while(x){if(tr[x].vl==k) return ++tr[x].cnt,spl(rt,x,0),void();fa=x,x=tr[x].s[tr[x].vl<k];}tr[fa].s[tr[fa].vl<k]=x=nw(k,fa),spl(rt,x,0);
}
int pre(int x,int k){int ans=-inf,pos=1;while(x)if(k<=tr[x].vl) x=tr[x].s[0];else{if(ans<=tr[x].vl) ans=tr[x].vl,pos=x;x=tr[x].s[1];}return pos;
}
int nxt(int x,int k){int ans=inf,pos=2;while(x)if(k>=tr[x].vl) x=tr[x].s[1];else{if(ans>=tr[x].vl) ans=tr[x].vl,pos=x;x=tr[x].s[0];}return pos;
}
void del(int &rt,int x,int k){if(tr[x].vl==k){if(tr[x].cnt>1) --tr[x].cnt;else{int pv=pre(rt,k),nt=nxt(rt,k);spl(rt,pv,0),spl(rt,nt,pv);tr[nt].s[0]=0;psu(nt),psu(pv);}}else del(rt,tr[x].s[tr[x].vl<k],k);psu(x);
}
int pre(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr) return tr[pre(rt[x],k)].vl;int mid=(l+r)>>1,ans=-inf;if(ql<=mid) ans=max(ans,pre(x*2,l,mid,ql,qr,k));if(qr>mid) ans=max(ans,pre(x*2+1,mid+1,r,ql,qr,k));return ans;
}
int nxt(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr) return tr[nxt(rt[x],k)].vl;int mid=(l+r)>>1,ans=inf;if(ql<=mid) ans=min(ans,nxt(x*2,l,mid,ql,qr,k));if(qr>mid) ans=min(ans,nxt(x*2+1,mid+1,r,ql,qr,k));return ans;
}
int rnk(int x,int k){if(!x) return 0;if(k<=tr[x].vl) return rnk(tr[x].s[0],k);return tr[tr[x].s[0]].sz+tr[x].cnt+rnk(tr[x].s[1],k);
}
int rnk(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr) return rnk(rt[x],k)-1;int mid=(l+r)>>1,ans=0;if(ql<=mid) ans+=rnk(x*2,l,mid,ql,qr,k);if(qr>mid) ans+=rnk(x*2+1,mid+1,r,ql,qr,k);return ans;
}
void upt(int x,int l,int r,int pos,int k){if(l<=pos&&pos<=r) del(rt[x],rt[x],a[pos]),ins(rt[x],k);if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) upt(x*2,l,mid,pos,k);else upt(x*2+1,mid+1,r,pos,k);
}
void bld(int x,int l,int r){ins(rt[x],-inf),rt[x]=tot,ins(rt[x],inf);for(int i=l;i<=r;++i) ins(rt[x],a[i]);if(l==r) return;int mid=(l+r)>>1;bld(x*2,l,mid),bld(x*2+1,mid+1,r);
}
int kth(int ql,int qr,int k){  //要二分int l=0,r=1e8;while(l<r){int mid=(l+r+1)>>1;if(rnk(1,1,n,ql,qr,mid)+1>k) r=mid-1;else l=mid;}return l;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;++i) cin>>a[i];bld(1,1,n);tr[1].vl=-inf,tr[2].vl=inf;while(m--){cin>>op>>x>>y;if(op!=3) cin>>k;if(op==1) cout<<rnk(1,1,n,x,y,k)+1<<endl;else if(op==2) cout<<kth(x,y,k)<<endl;else if(op==3) upt(1,1,n,x,y),a[x]=y;else if(op==4) cout<<pre(1,1,n,x,y,k)<<endl;else cout<<nxt(1,1,n,x,y,k)<<endl;}return 0;
}

P3804 【模板】后缀自动机（SAM）

反转了，要开 longlong

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
struct SAM{int len,link;int nxt[27];
}suf[N];
int siz,last;
ll ans,cnt[N];
void add(char c){int cur=++siz; cnt[cur]=1;suf[cur].len=suf[last].len+1;int p=last; last=cur;while(~p&&!suf[p].nxt[c]) suf[p].nxt[c]=cur,p=suf[p].link;if(p==-1) return suf[cur].link=0,void();int q=suf[p].nxt[c];if(suf[q].len==suf[p].len+1) suf[cur].link=q;else{int clone=++siz;suf[clone]=suf[q];suf[clone].len=suf[p].len+1;while(~p&&suf[p].nxt[c]==q) suf[p].nxt[c]=clone,p=suf[p].link;suf[q].link=suf[cur].link=clone;}
}
int head[N],nxt[N],edge[N],idx;
void addE(int u,int v){edge[++idx]=v;nxt[idx]=head[u];head[u]=idx;
}
void dfs(int u){for(int i=head[u];i;i=nxt[i]){int v=edge[i];dfs(v);cnt[u]+=cnt[v];}if(cnt[u]!=1) ans=max(ans,cnt[u]*suf[u].len);
}
signed main(){string s;cin>>s;suf[0].link=-1;for(int i=0;i<s.size();i++) add(s[i]-'a');for(int i=1;i<=siz;i++) addE(suf[i].link,i);dfs(0);cout<<ans;return 0;
}

P3803 【模板】多项式乘法（FFT）

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=5e6+10,inf=0x3f3f3f3f,mod=1e9+7;
const double pi=4*atan(-1.0);
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,len=1,tot;
complex<double> a[N],b[N]; 
void fft(complex<double> *cmx,int len,int k){if(len==1) return;complex<double> e[len/2],o[len/2];for(int i=0;i<len;i+=2)e[i/2]=cmx[i],o[i/2]=cmx[i+1];fft(e,len/2,k),fft(o,len/2,k);complex<double> omegan(cos(2*pi/(len*1.0)),k*sin(2*pi/(len*1.0))),omegak(1,0);for(int i=0;i<len/2;i++,omegak*=omegan){cmx[i]=e[i]+o[i]*omegak;cmx[i+len/2]=e[i]-o[i]*omegak;}
}
signed main(){cin>>n>>m;for(int i=0;i<=n;i++) cin>>tot,a[i].real(tot);for(int i=0;i<=m;i++) cin>>tot,b[i].real(tot);while(len<n+m+1) len*=2;fft(a,len,1),fft(b,len,1);for(int i=0;i<len;i++) a[i]*=b[i];fft(a,len,-1);for(int i=0;i<=n+m;i++) printf("%.0f ",(a[i].real()+0.5)/len);return 0;
}

P1919 【模板】高精度乘法 | A*B Problem 升级版

简单 ntt

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=5e6+10,inf=0x3f3f3f3f,p=998244353,g=3,gi=332748118;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,len=1,tot,l,r[N];
int a[N],b[N]; 
int quickMi(int a,int b){int ans=1,bit=a;while(b>0){if(b&1) ans=(ans*bit)%p;bit=(bit*bit)%p;b>>=1;}return ans%p;
}
void ntt(int *cmx,int len,int k){for(int i=0;i<len;i++)if(i<r[i]) swap(cmx[i],cmx[r[i]]);for(int mid=1;mid<len;mid<<=1){int omegan=quickMi((k==1?g:gi),(p-1)/(mid<<1));for(int t=mid<<1,i=0;i<len;i+=t){int omegak=1;for(int k=0;k<mid;k++,omegak=(omegak*omegan)%p){int x=cmx[i+k],y=(omegak*cmx[i+k+mid])%p;cmx[i+k]=(x+y)%p;cmx[i+k+mid]=(x-y+p)%p;}}}
}
int ans[N];
string s1,s2;
signed main(){cin>>s1>>s2; n=s1.size()-1,m=s2.size()-1;for(int i=0;i<=n;i++) a[i]=(s1[n-i]-'0');for(int i=0;i<=m;i++) b[i]=(s2[m-i]-'0');while(len<n+m+1) len*=2,l++;for(int i=0;i<len;i++) r[i]=(r[i>>1ll]>>1ll)|((i&1ll)<<(l-1ll));ntt(a,len,1),ntt(b,len,1);for(int i=0;i<len;i++) a[i]*=b[i];ntt(a,len,-1);int inv=quickMi(len,p-2);;for(int i=0;i<=len;i++) ans[i]=(a[i]*inv)%p;for(int i=0;i<=len;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;while(ans[len]==0&&len) len--;while(~len) cout<<ans[len--];return 0;
}

P4238 【模板】多项式乘法逆

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,p=998244353,g=3,gi=332748118;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,len=1,tot,l,r[N];
int a[N],b[N]; 
int quickMi(int a,int b){int ans=1,bit=a;while(b>0){if(b&1) ans=(ans*bit)%p;bit=(bit*bit)%p;b>>=1;}return ans%p;
}
void ntt(int *cmx,int len,int k){for(int i=0;i<len;i++)if(i<r[i]) swap(cmx[i],cmx[r[i]]);for(int mid=1;mid<len;mid<<=1){int omegan=quickMi((k==1?g:gi),(p-1)/(mid<<1));for(int t=mid<<1,i=0;i<len;i+=t){int omegak=1;for(int k=0;k<mid;k++,omegak=(omegak*omegan)%p){int x=cmx[i+k],y=(omegak*cmx[i+k+mid])%p;cmx[i+k]=(x+y)%p;cmx[i+k+mid]=(x-y+p)%p;}}}
}
int ans[N];
char s1[N],s2[N];
void work(int *f,int *g,int n){if(n==1){g[0]=quickMi(f[0],p-2);return;}work(f,g,((n+1)>>1));int len=1,l=0;while(len<(n<<1)) len<<=1,l++;for(int i=0;i<n;i++) ans[i]=f[i];for(int i=n;i<len;i++) ans[i]=0;for(int i=1;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));ntt(ans,len,1),ntt(g,len,1);for(int i=0;i<len;i++) g[i]=(g[i]*((2ll-ans[i]*g[i])%p+p)%p)%p;ntt(g,len,-1);int inv=quickMi(len,p-2);for(int i=0;i<len;i++) g[i]=(g[i]*inv)%p;for(int i=n;i<len;i++) g[i]=0;
}
signed main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i],a[i]=(a[i]+p)%p;work(a,b,n);for(int i=0;i<n;i++)cout<<b[i]<<" ";return 0;
}

P3402 可持久化并查集

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
struct node{int l,r,c,dep;
}f[N*20];
int tot,n,m,opt,k,u,v,rt[N];
int init(int l,int r){int mid=(l+r)>>1,pos=++tot;if(l==r){f[pos].c=l;return pos;}f[pos].l=init(l,mid),f[pos].r=init(mid+1,r);return pos;
}
int find_k(int l,int r,int k,int pos){    //f[k]if(l==r) return pos;int mid=(l+r)>>1;if(k>mid) return find_k(mid+1,r,k,f[pos].r);else return find_k(l,mid,k,f[pos].l);
}
int change(int l,int r,int k,int p,int x){   //f[k]=xint mid=(l+r)>>1,pos=++tot;f[pos]=f[p];if(l==r){f[pos].c=x;return pos;}if(k>mid) f[pos].r=change(mid+1,r,k,f[p].r,x);else f[pos].l=change(l,mid,k,f[p].l,x);return pos;
}
int newl(int l,int r,int p,int x){int mid=(l+r)>>1,pos=++tot; f[pos]=f[p];if(l==r){f[pos].dep++;return pos;}if(x>mid) f[pos].r=newl(mid+1,r,f[p].r,x);else f[pos].l=newl(l,mid,f[p].l,x);return pos;
}
int find(int x,int c){int fa=find_k(1,n,x,rt[c]);if(f[fa].c==x) return fa;return find(f[fa].c,c);
}
int main(){cin>>n>>m;rt[0]=init(1,n);for(int i=1;i<=m;i++){rt[i]=rt[i-1];scanf("%d%d",&opt,&u);if(opt==1){scanf("%d",&v);u=find(u,i-1),v=find(v,i-1);if(f[u].c==f[v].c) continue;//f[find(u)]=find(v)if(f[u].dep>f[v].dep) swap(u,v);rt[i]=change(1,n,f[u].c,rt[i],f[v].c);if(f[u].dep==f[v].dep) rt[i]=newl(1,n,rt[i],f[v].c);}else if(opt==2) rt[i]=rt[u];else{scanf("%d",&v);cout<<(find(u,i)==find(v,i))<<"\n";}}return 0;
}

P6178 【模板】Matrix-Tree 定理

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=8e2+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int qm(int a,int b){int res=1;while(b){if(b&1) res=(res*a)%mod;a=a*a%mod,b>>=1;} return res;
}
const double eps=1e-7;
struct Mat{int n,m,ck=0,mx[N][N];void chk(int lx,int rx,int ly,int ry){for(int i=lx;i<=rx;i++){for(int j=ly;j<=ry;j++)cout<<(mx[i][j]+mod)%mod<<" ";cout<<"\n";}cout<<"\n";}void gk(int i,int k) {for(int x=1;x<=m;x++) mx[i][x]=mx[i][x]*qm(k,mod-2)%mod;} void sw(int i,int j) {if(i==j) return;for(int x=1;x<=m;x++) swap(mx[i][x],mx[j][x]);}void ad(int i,int j,int k) {if(!i||!j||i==j) return;for(int x=1;x<=m;x++) mx[j][x]=((mx[j][x]+k*mx[i][x])%mod+mod)%mod;}void gs(){int l=1;for(int i=1;i<=m&&l<=n;i++){int ans=0;for(int j=l;j<=n;j++) if(mx[j][i]) {ans=j;break;}if(!ans) continue; sw(l,ans);for(int j=1;j<=n;j++) ad(l,j,-mx[j][i]*qm(mx[l][i],mod-2)%mod);++l;}}int det(){int res=1; gs();for(int i=1;i<=n;i++) res=res*mx[i][i]%mod;return res;} 
}M,T;
int n,m,t;
void add(int u,int v,int w){M.mx[v][v]=(M.mx[v][v]+w)%mod;M.mx[v][u]=(M.mx[v][u]-w)%mod;
}
signed main(){cin>>n>>m>>t; --n; M.n=M.m=n;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(--u,--v,w);if(!t) add(v,u,w);}cout<<M.det();return 0;
}

P4725 【模板】多项式对数函数（多项式 ln）

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e6+10,inf=0x3f3f3f3f,p=998244353,g=3,gi=332748118;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/**/
int n,m,len=1,tot,l,r[N];
int a[N],b[N],c[N]; 
int quickMi(int a,int b){int ans=1,bit=a;while(b>0){if(b&1) ans=(ans*bit)%p;bit=(bit*bit)%p;b>>=1;}return ans%p;
}
void ntt(int *cmx,int len,int k){for(int i=0;i<len;i++)if(i<r[i]) swap(cmx[i],cmx[r[i]]);for(int mid=1;mid<len;mid<<=1){int omegan=quickMi((k==1?g:gi),(p-1)/(mid<<1));for(int t=mid<<1,i=0;i<len;i+=t){int omegak=1;for(int k=0;k<mid;k++,omegak=(omegak*omegan)%p){int x=cmx[i+k],y=(omegak*cmx[i+k+mid])%p;cmx[i+k]=(x+y)%p;cmx[i+k+mid]=(x-y+p)%p;}}}
}
int ans[N];
char s1[N],s2[N];
void ginv(int *f,int *g,int n){if(n==1){g[0]=quickMi(f[0],p-2);return;}ginv(f,g,((n+1)>>1));int len=1,l=0;while(len<(n<<1)) len<<=1,l++;for(int i=0;i<n;i++) ans[i]=f[i];for(int i=n;i<len;i++) ans[i]=0;for(int i=1;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));ntt(ans,len,1),ntt(g,len,1);for(int i=0;i<len;i++) g[i]=(g[i]*((2ll-ans[i]*g[i])%p+p)%p)%p;ntt(g,len,-1);int inv=quickMi(len,p-2);for(int i=0;i<len;i++) g[i]=(g[i]*inv)%p;for(int i=n;i<len;i++) g[i]=0;
}
void mul(int *a,int *b,int *c,int n,int m,int &len){while(len<n+m+1) len*=2,l++;for(int i=0;i<len;i++) r[i]=(r[i>>1ll]>>1ll)|((i&1ll)<<(l-1ll));ntt(a,len,1),ntt(b,len,1);for(int i=0;i<len;i++) a[i]=(a[i]*b[i])%p;ntt(a,len,-1);int inv=quickMi(len,p-2); len=n+m;for(int i=0;i<=len;i++) c[i]=(a[i]*inv)%p;
}
signed main(){cin>>n; n--;for(int i=0;i<=n;i++) cin>>a[i],a[i]=(a[i]+p)%p; ginv(a,b,n); for(int i=0;i<=n;i++) a[i]=a[i+1]*(i+1)%p;mul(a,b,c,n-1,n,len); ++len;for(int i=n;i;i--) c[i]=c[i-1]*quickMi(i,p-2)%p; c[0]=0;for(int i=0;i<=n;i++) cout<<c[i]<<" ";return 0;
}