模板库

缺省源

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#include<assert.h>
#define _INT_INF ((int)0x3f3f3f3f)
#define _UINT_MAX ((unsigned int)0xffffffff)
#define _INT_MAX ((int)0x7fffffff)
#define _LL_INF ((long long)0x3f3f3f3f3f3f3f3f)
#define _ULL_MAX ((unsigned long long)0xffffffffffffffff)
#define _LL_MAX ((long long)0x7fffffffffffffff)
namespace FastIO{
	#define BUF_SIZE 33554432
	char buff[BUF_SIZE];char *p1=buff,*p2=buff;
	#define getChar (p1==p2&&(p2=(p1=buff)+fread(buff,1,BUF_SIZE,stdin),p1==p2)?EOF:*p1++)
	__attribute__((always_inline))inline int read(){
		register int x=0;register char c=getChar;
		while(c<'0'||c>'9')	c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	__attribute__((always_inline))inline int reads(){
		register int x=0,y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	__attribute__((always_inline))inline long long readl(){
		register long long x=0;register char c=getChar;
		while(c<'0'||c>'9') c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	__attribute__((always_inline))inline int readsl(){
		register long long x=0;register int y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	__attribute__((always_inline))inline void read(char *s){
		register char c=getChar;while(c=='
'||c=='
'||c==' '||c=='	') c=getChar;
        while(c!='
'&&c!='
'&&c!=' '&&c!='	'&&c!=EOF) *s=c,s++,c=getChar;*s=0;
	}
	#undef getChar
	#define EN write('
')
	#define SPACE write(' ')
	char buffW[BUF_SIZE];int bb;
	char stack[28];
	__attribute__((always_inline))inline void write(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];
	}
	__attribute__((always_inline))inline void writeEN(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]='
',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]='
';
	}
	__attribute__((always_inline))inline void writeSP(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]=' ',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]=' ';
	}
	__attribute__((always_inline))inline void write(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];
	}
	__attribute__((always_inline))inline void writeEN(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]='
',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]='
';
	}
	__attribute__((always_inline))inline void writeSP(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]=' ',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]=' ';
	}
	__attribute__((always_inline))inline void write(register char c){buffW[bb++]=c;}
	__attribute__((always_inline))inline void write(const char *c){while(*c) buffW[bb++]=*c,c++;}
	#define SUC_RETURN fwrite(buffW,1,bb,stdout),0
	#undef BUF_SIZE
}//namespace FastIO
using namespace FastIO;
namespace lib{
	__attribute__((always_inline))inline void chkMin(int &a,const int &b){(a>b)&&(a=b);}
	__attribute__((always_inline))inline void chkMin(long long &a,const long long &b){(a>b)&&(a=b);}
	__attribute__((always_inline))inline void chkMax(int &a,const int &b){(a<b)&&(a=b);}
	__attribute__((always_inline))inline void chkMax(long long &a,const long long &b){(a<b)&&(a=b);}
	__attribute__((always_inline))inline int min(const int &a,const int &b){return a>b?b:a;}
	__attribute__((always_inline))inline long long min(const long long &a,const long long &b){return a>b?b:a;}
	__attribute__((always_inline))inline int max(const int &a,const int &b){return a>b?a:b;}
	__attribute__((always_inline))inline long long max(const long long &a,const long long &b){return a>b?a:b;}
	__attribute__((always_inline))inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
	__attribute__((always_inline))inline void swap(long long &a,long long &b){a^=b;b^=a;a^=b;}
	__attribute__((always_inline))inline int abs(const int &a){return a>0?a:-a;}
	__attribute__((always_inline))inline long long abs(const long long &a){return a>0?a:-a;}
}
int main(){
	return SUC_RETURN;
}

图论

邻接表

struct Graph{
	int fir[N],nex[M],to[M],tot;
	inline void add(int u,int v,int flag=1){
		to[++tot]=v;
		nex[tot]=fir[u];fir[u]=tot;
		if(flag) add(v,u,0);
	}
	inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;

dij 最短路

inline void dij(int u,int *dis,const Graph &G=::G){
	std::memset(dis,0x3f,(n+1)*sizeof dis[0]);dis[u]=0;
	static std::priority_queue<std::pair<int,int> >que;
	que.push(std::make_pair(0,u));
	while(!que.empty()){
		u=que.top().second;
		if(que.top().first^(-dis[u])){que.pop();continue;}
		que.pop();
		for(int v,i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(dis[v]<=dis[u]+G.w[i]) continue;
			dis[v]=dis[u]+G.w[i];que.push(std::make_pair(-dis[v],v));
		}
	}
}

tarjan 缩强连通分量

int dfn[N],low[N],dfscnt;
int stack[N],top;
int scc[N],scccnt;
void tarjan(int u){
	dfn[u]=low[u]=++dfscnt;
	stack[top++]=u;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
		}
		else if(!scc[v]) low[u]=std::min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scccnt++;
		do{
			scc[stack[--top]]=scccnt;
		}while(stack[top]^u);
	}
}

tarjan 求割点

int dfn[N],low[N],dfscnt;
int cut[N];
void tarjan(int u,int root){
	dfn[u]=low[u]=++dfscnt;
	int cnt=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(!dfn[v]){
			tarjan(v,root);
			low[u]=std::min(low[v],low[u]);
			if(low[v]>=dfn[u]&&u!=root) cut[u]=1;
			cnt++;
		}
		low[u]=std::min(low[u],dfn[v]);
	}
	if(cnt>1&&u==root) cut[u]=1;
}

tarjan 求桥

void tarjan(int u){
	dfn[u]=low[u]=++dfscnt;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(!dfn[v]){
			fa[v]=u;tarjan(v);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>dfn[u]) bridge[v]=1,ans++;
		}
		else if(v!=fa[u]) low[u]=std::min(low[u],dfn[v]);
	}
}

dinic

int n,m,S,T;
int deep[N];
int left,right,que[N];
inline int bfs(){
	std::memset(deep,0,(n+1)*sizeof deep[0]);
	left=right=0;
	que[0]=S;deep[S]=1;
	int u;
	while(left<=right){
		u=que[left++];
		for(int v,i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(deep[v]||!G.w[i]) continue;
			deep[v]=deep[u]+1;que[++right]=v;
			if(v==T) return 1;
		}
	}
	return 0;
}
long long dfs(int u,long long now=1e18){
	if(u==T) return now;
	long long res=now;
	for(int v,&i=G.fir_[u];i;i=G.nex[i]){
		v=G.to[i];
		if(deep[v]!=deep[u]+1||!G.w[i]) continue;
		long long k=dfs(v,std::min(res,G.w[i]));
		if(!k) deep[v]=0;
		else G.w[i]-=k,G.w[i^1]+=k,res-=k;
		if(!res) break;
	}
	return now-res;
}
inline long long dinic(){
	long long ans=0;
	while(bfs()){
		long long now;
		std::memcpy(G.fir_,G.fir,(n+1)*sizeof G.fir[0]);
		while(now=dfs(S)) ans+=now;
	}
	return ans;
}

最小费用最大流

int n,m,S,T;
long long dis[N],h[N];
int pre_edge[N],pre_node[N];
std::priority_queue<std::pair<long long,int> >pque;
inline void dij(){
	std::memset(dis,0x3f,sizeof dis);dis[S]=0;
	while(!pque.empty()) pque.pop();
	pque.push(std::make_pair(0,S));
	int u,i,v;
	while(!pque.empty()){
		u=pque.top().second;
		if(dis[u]!=-pque.top().first){pque.pop();continue;}
		pque.pop();
		if(u==T) break;
		for(i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			long long len=G.c[i]+h[u]-h[v];
			if(!G.w[i]||dis[v]<=dis[u]+len) continue;
			dis[v]=dis[u]+len;
			preNode[v]=u;preEdge[v]=i;
			pque.push(std::make_pair(-dis[v],v));
		}
	}
}
int in[N],left,right,que[N*20];
inline void spfa(){
	left=right=0;que[0]=S;
	std::memset(h,0x3f,sizeof h);
	h[S]=0;in[S]=1;
	int u,i,v;
	while(left<=right){
		u=que[left++];in[u]=0;
		for(i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(!G.w[i]||h[v]<=h[u]+G.c[i]) continue;
			h[v]=h[u]+G.c[i];
			if(!in[v]) que[++right]=v,in[v]=1;
		}
	}
}
long long maxflow,ans;
inline void work(int n){
	spfa();
	for(;;){
		dij();
		if(dis[T]==LL_INF) break;
		long long minflow=LL_INF;
		for(int i=T;i^S;i=pre_node[i]) minflow=std::min(minflow,G.w[pre_edge[i]]);
		for(int i=T;i^S;i=pre_node[i]) G.w[pre_edge[i]]-=minflow,G.w[pre_edge[i]^1]+=minflow;
		maxflow+=minflow;ans+=minflow*(dis[T]+h[T]);
		for(int i=1;i<=n;i++) h[i]=std::min(h[i]+dis[i],LL_INF);
	}
}

有源汇上下界最大流

long long d[N];
inline void add(int u,int v,long long l,long long r){
	G.add(u,v,r-l);
	d[u]-=l;d[v]+=l;
}
int main(){
	int s=n+1,t=s+1;
	S=t+1;T=S+1;
	long long sum=0;
	for(int i=1;i<=t;i++){
		if(d[i]>0) G.add(S,i,d[i]),sum+=d[i];
		else if(d[i]<0) G.add(i,T,-d[i]);
	}
	G.add(t,s,LL_INF);
	if(dinic()^sum) puts("-1
");
	else{
		for(int i=G.fir[S];i;i=G.nex[i]) G.w[i]=G.w[i^1]=0;
		for(int i=G.fir[T];i;i=G.nex[i]) G.w[i]=G.w[i^1]=0;
		sum=G.w[G.tot];G.w[G.tot]=G.w[G.tot-1]=0;
		S=s;T=t;
		printf("%lld

",sum+dinic());
	}
	return 0;
}

最小割树

Graph G,T; 
struct Flow{
	int S,T;
	int deep[N];
	int left,right,que[N];
	inline int bfs(){
		std::memset(deep,0,sizeof deep);
		left=right=0;
		que[0]=S;deep[S]=1;
		int u;
		while(left<=right){
			u=que[left++];
			for(int v,i=G.fir[u];i;i=G.nex[i]){
				v=G.to[i];
				if(deep[v]||!G.w[i]) continue;
				deep[v]=deep[u]+1;que[++right]=v;
				if(v==T) return 1;
			}
		}
		return 0;
	}
	int dfs(int u,int now=INT_INF){
		if(u==T) return now;
		int res=now;
		for(int v,&i=G.fir_[u];i;i=G.nex[i]){
			v=G.to[i];
			if(deep[v]!=deep[u]+1||!G.w[i]) continue;
			int k=dfs(v,std::min(res,G.w[i]));
			if(!k) deep[v]=0;
			else G.w[i]-=k,G.w[i^1]+=k,res-=k;
			if(!res) break;
		}
		return now-res;
	}
	inline void init(){
		for(int i=2;i<=G.tot;i+=2){
			G.w[i]+=G.w[i^1];
			G.w[i^1]=0;
		}
	}
	inline int dinic(int s,int t){
		init();S=s;T=t;
		int ans=0,now=0;
		while(bfs()){
			std::memcpy(G.fir_,G.fir,sizeof G.fir);
			while(now=dfs(s)) ans+=now;
		}
		return ans;
	}
}F;
int min[11][N],fa[11][N],deep[N];
int node[N],tmp1[N],tmp2[N];
void build(int l,int r){
	if(l==r) return;
	int s=node[l],t=node[l+1];
	int cut=F.dinic(s,t);
	T.add(s,t,cut);T.add(t,s,cut);
	int cnt1=0,cnt2=0;
	for(int i=l;i<=r;i++){
		if(F.deep[node[i]]) tmp1[++cnt1]=node[i];
		else tmp2[++cnt2]=node[i];
	}
	for(int i=l;i<l+cnt1;i++) node[i]=tmp1[i-l+1];
	for(int i=l+cnt1;i<=r;i++) node[i]=tmp2[i-cnt1-l+1];
	build(l,l+cnt1-1);build(l+cnt1,r);
}

HLPP 最大流

int S,T;
int left,right,que[N*100];
int in[N];
int h[N],cnth[N*2];
long long res[N];
inline void bfs(){
	std::memset(h,0x3f,sizeof h);h[T]=0;
	left=right=0;que[0]=T;in[T]=1;
	int u;
	while(left<=right){
		u=que[left++];in[u]=0;
		for(int v,i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(!G.w[i^1]||h[v]<=h[u]+1) continue;
			h[v]=h[u]+1;
			if(!in[v]) que[++right]=v,in[v]=1;
		}
	}
}
inline int pqueCmp(const int &a,const int &b){return h[a]<h[b];}
std::priority_queue<int,std::vector<int>,int(*)(const int &a,const int &b)>pque(pqueCmp);
inline void push(int u){
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(h[v]+1!=h[u]||!G.w[i]) continue;
		long long k=std::min(G.w[i],res[u]);
		G.w[i]-=k;G.w[i^1]+=k;
		res[u]-=k;res[v]+=k;
		if(!in[v]&&v!=T&&v!=S) in[v]=1,pque.push(v);
		if(!res[u]) break;
	}
}
inline void relabel(int u){
	h[u]=INT_INF;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(G.w[i]) h[u]=std::min(h[u],h[v]+1);
	}
}
inline long long hlpp(int s,int t){
	S=s;T=t;
	bfs();
	if(h[S]==INT_INF) return 0;
	h[S]=n;
	for(int i=1;i<=n;i++)if(h[i]<INT_INF) cnth[h[i]]++;
	for(int v,i=G.fir[S];i;i=G.nex[i]){
		v=G.to[i];
		if(G.w[i]&&h[v]<INT_INF){
			res[S]-=G.w[i];res[v]+=G.w[i];
			G.w[i^1]+=G.w[i];G.w[i]=0;
			if(!in[v]&&v!=T&&v!=S) pque.push(v),in[v]=1;
		}
	}
	int u;
	while(!pque.empty()){
		u=pque.top();pque.pop();in[u]=0;
		push(u);
		if(res[u]){
			if(!--cnth[h[u]]){
				for(int i=1;i<=n;i++)if(h[i]>h[u]&&i!=S&&i!=T) h[i]=n+1;
			}
			relabel(u);cnth[h[u]]++;
			pque.push(u);in[u]=1;
		}
	}
	return res[T];
}

Stoer-Wagner 求无向图最小割

int S,T;
int w[N],inA[N];
int del[N],dis[N][N];
inline int mincut(int x){
	std::memset(w,0,sizeof w);std::memset(inA,0,sizeof inA);
	w[0]=-1;
	for(int id,i=1;i<=n-x+1;i++){
		id=0;
		for(int j=1;j<=n;j++)if(!inA[j]&&!del[j]&&w[j]>w[id]) id=j;
		inA[id]=1;
		if(i==n-x) S=id;
		else if(i==n-x+1) T=id;
		for(int j=1;j<=n;j++)if(!inA[j]&&!del[j]) w[j]+=dis[id][j];
	}
	return w[T];
}
inline int sw(){
	int ret=1e9;
	for(int i=1;i<n;i++){
		ret=std::min(ret,mincut(i));
		del[T]=1;
		for(int j=1;j<=n;j++) dis[S][j]+=dis[T][j],dis[j][S]+=dis[j][T];
	}
	return ret;
}

tarjan 最小树形图

int uniFa[N];
inline int find(int k){return k==uniFa[k]?k:uniFa[k]=find(uniFa[k]);}
struct Edge{
	int u,v,w,w0;
};
struct Node{
	Node *ls,*rs,*root;
	int deep,tag;
	Edge *edge;
	inline void pushdown(){
		ls->tag+=tag;rs->tag+=tag;
		edge->w+=tag;
		tag=0;
	}
}nullNode,*null=&nullNode;
int tot;
inline void New(Node *&x,Edge *e){
	x=new Node;
	x->deep=1;x->tag=0;
	x->ls=x->rs=null;
	x->root=x;x->edge=e;
}
Node *merge(Node *x,Node *y){
	if(x==null) return y;
	if(y==null) return x;
	if(x->edge->w+x->tag>y->edge->w+y->tag) std::swap(x,y);
	x->pushdown();
	x->rs=merge(x->rs,y);
	if(x->ls->deep<x->rs->deep) std::swap(x->ls,x->rs);
	x->deep=x->rs->deep+1;
	x->ls->root=x->rs->root=x;
	return x;
}
inline void pop(Node *&x){
	x->pushdown();
	Node *ls=x->ls,*rs=x->rs;
	delete x;
	x=merge(ls,rs);
}
int n,m;
int vis[N],fa[N];
int nex[N];
Edge *in[M],edge[M];
Node *p[N];
inline void contraction(){
	for(int i=1;i<=n;i++) p[i]=null,uniFa[i]=i;
	for(int i=1;i<=m;i++){
		Node *tmp;
		New(tmp,&edge[i]);
		p[edge[i].v]=merge(p[edge[i].v],tmp);
	}
	vis[1]=1;
	for(int u=1,pre=1,o;p[u];pre=u,vis[u]=1){
		do{
			in[u]=p[u]->edge;pop(p[u]);
			u=find(in[u]->u);
		}while(u==pre&&p[u]!=null);
		if(u==pre) break;
		if(!vis[u]) continue;
		p[++n]=null;uniFa[n]=n;
		for(pre=u;u^n;){
			uniFa[u]=fa[u]=n;
			if(p[u]!=null) p[u]->tag-=in[u]->w;
			p[n]=merge(p[n],p[u]);
			o=find(in[u]->u);
			nex[o==n?pre:o]=u;
			u=o;
		}
	}
}
int expand(int,int);
int expand(int u){
	int ans=0;
	for(int x=nex[u];x^u;x=nex[x]){
		if(in[x]->w0==INT_INF) return INT_INF;
		if((ans+=in[x]->w0+expand(in[x]->v,x))>=INT_INF) return INT_INF;
	}
	return ans;
}
inline int expand(int u,int goal){
	int ans=0;
	for(;u^goal;u=fa[u])
		if((ans+=expand(u))>=INT_INF) return INT_INF;
	return ans;
}
int main(){
	n=read();m=read();int root=read();
	for(int i=1;i<=m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].w=edge[i].w0=read();
	for(int i=1;i<n;i++) edge[++m]={i,i+1,INT_INF,INT_INF};
	edge[++m]={n,1,INT_INF,INT_INF};
	contraction();
	int ans=expand(root,n);
	printf("%d
",ans==INT_INF?-1:ans);
	return 0;
}

spfa 找负环

int dis[N],cnt[N];
int left,right,que[N];
inline int spfa(){
	std::memset(dis,0x3f,sizeof dis);std::memset(cnt,0,sizeof cnt);
	right=left=0;que[0]=1;
	dis[1]=0;
	int u,v,i;
	while(left<=right){
		u=que[left++];
		for(i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(dis[v]>dis[u]+G.w[i]){
				dis[v]=dis[u]+G.w[i];
				cnt[v]++;
				if(cnt[v]>n) return 1;
				que[++right]=v;
			}
		}
	}
	return 0;
}

支配树

Graph G,H,T;
int uni[N],min[N];
int dfscnt,dfn[N],id[N],fa[N];
int sdom[N],idom[N];
inline int find(int k){
	if(k==uni[k]) return k;
	int ret=find(uni[k]);
	if(dfn[sdom[min[uni[k]]]]<dfn[sdom[min[k]]]) min[k]=min[uni[k]];
	return uni[k]=ret;
}
void dfs(int u){
	dfn[u]=++dfscnt;id[dfscnt]=u;
	for(int i=G.fir[u];i;i=G.nex[i])
		if(!dfn[G.to[i]]) fa[G.to[i]]=u,dfs(G.to[i]);
}
inline void work(int s){
	dfs(s);
	for(int i=1;i<=n;i++) sdom[i]=uni[i]=min[i]=i;
	for(int u,i=dfscnt;i>1;i--){
		u=id[i];
		for(int v,i=H.fir[u];i;i=H.nex[i]){
			v=H.to[i];
			if(!dfn[v]) continue;
			find(v);
			if(dfn[sdom[min[v]]]<dfn[sdom[u]]) sdom[u]=sdom[min[v]];
		}
		uni[u]=fa[u];
		T.add(sdom[u],u);u=fa[u];
		for(int v,i=T.fir[u];i;i=T.nex[i]){
			v=T.to[i];
			find(v);idom[v]=(u==sdom[min[v]])?u:min[v];
		}
		T.fir[u]=0;
	}
	for(int u,i=2;i<=dfscnt;i++){
		u=id[i];
		if(idom[u]^sdom[u]) idom[u]=idom[idom[u]];
	}
}
int ans[N];
inline void get_ans(){
	for(int i=dfscnt;i>1;i--) ans[idom[id[i]]]+=++ans[id[i]];
	ans[id[1]]++;
}

LGV 引理

https://oi-wiki.org//graph/lgv/

匈牙利

int match[N],vis[N];
int dfs(int u){
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(vis[v]) continue;
		vis[v]=1;
		if(!match[v]||dfs(match[v])) return match[v]=u,match[u]=v,1;
	}
	return 0;
}

二分图最大权匹配 KM

int num_left,num_right;
int G[N][N];
int vis[N],pre[N],match[N],lw[N],d[N];
int que[N],tail,head;
inline int bfs(int u){
    tail=head=0;que[0]=u;
    pre[u]=0;
    while(tail<=head){
        u=que[tail++];vis[u]=1;
        for(int i=num_left+1;i<=num_right;i++)if(G[u][i]==lw[u]+lw[i]){
            if(vis[i]) continue;
            vis[i]=1;
            if(match[i]) pre[match[i]]=u,que[++head]=match[i];
            else{
                int d=u,e=i,t;
                while(d){
                    t=match[d];
                    match[d]=e;match[e]=d;
                    d=pre[d];e=t; 
                }
                return 1;
            }
        }
    }
    return 0;
}
inline LL max_match(){
    for(int i=1;i<=num_left;i++){
        for(int j=num_left+1;j<=num_right;j++) lw[i]=std::max(lw[i],G[i][j]);
    }
    for(int i=1;i<=num_left;i++){
        std::memset(vis,0,sizeof vis);std::memset(d,0x3f,sizeof d);
        if(bfs(i)) continue;
        for(int j=1;j<=num_left;j++)if(vis[j])
            for(int k=num_left+1;k<=num_right;k++)
                if(!vis[k]) d[k]=std::min(d[k],lw[j]+lw[k]-G[j][k]);
        while(1){
            int now=INT_INF,to,s;
            for(int j=num_left+1;j<=num_right;j++)if(!vis[j]) now=std::min(now,d[j]);
            for(int j=1;j<=num_left;j++)if(vis[j]) lw[j]-=now;
            for(int j=num_left+1;j<=num_right;j++)
                if(vis[j]) lw[j]+=now;
                else d[j]-=now,to=d[j]?to:j;
            if(!match[to]) break;
            s=match[to];vis[to]=vis[s]=1;//打上 vis 标记
            for(int j=num_left+1;j<=num_right;j++)if(!vis[j]) d[j]=std::min(d[j],lw[s]+lw[j]-G[s][j]);
        }
        std::memset(vis,0,sizeof vis);
        bfs(i);
    }
    long long ans=0;
    for(int i=1;i<=num_right;i++) ans+=lw[i];
    return ans; 
}

树的最小表示法

struct Center{int a,b;};
int size[N],maxson[N];
void getMaxs(int u,int fa,int n,const Graph &G){
	size[u]=1;maxson[u]=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa) continue;
		getMaxs(v,u,n,G);
		size[u]+=size[v];maxson[u]=std::max(maxson[u],size[v]);
	}
	maxson[u]=std::max(maxson[u],n-size[u]);
}
inline Center getCenter(int n,const Graph &G){
	getMaxs(1,0,n,G);
	int min=1e9;
	for(int i=1;i<=n;i++) min=std::min(maxson[i],min);
	Center ret={0,0};
	for(int i=1;i<=n;i++)if(maxson[i]==min) (ret.a?ret.b:ret.a)=i;
	return ret;
}
int fa[N];
std::vector<int>p[N];
int dfs(int u,int deep,const Graph &G){
	p[deep].push_back(u);
	int ret=deep;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa[u]) continue;
		fa[v]=u;
		ret=std::max(ret,dfs(v,deep+1,G));
	}
	return ret;
}
int tag[N];
std::vector<int>sonTag[N];
inline void getans(int u,int *ans,const Graph &G){
	ans[++ans[0]]=0;
	std::vector<int>v;
	for(int i=G.fir[u];i;i=G.nex[i])if(G.to[i]^fa[u]) v.push_back(G.to[i]);
	std::sort(v.begin(),v.end(),[](const int &a,const int &b){return tag[a]<tag[b];});
	for(int j=0,sz=v.size();j<sz;j++) getans(v[j],ans,G);
	ans[++ans[0]]=1;
}
inline int ahu(int n,const Graph &G,int root,int *ans){
	for(int i=1;i<=n;i++) p[i].clear(),sonTag[i].clear();
	fa[root]=0;int h=dfs(root,1,G);
	for(int j=0,sz=p[h].size();j<sz;j++) tag[p[h][j]]=0;
	int tot=0;
	for(int i=h-1;i;i--){
		for(int j=0,sz=p[i+1].size(),v;j<sz;j++){
			v=p[i+1][j];
			sonTag[fa[v]].push_back(tag[v]);
		}
		std::sort(p[i].begin(),p[i].end(),[](const int &a,const int &b){return sonTag[a]<sonTag[b];});
		for(int j=0,sz=p[i].size(),u;j<sz;j++){
			u=p[i][j];
			if(j&&sonTag[u]!=sonTag[p[i][j-1]]) tot++;
			tag[u]=tot;
		}
	}
	getans(root,ans,G);
	return h;
}

点分治

int root,sum;
void find(int x,int fa=0){
	size[x]=1;max[x]=0;
	for(int v,i=G.fir[x];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		find(v,x);
		size[x]+=size[v];
		if(max[x]<size[v]) max[x]=size[v];
	}
	if(max[x]<sum-size[x]) max[x]=n-size[x];
	if(max[x]<max[root]) root=x;
}
inline void calc(int u){
	
}
void divide(int u){
	vis[u]=1;
	calc(u);
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(vis[v]) continue;
		root=0;sum=size[v];
		find(v);find(root);
		divide(root);
	}
}
int main(){
	max[0]=INT_INF;sum=n;
	find(1);find(root);
	divide(root);
	return 0;
}

数据结构

普通堆

使用 std::priority_queue

使用自定义函数重载 std::set，std::priority_queue 等的比较

函数指针

inline int pqueCmp(const int &a,const int &b){return a>b;}
std::priority_queue<int,std::vector<int>,int(*)(const int &a,const int &b)>pque(pqueCmp);

lambda 函数

auto pqueCmp=[](const int &a,const int &b){return a>b;};
std::priority_queue<int,std::vector<int>,decltype(pqueCmp)>pque(pqueCmp);

并查集

int fa[N];
int find(int k){return fa[k]==k?k:fa[k]=find(fa[k]);}
inline void link(int x,int y){
	x=find(x);y=find(y);
	if(x!=y) fa[x]=y;
}

树状数组

int tree[N];
#define lowbit(x) (x&(-x))
inline void add(int pos,int k){for(;pos<=n;pos+=lowbit(pos)) tree[pos]+=k;}
inline int ask(int pos){
	int ans=0;
	for(;pos;pos-=lowbit(pos)) ans+=tree[pos];
	return ans;
}

线段树

struct Node{
	Node *ls,*rs;
	int tag;
	inline void pushup(){}
	inline void pushdown(){}
}dizhi[N*2],*root=&dizhi[0];int tot=0;
void build(Node *&tree,int l,int r){
	tree=&dizhi[++tot];
	if(l==r) return;
	int mid=(l+r)>>1;
	build(tree->ls,l,mid);build(tree->rs,mid+1,r);
	tree->pushup();
}
void change(Node *tree,int l,int r,int pos){
	if(l==r) return;
	tree->pushdown();
	int mid=(l+r)>>1;
	pos<=mid?change(tree->ls,l,mid,pos):change(tree->rs,mid+1,r,pos);
	tree->pushup();
}
void change(Node *tree,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return;
	tree->pushdown();
	int mid=(l+r)>>1;
	if(ql<=mid) change(tree->ls,l,mid,ql,qr,k);
	if(qr>mid) change(tree->rs,mid+1,r,ql,qr,k);
	tree->pushup();
}
Data ask(Node *tree,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree->x;
	tree->pushdown();
	int mid=(l+r)>>1;
	if(qr<=mid) return ask(tree->ls,l,mid,ql,qr);
	if(ql>mid) return ask(tree->rs,mid+1,r,ql,qr);
	return ask(tree->ls,l,mid,ql,qr)+ask(tree->rs,mid+1,r,ql,qr);
}

简单平衡树

std::set

替罪羊树

#define alpha 0.7
struct Node{
	Node *ls,*rs;
	int val,cnt,size;//size:num of not deleted,cnt:all
	int deleted;
	inline void pushup(){}
}*null,*root,*nodes[1100005],**badtag;
int nodeNum;
inline int isbad(Node *tree){return tree->ls->cnt>alpha*tree->cnt+5||tree->rs->cnt>alpha*tree->cnt+5;}
void dfs(Node *tree){
	if(tree==null) return;
	dfs(tree->ls);
	if(!tree->deleted) nodes[++nodeNum]=tree;
	dfs(tree->rs);
	if(tree->deleted) delete tree;
}
Node *build(int l,int r){
	if(l>r) return null;
	if(l==r){
		nodes[l]->ls=nodes[l]->rs=null;
		nodes[l]->cnt=nodes[l]->size=1;
		return nodes[l];
	}
	int mid=(l+r)>>1;
	Node *tree=nodes[mid];
	tree->ls=build(l,mid-1);tree->rs=build(mid+1,r);
	tree->pushup();
	return tree;
}
inline void rebuild(Node *&tree){
	nodeNum=0;
	dfs(tree);
	tree=build(1,nodeNum);
}
void insert(Node *&tree,int x){
	if(tree==null){
		tree=new Node;
		tree->ls=tree->rs=null;
		tree->deleted=0;tree->val=x;
		tree->size=tree->cnt=1;
		return;
	}
	tree->size++;tree->cnt++;
	if(x>tree->val) insert(tree->rs,x);
	else insert(tree->ls,x);
	if(isbad(tree)) badtag=&tree;
}
inline void Insert(Node *&tree,int x){
	badtag=&null;
	insert(tree,x);
	if(badtag!=&null) rebuild(*badtag);
}
inline int rank(Node *tree,int x){
	int ans=1;
	while(tree!=null){
		if(x<=tree->val) tree=tree->ls;
		else{
			ans+=tree->ls->size+!tree->deleted;
			tree=tree->rs;
		}
	}
	return ans;
}
inline int kth(tr *tree,int rk){
	while(tree!=null){
		if(!tree->deleted&&tree->ls->size+1==rk) return tree->val;
		if(rk<=tree->ls->size) tree=tree->ls;
		else{
			rk-=tree->ls->size+!tree->deleted;
			tree=tree->rs;
		}
	}
}
void erase(tr *tree,int rk){
	if(!tree->deleted&&rk==tree->ls->size+1){
		tree->deleted=1;
		tree->size--;
		return;
	}
	tree->size--;
	if(rk<=tree->ls->size+!tree->deleted) erase(tree->ls,rk);
	else erase(tree->rs,rk-tree->ls->size-!tree->deleted);
}

fhq-treap

struct Node{
	Node *ls,*rs;
	int val,rnd,size;
	inline void pushup(){size=1+ls->size+rs->size;}
}*root,*null;
inline void init(Node *x){x->ls=x->rs=null;x->size=1;x->rnd=rand();}
inline void init(){
	srand(822);
	null=new Node;null->ls=null->rs=null;null->size=0;null->val=INT_INF;
	root=null;
}
void split(Node *tree,int k,Node *&L,Node *&R){
	if(tree==null) return L=R=null,void();
	if(tree->ls->size>=k){
		R=tree;
		split(tree->ls,k,L,R->ls);
		R->pushup();
	}
	else{
		L=tree;
		split(tree->rs,k-tree->ls->size-1,L->rs,R);
		L->pushup();
	}
}
Node* merge(Node *L,Node *R){
	if(L==null) return R;
	if(R==null) return L;
	if(L->rnd<R->rnd){
		L->rs=merge(L->rs,R);
		return L->pushup(),L;
	}
	else{
		R->ls=merge(L,R->ls);
		return R->pushup(),R;
	}
}
inline int rank(int val){
	int ans=1;
	Node *tree=root;
	while(tree!=null){
		if(val<=tree->val) tree=tree->ls;
		else{
			ans+=tree->ls->size+1;
			tree=tree->rs;
		}
	}
	return ans;
}
inline void insert(int val){
	int rk=rank(val)-1;
	Node *x,*y;
	split(root,rk,x,y);
	Node *a=new Node;init(a);a->val=val;
	root=merge(merge(x,a),y);
}
inline void del(int val){
	int rk=rank(val);
	Node *x,*y,*z;
	split(root,rk,x,z);
	split(x,rk-1,x,y);//y->val=val,y->size=1
	root=merge(x,z);
	delete y;
}
inline int kth(int k){
	Node *x,*y,*z;
	split(root,k-1,x,y);
	split(y,1,y,z);
	root=merge(x,merge(y,z));
	return y->val;
}

link-cut-tree

struct LCT{
	struct Node{
		Node *son[2],*fa;
		int val,res;
		int tag;
	}dizhi[N],*null;
	inline void init(){null=&dizhi[0];}
	#define ident(tree,fa) (fa->son[1]==tree)
	#define notroot(tree) (tree->fa->son[0]==tree||tree->fa->son[1]==tree)
	#define pushup(tree) (tree->res=tree->son[0]->res^tree->son[1]->res^tree->val)
	inline void connect(Node *tree,Node *fa,int k){fa->son[k]=tree;tree->fa=fa;}
	inline void pushdown(Node *tree){
		if(!tree->tag) return;
		tree->tag=0;
		tree->son[0]->tag^=1;tree->son[1]->tag^=1;
		std::swap(tree->son[0],tree->son[1]);
	}
	inline void rotate(Node *tree){
		Node *fa=tree->fa,*faa=fa->fa;
		pushdown(fa);pushdown(tree);
		int k=ident(tree,fa);
		connect(tree->son[k^1],fa,k);
		tree->fa=faa;
		if(notroot(fa)) faa->son[ident(fa,faa)]=tree;
		connect(fa,tree,k^1);
		pushup(fa);pushup(tree);
	}
	inline void splay(Node *tree){
		Node *fa=tree->fa,*faa=fa->fa;
		while(notroot(tree)){
			fa=tree->fa;faa=fa->fa;
			if(notroot(fa)) rotate((ident(tree,fa)^ident(fa,faa))?tree:fa);
			rotate(tree);
		}
	}
	inline void access(Node *x){
		for(Node *lastx=null;x!=null;lastx=x,x=x->fa){
			pushdown(x);splay(x);x->son[1]=lastx;pushup(x);
		}
	}
	inline void makeroot(Node *x){access(x);splay(x);x->tag^=1;}
	inline Node* findroot(Node *x){
		access(x);splay(x);pushdown(x);
		while(x->son[0]!=null) x=x->son[0],pushdown(x);
		splay(x);return x;
	}
	inline void link(Node *x,Node *y){makeroot(x);if(findroot(y)!=x) x->fa=y;}
	inline void cut(Node *x,Node *y){
		makeroot(x);
		if(findroot(y)!=x||y->fa!=x||y->son[0]!=null) return;
		y->fa=x->son[1]=null;pushup(x);
	}
	inline Node* split(Node *x,Node *y){makeroot(x);access(y);splay(y);return y;}
	inline Node* Split(int x,int y){return split(&dizhi[x],&dizhi[y]);}
	inline void Link(int x,int y){link(&dizhi[x],&dizhi[y]);}
	inline void Cut(int x,int y){cut(&dizhi[x],&dizhi[y]);}
	inline void Change(int o,int val){Node *x=&dizhi[o];splay(x);x->val=val;pushup(x);}
};

数学

lu div

inline void luDiv(int n,ModInt (*l)[N],ModInt (*u)[N],ModInt (*a)[N]){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			u[i][j]=a[i][j];
			for(int k=1;k<i;k++) u[i][j]-=l[i][k]*u[k][j];
			l[j][i]=a[j][i];
			for(int k=1;k<i;k++) l[j][i]-=l[j][k]*u[k][i];
			l[j][i]/=u[i][i];
		}
		l[i][i]=1;
	}
}

其他

快速幂

inline long long power(long long a,long long b,long long mod=MOD){
	long long ans=1;
	while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
	return ans;
}

取模

inline long long power(long long a,long long b,long long mod=MOD){
	long long ans=1;
	while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
	return ans;
}
struct ModInt{
	long long x;
#define inline __attribute__((always_inline))
	inline ModInt operator - (ModInt o){return {(x-o.x<0)?(x-o.x+MOD):(x-o.x)};}
	inline ModInt operator - (int o){return {(x-o<0)?(x-o+MOD):(x-o)};}
	inline void operator -= (ModInt o){x=(x-o.x<0)?(x-o.x+MOD):(x-o.x);}
	inline void operator -= (int o){x=(x-o<0)?(x-o+MOD):(x-o);}
	inline friend ModInt operator - (int a,ModInt b){return {(a-b.x<0)?(a-b.x+MOD):(a-b.x)};}
	inline void operator -- (int){x--;if(x<0) x=MOD-1;}
	inline ModInt operator + (ModInt o){return {(x+o.x>=MOD)?(x+o.x-MOD):(x+o.x)};}
	inline ModInt operator + (int o){return {(x+o>=MOD)?(x+o-MOD):(x+o)};}
	inline void operator += (ModInt o){x=(x+o.x>=MOD)?(x+o.x-MOD):(x+o.x);}
	inline void operator += (int o){x=(x+o>=MOD)?(x+o-MOD):(x+o);}
	inline friend ModInt operator + (int a,ModInt b){return {(b.x+a>=MOD)?(b.x+a-MOD):(b.x+a)};}
	inline void operator ++ (int){x++;if(x==MOD) x=0;}
	inline ModInt operator * (ModInt o){return {x*o.x%MOD};}
	inline ModInt operator * (int o){return {x*o%MOD};}
	inline void operator *= (ModInt o){x=x*o.x%MOD;}
	inline void operator *= (int o){x=x*o%MOD;}
	inline friend ModInt operator * (int a,ModInt b){return {a*b.x%MOD};}
	inline ModInt operator / (ModInt o){return {x*power(o.x,MOD-2)%MOD};}
	inline ModInt operator / (int o){return {x*power(o,MOD-2)%MOD};}
	inline void operator /= (ModInt o){x=x*power(o.x,MOD-2)%MOD;}
	inline void operator /= (int o){x=x*power(o,MOD-2)%MOD;}
	inline friend ModInt operator / (int a,ModInt b){return {a*power(b.x,MOD-2)%MOD};}
	inline void operator = (int a){x=a;}
	inline int operator == (const ModInt &o){return x==o.x;}
	inline int operator == (const int &o){return x==o;}
#undef inline
};

fread 和 fwrite

namespace FastIO{
	#define BUF_SIZE 33554432
	char buff[BUF_SIZE];char *p1=buff,*p2=buff;
	#define getChar (p1==p2&&(p2=(p1=buff)+fread(buff,1,BUF_SIZE,stdin),p1==p2)?EOF:*p1++)
	__attribute__((always_inline))inline int read(){
		register int x=0;register char c=getChar;
		while(c<'0'||c>'9')	c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	__attribute__((always_inline))inline int reads(){
		register int x=0,y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	__attribute__((always_inline))inline long long readl(){
		register long long x=0;register char c=getChar;
		while(c<'0'||c>'9') c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	__attribute__((always_inline))inline int readsl(){
		register long long x=0;register int y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	__attribute__((always_inline))inline void read(char *s){
		register char c=getChar;while(c=='
'||c=='
'||c==' '||c=='	') c=getChar;
        while(c!='
'&&c!='
'&&c!=' '&&c!='	'&&c!=EOF) *s=c,s++,c=getChar;*s=0;
	}
	#undef getChar
	#define EN write('
')
	#define SPACE write(' ')
	char buffW[BUF_SIZE];int bb;
	char stack[28];
	__attribute__((always_inline))inline void write(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];
	}
	__attribute__((always_inline))inline void writeEN(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]='
',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]='
';
	}
	__attribute__((always_inline))inline void writeSP(register int x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]=' ',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]=' ';
	}
	__attribute__((always_inline))inline void write(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];
	}
	__attribute__((always_inline))inline void writeEN(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]='
',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]='
';
	}
	__attribute__((always_inline))inline void writeSP(register long long x,register short base=10){
		if(!x) return buffW[bb++]='0',buffW[bb++]=' ',void();if(x<0) buffW[bb++]='-',x=-x;
		register short top=0;
		while(x) stack[++top]=(x%base)^48,x/=base;while(top) buffW[bb++]=stack[top--];buffW[bb++]=' ';
	}
	__attribute__((always_inline))inline void write(register char c){buffW[bb++]=c;}
	__attribute__((always_inline))inline void write(char *c){while(*c) buffW[bb++]=*c,c++;}
	#define SUC_RETURN fwrite(buffW,1,bb,stdout),0
	#undef BUF_SIZE
}//namespace FastIO

快速排序

使用 sort

计算几何

lib

struct Vector{
	double x,y;
	inline double len(){return std::sqrt(x*x+y*y);}
	inline void operator += (const Vector &a){x+=a.x;y+=a.y;}
	inline void operator -= (const Vector &a){x-=a.x;y-=a.y;}
	inline void operator *= (const double &a){x*=a;y*=a;}
	inline void operator /= (const double &a){x/=a;y/=a;}
	inline Vector operator + (const Vector &a)const{return {x+a.x,y+a.y};}
	inline Vector operator - (const Vector &a)const{return {x-a.x,y-a.y};}
	inline Vector operator * (const double &a)const{return {x*a,y*a};}
	inline Vector operator / (const double &a)const{return {x/a,y/a};}
	inline double operator * (const Vector &a)const{return x*a.x+y*a.y;}
	inline double operator ^ (const Vector &a)const{return x*a.y-y*a.x;}
};
struct Line{
	Vector p,way;
	double ang;
	inline void makeLine(const Vector &a,const Vector &b){p=a;way=b;ang=atan2(b.y,b.x);}
};
inline int onRight(const Line &a,const Vector &b){return (a.way^(b-a.p))<=-eps;}
inline Vector intersect(const Line &a,const Line &b){
	double x=(b.way^(a.p-b.p))/(a.way^b.way);
	return a.p+a.way*x;
}
inline double polygonArea(int n,Vector *a){
	double S=0;
	for(int i=1;i<n;i++) S+=(a[i]^a[i+1]);
	S+=(a[n]^a[1]);
	return S/2;
}

二维凸包

inline int graham(int n,Vector *p,Vector *stack){
	for(int i=2;i<=n;i++) p[i].ang=atan2(p[i].y-p[1].y,p[i].x-p[1].x);
	std::sort(p+2,p+1+n);
	stack[1]=p[1];int top=1;
	for(int i=2;i<=n;i++){
		while(top>1&&cross(p[i]-stack[top],stack[top]-stack[top-1])<=eps) top--;
		stack[++top]=p[i];
	}
	stack[++top]=p[1];
	return top;
}

半平面交

int left,right;
Line que[N];
inline int halfPlane(int n,Line *a,Vector *p){
	std::sort(a+1,a+1+n,cmp);
	left=right=0;que[0]=a[1];
	for(int i=2;i<=n;i++){
		while(left<right&&onRight(a[i],p[right])) right--;
		while(left<right&&onRight(a[i],p[left+1])) left++;
		que[++right]=a[i];
		if(abs(cross(que[right].way,que[right-1].way))<=eps){//平行
			if(onRight(que[right],que[right-1].p)&&abs(que[right].way.y+que[right-1].way.y+que[right].way.x+que[right-1].way.x)<=eps) return 0;
			right--;
			if(!onRight(que[right],a[i].p)) que[right]=a[i];
		}
		if(left<right) p[right]=intersect(que[right],que[right-1]);
	}
	while(left<right&&onRight(que[left],p[right])) right--;
	if(right-left<=1) return 0;
	p[left]=intersect(que[left],que[right]);
	return 1;
}

旋转卡壳

inline int nex(int i){return i==n?1:(i+1);}
int main(){
	if(n<=3) return printf("%lld
",(q[2]-q[1]).len()),0;
	long long ans=0;
	for(int i=1,j=3;i<n;i++){
		while(abs((q[j]-q[i])^(q[j]-q[i+1]))<=abs((q[nex(j)]-q[i])^(q[nex(j)]-q[i+1]))) j=nex(j);
		ans=std::max(ans,std::max((q[j]-q[i]).len(),(q[j]-q[i+1]).len()));
	}
	printf("%lld
",ans);
	return 0;
}

字符串

kmp

manacher

AC 自动机

struct Node{
	Node *tr[26],*fail;
	int cnt,in;
}dizhi[N],*root=&dizhi[0],*which[N];
int tot;
inline void insert(char *s,int id){
	Node *tree=root;
	for(int num,i=1;s[i];i++){
		num=s[i]-'a';
		if(!tree->tr[num]) tree->tr[num]=&dizhi[++tot];
		tree=tree->tr[num];
	}
	which[id]=tree;
}
int left,right;
Node *que[N];
inline void build(){
	left=0;right=-1;
	root->fail=root;
	for(int i=0;i<26;i++){
		if(root->tr[i]) root->tr[i]->fail=root,que[++right]=root->tr[i];
		else root->tr[i]=root;
	}
	Node *u;
	while(left<=right){
		u=que[left++];
		for(int i=0;i<26;i++){
			if(u->tr[i]){
				u->tr[i]->fail=u->fail->tr[i];
				que[++right]=u->tr[i];u->fail->tr[i]->in++;
			}
			else u->tr[i]=u->fail->tr[i];
		}
	}
}

SAM

struct Node{
	Node *son[26];
	int len,cnt;
	Node *link;
}dizhi[N*2],*root=&dizhi[0],*last=root;
int tot;
inline void add(int c){
	Node *p=last,*now=&dizhi[++tot];
	now->len=p->len+1;now->cnt=1;
	for(;p&&!p->son[c];p=p->link) p->son[c]=now;
	if(!p) now->link=root;
	else{
		Node *q=p->son[c];
		if(q->len==p->len+1) now->link=q;
		else{
			Node *clone=&dizhi[++tot];*clone=*q;
			clone->len=p->len+1;clone->cnt=0;
			q->link=now->link=clone;
			for(;p&&p->son[c]==q;p=p->link) p->son[c]=clone;
		}
	}
	last=now;
}

PAM

struct Node{
	Node *son[26],*fail;
	int len,cnt;
}dizhi[N],*root0=&dizhi[0],*root1=&dizhi[1],*last;
int tot;
inline void init(){
	last=root1;
	root0->fail=root1;root1->fail=root0;
	root1->len=-1;
	tot=1;
}
char s[N];
inline int cnt(Node *u){
	if(u==root0||u==root1) return 0;
	if(u->cnt) return u->cnt;
	return u->cnt=1+cnt(u->fail);
}
inline int insert(int i){
	while(s[i-last->len-1]^s[i]) last=last->fail;
	if(!last->son[s[i]-'a']){
		Node *u=&dizhi[++tot];
		u->len=last->len+2;
		reg Node *j=last->fail;
		while(s[i-j->len-1]^s[i]) j=j->fail;
		u->fail=j->son[s[i]-'a'];
		if(!u->fail) u->fail=root0;
		last->son[s[i]-'a']=u;
	}
	last=last->son[s[i]-'a'];
	return cnt(last);
}