交换两个 vector：a.swap(b)

判断数 $x$ 是否在 map 中出现过：mp.count(x)

多测要换行，开龙龙常数加LL

开大栈空间 -Wl,--stack=268435456

文本比对

#include<iostream>
system("fc 文件名1 文件名2");

__int128

#include<cstdio>
inline __int128 read(){
	__int128 s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void write(__int128 x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

快速幂模板

int pows(int a,int b){
	int s=1,p=a;
  	while(b){
  		if(b&1)s=s*p;
    	p*=p;
		b>>=1;
 	}
  	return s;
}

lucas模板（求模素数 p 意义下的组合数）

int lucas(int x,int y,int p){
    if(!y)return 1;
    return C(x%p,y%p,p)*lucas(x/p,y/p,p)%p;
}

排列组合公式法模板

void init(){
	int i;
	fac[0]=1;
	for(i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
	inv[100000]=pows(fac[100000],mod-2);
	for(i=100000;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
int C(int n,int m){
	if(m>n||m<0)return 0;
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

排列组合杨辉三角法模板

c[0][0]=1;
for(i=1;i<=k;i++){
    c[i][0]=1;
    for(j=1;j<=i;j++){
        c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
}

排列组合朴素法模板

int C(int a,int b){
	int i,j=1,s=1;
	for(i=a;i>=a-b+1;i--){
		s*=i;
		s/=j;
		j++;
	}
	return s;
}

st表(gcd,min,max)

int query(int l,int r){
	int lglr=lg2[r-l+1];
	return gcd(f[l][lglr],f[r-(1<<lglr)+1][lglr]);
}
for(j=1;j<=logx[n];j++){
	for(i=1;i+(1<<j)-1<=n;i++){
		f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
}
for(i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;

gcd

int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}

树状数组

int lowbit(int x){
	return x&(-x);
}
void add(int i,int x){
	while(i<=n){
		c[i]+=x;//求和
      //c[i]=max(c[i],x);//求最大值
		i+=lowbit(i);
	} 
}
int query(int i){
	int s=0,maxn=0;
	while(i>0){
		s+=c[i];//求和
      //maxn=max(maxn,c[i]);//求最大值
		i-=lowbit(i);
	}
	return s;
}

lca

void dfs(int u){
	int i;
	for(i=1;i<=15;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa[u][0])continue;
		fa[v][0]=u;
		d[v]=d[u]+1;
		dfs(v);
	}
}
int up(int v,int d){
	int i;
	for(i=0;i<=15;i++){
		if(d&(1<<i)){
			v=fa[v][i];
		}
	}
	return v;
}
int lca(int u,int v){
	int i;
	if(d[u]>d[v])swap(u,v);
	int h=d[v]-d[u];
	v=up(v,h);
	if(v==u)return u;
	for(i=15;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}

最小生成树

int finds(int x){
	if(fa[x]==x)return x;
	return fa[x]=finds(fa[x]);
}
sort(a+1,a+m+1);
for(i=1;i<=m;i++){
	int u=finds(a[i].u);
	int v=finds(a[i].v);
	if(u!=v){
		fa[u]=v;
		ans+=a[i].w;
		num++;
	}
}

树链剖分

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,q,cnt;
int w[30005],son[30005],siz[30005],dep[30005],fa[30005];
//son 重儿子，siz 子树大小，dep 深度，fa 父节点 
int dfn[30005],top[30005],rnk[30005];
//dfn 遍历后新序号，top 链顶，rnk 新序号对应的原序号 
string s;
vector<int> g[30005];
struct tree{
	int maxn,sum;
}tr[120005];
void dfs1(int u,int f){//找重边 
	int i;
	son[u]=-1;
	siz[u]=1;
	for(i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==f)continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int tp){//找重链 
	int i;
	top[u]=tp;
	dfn[u]=++cnt;
	rnk[cnt]=u;
	if(son[u]==-1)return;//叶子节点 
	dfs2(son[u],tp);//优先重儿子，保证重链 dfs 序连续 
	for(i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==son[u]||v==fa[u])continue;//不能是重儿子和父节点 
		dfs2(v,v);
	}
}
void build(int root,int l,int r){
	if(l==r){
		tr[root].maxn=tr[root].sum=w[rnk[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	tr[root].maxn=max(tr[root*2].maxn,tr[root*2+1].maxn);
	tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}
void update(int root,int l,int r,int x,int y){
	if(l==r){
		tr[root].maxn=tr[root].sum=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		update(root*2,l,mid,x,y);
	}else{
		update(root*2+1,mid+1,r,x,y);
	}
	tr[root].maxn=max(tr[root*2].maxn,tr[root*2+1].maxn);
	tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}
int querymax(int root,int l,int r,int x,int y){
	if(x>r||y<l)return -1e9;
	if(x<=l&&r<=y)return tr[root].maxn;
	int mid=(l+r)>>1;
	return max(querymax(root*2,l,mid,x,y),querymax(root*2+1,mid+1,r,x,y));
}
int querysum(int root,int l,int r,int x,int y){
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return tr[root].sum;
	int mid=(l+r)>>1;
	return querysum(root*2,l,mid,x,y)+querysum(root*2+1,mid+1,r,x,y);
}
int qmax(int u,int v){
	int res=-1e9;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		res=max(res,querymax(1,1,n,dfn[top[u]],dfn[u]));//查询跳上去这段 
		u=fa[top[u]];//跳 
	}
	if(dep[u]>dep[v])swap(u,v);
	res=max(res,querymax(1,1,n,dfn[u],dfn[v]));
	
	return res;
}
int qsum(int u,int v){
	int res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		res+=querysum(1,1,n,dfn[top[u]],dfn[u]);//查询跳上去这段 
		u=fa[top[u]];//跳 
	}
	if(dep[u]>dep[v])swap(u,v);
	res+=querysum(1,1,n,dfn[u],dfn[v]);
	return res;
}
int main(){
	int i,u,v;
	cin>>n;
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(i=1;i<=n;i++)scanf("%d",&w[i]);
	dfs1(1,-1);
	dfs2(1,1);
	build(1,1,n);
	cin>>q;
	while(q--){
		cin>>s;
		scanf("%d%d",&u,&v);
		if(s=="CHANGE")update(1,1,n,dfn[u],v);
		if(s=="QMAX")printf("%d\n",qmax(u,v));
		if(s=="QSUM")printf("%d\n",qsum(u,v));
	}
}

组合数的各种算法

线段树详解

$\forall a_i, i∈[l,r],a_i+=d：$使用权值线段树

$\forall a_i, i∈[l,r],a_i=d：$使用珂朵莉树

$\forall a_i, i∈[l,r],a_i=max(a_i,d)：$使用吉司机线段树

做题小trick：

数量相同（中位数）$→$ 变 $+1,-1$ 维护前缀和

$+1,-1$ 数量相同且每个前缀 $≥0→$ 括号序列

很小字符个数+有规律合并 $→$ 字符转数字找规律（$maybe$ 取模）