模板库:

字典树,数组实现(hdu1251)

#include 
     
      using namespace std;const int maxn=1e6+10,maxm=2e6+10;struct Trie{
    #define base 'a'	int next[maxn][27],size,cnt[maxn];	void init(){		size=1;		memset(next[0],0,sizeof next[0]);	}	void add(char *str,int len=0){		int cur=0,k;		if(len==0) len=strlen(str);		for(int i=0;i
     

FFT 完整模板 自定义虚数

struct cp {  double x, y;  cp(double a=0, double b=0):x(a), y(b) {}  inline cp operator +(cp &b) {return cp(x+b.x, y+b.y);}  inline cp operator -(cp &b) {return cp(x-b.x, y-b.y);}  inline cp operator *(cp &b) {return cp(x*b.x-y*b.y, x*b.y+y*b.x);}  inline cp conj() {return cp(x, -y);}};struct FFT {  int size, rev[maxn];  void init(int lim) {    size=1;int k=0;    while(size
     
      >1;      cp wn=(cp){cos(2*PI/l), flag*sin(2*PI/l)};      for(cp *p=a; p!=a+size; p+=l) {        cp w=(cp){1,0};        for(int k=0; k
     

欧拉函数

ll euler(ll n) {	ll res=n,a=n;	for(int i=2; i*i<=a; i++) {		if(a%i==0) {			res=res/i*(i-1);			while(a%i==0) a/=i;		}	}	if(a>1) res=res/a*(a-1);	return res;}int euler[maxn];void geteul() {	euler[1]=1;	int n=maxn-10;	for(int i=2; i<=n; i++) euler[i]=i;	for(int i=2; i<=n; i++)if(euler[i]==i)		for(int j=i; j<=n; j+=i)			euler[j]=euler[j]/i*(i-1);}

打表 莫比乌斯函数

int mu[maxn],prime[maxn],nump;bool isp[maxn];void getmu(){  mu[1]=1;  int n=maxn-5;  for(int i=2;i<=n;i++){		if(!isp[i])prime[++nump]=i,mu[i]=-1;		for(int j=1;j<=nump&&prime[j]*i<=n;j++){			isp[i*prime[j]]=1;			if(i%prime[j]==0){mu[i*prime[j]]=0;break;}			else mu[i*prime[j]]=-mu[i];		}  }}

素数筛.米勒罗宾判素数,需要快速乘

ll prime[maxn];ll count_primell init_prime(ll n){	ll count=0;	bool vis[n+1];	for(int i=2;i<=n;++i)vis[i] = true;	vis[2] = true;	for(int j=2;j<=n;++j)		if(vis[j]==true)			for(int m=2;j*m<=n;++m)vis[j*m] = false;	for(int i=2;i<=n;++i)		if(vis[i]==true)			prime[count++]=i;	return count;}bool test(ll n,ll a,ll d) {	if(n==2||n==a) return true;	if((n&1)==0) return false;	while(!(d&1)) d>>=1;	ll t=powmod(a,d,n);	while(d!=n-1&&t!=1&&t!=n-1){		t=mul_mod(t,t,n);		d<<=1;	}	return (t==n-1||(d&1)==1);}bool isprime(ll n) {	if(n<2) return false;	rep(i,0,count_prime) if(!test(n,prime[i],n-1)) return false;	return true;}

初等数论板-加入快速乘,快速乘快速幂

const ll mod=1e9+7;ll gcd_mod(ll a,ll b,ll c=mod){while(b)b=((a%b)%c+((a=b)-b)%c)%c;return a;}ll lcm_mod(ll a,ll b,ll c=mod){return (a/gcd(a,b)*b)%mod;}ll pow_mod(ll a,ll b,ll c=mod,ll ans=1){while(b){if(b&1) ans=(a*ans)%c;a=(a*a)%c,b>>=1;}return ans;}ll inv_mod(ll a){return pow_mod(a,mod-2);}ll mul_mod(ll a, ll b, ll c=mod) {if(a
     
      >=1;}return res;}ll pow_mul_mod(ll a, ll b, ll n=mod) {ll res=1;while(b) {if(b&1)res=mul_mod(res,a,n);a=mul_mod(a,a,n);b>>=1;}return res;}
     

Dfs查找欧拉路径/回路

int vis[maxn];int cnt;struct node {	int to,flag,id,next;}e[maxm];int head[maxn],nume,deg[maxn];inline void _add(int a,int b,int c){	e[++nume]=(node){b,1,c,head[a]};	head[a]=nume;}inline void add(int a,int b,int c){	addnode(a,b,c);addnode(b,a,-c);}vector
     
       ans[maxn];void dfs(int now){	vis[now]=1;	for(int i=head[now];i;i=e[i].next){		if(!e[i].flag) continue;		e[i].flag=e[i^1].flag=0;		dfs(e[i].to);		ans[cnt].push_backe(-e[i].id);	}}void solve(){	rep(i,1,n){		if(!vis[i]&°[i]&1) {			cnt++;			dfs(i);		}	}	rep(i,1,n){		if(!vis[i]&°[i]){			cnt++;			dfs(i);		}	}}
     

平衡树之Treap,插入,删除,zag,zig,更新,求第k大,求val名次,求前驱,求后继

#define nd treap[now]#define ndl treap[treap[now].l]#define ndr treap[treap[now].r]#define ndt treap[tmp]struct node {	int l,r,val,num,size,rnd;}treap[maxn];int cnt,root,ans;inline void resize(int now){	nd.size=ndl.size+ndr.size+nd.num;}inline void rturn(int &now){	int tmp=nd.l;	nd.l=ndt.r,ndt.r=now;	ndt.size=nd.size;	resize(now);	now=tmp;}inline void lturn(int &now){	int tmp=nd.r;	nd.r=ndt.l,ndt.l=now;	ndt.size=nd.size;	resize(now);	now=tmp;}void insert(int &now,int val){	if(!now) {		now=++cnt;		nd=(node){0,0,val,1,1,rand()};		return ;	}	nd.size++;	if(val==nd.val)nd.num++;	else if(val>nd.val){		insert(nd.r,val);		if(ndr.rnd
     
      1){			nd.num--,nd.size--;			return ;		}		if(nd.r*nd.l==0) now=nd.l+nd.r;		else {			if(ndl.rnd
      
       nd.val) erase(nd.r,val);		else erase(nd.l,val);	}}int query_rank(int now,int val){	if(!now) return 0;	if(val==nd.val)return ndl.size+1;	if(val>nd.val) return ndl.size+nd.num+query_rank(nd.r,val);	return query_rank(nd.l,val);}int query_val(int now,int rank){	if(!now) return 0;	if(rank<=ndl.size) return query_val(nd.l,rank);	if(rank-ndl.size<=nd.num) return nd.val;	return query_val(nd.r,rank-ndl.size-nd.num);}int query_pre(int now,int val){	if(!now) return ans;	if(val<=nd.val) return query_pre(nd.l,val);	ans=nd.val;	return query_pre(nd.r,val);}int query_sub(int now,int val){	if(!now) return ans;	if(val>=nd.val) return query_sub(nd.r,val);	ans=nd.val;	return query_sub(nd.l,val);}
      
     

数列分块单点修改

int size;ll num[maxn],tag[maxn];int id[maxn];void update(int s,int t,ll x){    for(int i=s;i<=min(id[s]*size,t);i++)        num[i]+=x;    if(id[s]!=id[t]){        for(int i=(id[t]-1)*size+1;i<=t;i++)            num[i]+=x;    }    for(int i=id[s]+1;i<=id[t]-1;i++){        tag[i]+=x;    }}void init(){	size=sqrt(n);  for(int i=1;i<=n;i++) id[i]=(i-1)/size+1;}

主席树求区间第K大

#include 
     
      #define nd seg[now]#define ndp seg[pre]#define mid ((s+t)>>1)using namespace std;const int maxn=1e5+10;int casn,n,m,k;int num[maxn],rt[maxn],size;vector
      
       pos;struct node{	int l,r,sum;}seg[maxn*20];void maketree(int s=1,int t=n,int &now=rt[0]){	now=++size;nd={s,t,0};	if(s==t) return ;	maketree(s,mid,nd.l);maketree(mid+1,t,nd.r);}void update(int &now,int pre,int k,int s=1,int t=n){	now=++size;nd=ndp,nd.sum++;	if(s==t) return ;	if(k<=mid)update(nd.l,ndp.l,k,s,mid);	else update(nd.r,ndp.r,k,mid+1,t);}int query(int now,int pre,int k,int s=1,int t=n){	if(s==t) return s;	int sum=seg[ndp.l].sum-seg[nd.l].sum;	if(k<=sum) return query(nd.l,ndp.l,k,s,mid);	else return query(nd.r,ndp.r,k-sum,mid+1,t);}int main(){	scanf("%d",&casn);	while(casn--){		scanf("%d%d",&k,&m);		pos.clear();		size=0;		for(int i=1;i<=k;i++){			scanf("%d",num+i);			pos.push_back(num[i]);		}		sort(pos.begin(),pos.end());		pos.erase(unique(pos.begin(),pos.end()),pos.end());		n=pos.size();		maketree(1,n,rt[0]);		for(int i=1;i<=k;i++){			int id=lower_bound(pos.begin(),pos.end(),num[i])-pos.begin()+1;			update(rt[i],rt[i-1],id);		}		while(m--){			int a,b,c;			scanf("%d%d%d",&a,&b,&c);			printf("%d\n",pos[query(rt[a-1],rt[b],c)-1]);		}	}  return 0;}
      
     

RMQ-树状数组

int bt[maxn],num[maxn];#define lb(x) (x&(-x))void upd(int pos, int x) {	num[pos] = x;	for(int i = pos; i <= n; i += lb(i)) {		bt[i] = x;		for(int j = 1; j < lb(i); j <<= 1) {			bt[i] = bt[i] > bt[i-j] ? bt[i] : bt[i-j];		}	}}void init() {	memset(bt, 0, sizeof bt);	for(int i = 1; i <= n; i++) {		bt[i] = num[i];		for(int j = 1; j 
     
       bt[i-j] ? bt[i] : bt[i-j];	}}int find(int l, int r) {	int ans = 0;	while(1) {		ans = ans > num[r] ? ans : num[r];		if(r == l) break;		for(r -= 1; r-l >= lb(r); r -= lb(r))			ans = ans > bt[r] ? ans : bt[r];	}	return ans;}
     

RMQ-ST表

int table[maxn][1<<18];void makest(int n) {	for(int i=1; i<=n; i++)		table[i][0]=A[i];	int m=(int)(log((double)n)/log(2.0)));	for(int j=1; j<=m; j++) {	for(int i=1; i+(1<
     
      <=n; i++)			table[i][j]=min(table[i][j-1],table[i+(1<
     

带删除操作的并查集

#define same(a,b) (find(a)==find(b))int pre[maxn],id[maxn];int numid;int fd(int a) {	return pre[a]==a?a:pre[a]=find(pre[a]);}int find(int a){return fd(id[a])};void unite(int a,int b){	a=find(id[a]),b=find(id[b]);	pre[b]=a;}void remove(int now){	int pos=find(id[now]);	id[now]=++numid;	pre[numid]=numid;}

doubly树上倍增

struct node {	int to,next;} e[maxm];int head[maxn],nume;void add(int a,int b) {	e[++nume]=(node) {b,head[a]};	head[a]=nume;}int dt[31][maxn],dep[maxn];void ldfs(int now,int pre){	for(int i=head[now];i;i=e[i].next){		int to=e[i].to;		if(to!=pre&&to!=dt[0][now]){			dep[to]=dep[now]+1;			dt[0][to]=now;			ldfs(to,now);		}	}}int lca(int a,int b){	if(dep[a]
     
      >i);i++){		if((dis>>i)&1) a=dt[i][a];	}	if(a==b) return a;	for(int i=20;i>=0;i--)		if(dt[i][a]!=dt[i][b]){			a=dt[i][a],b=dt[i][b];		}	return dt[0][a];}void init(int root){	dep[root]=1;	ldfs(root,root);	for(int i=1;(1<
      
       <=n;i++)	for(int j=1;j<=n;j++)		dt[i][j]=dt[i-1][dt[i-1][j]];}
      
     

常数优化高级指令

#pragma comment(linker, "/stack:200000000")#pragma GCC optimize("Ofast")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#pragma GCC optimize("unroll-loops")

KMP

int table[maxn][1<<18];void makest(int n) {	for(int i=1; i<=n; i++)		table[i][0]=A[i];	int m=(int)(log((double)n)/log(2.0)));	for(int j=1; j<=m; j++) {	for(int i=1; i+(1<
     
      <=n; i++)			table[i][j]=min(table[i][j-1],table[i+(1<
     

矩阵,重载运算符+-*,清空与赋值函数,成员函数:clear清空 e转化为单位矩阵 fill用数字或者数组填充,pow快速幂函数 带取模

struct node {int a,b;ll x[maxn][maxn];	void clear(int n=0,int m=0){a=n,b=m;memset(x,0,sizeof x);}	void e(int n){a=b=n;for(int i=0;i
     
      >=1;}return ans;}};
     

单调栈

int stk[maxn];//向左的第一个最小数字的位置void mstk(int a[]=num,int l[]=pos,int len=n){	int top=0;	for(int i=1;i<=n;i++){		while(top&&a[stk[top]>=a[i]]) top--;		if(top) l[i]=stk[top];		else l[i]=0;		stk[++top]=i;	}}

SPFA最小费用最大流,朴素无优化,复杂度$O(EV^2)$

struct node {	int pre,to,cap,cost,next;}e[maxm];int head[maxn],nume,inq[maxn],sum,ans;int que[maxn],pre[maxn],dis[maxn];int num[maxn],S,T;inline void addedge(int a,int b,int c,int d){	e[++nume]={a,b,c,d,head[a]};	head[a]=nume;}inline void add(int a,int b,int c,int d){	addedge(a,b,c,d);addedge(b,a,0,-d);}bool spfa(){	for(int i=0;i<=T;i++)dis[i]=INF;	dis[S]=que[0]=S;	int top=0,end=1;	while(top!=end){		int now=que[top++];top%=maxn;		for(int i=head[now];i;i=e[i].next){			if(e[i].cap&&dis[e[i].to]>dis[now]+e[i].cost){				pre[e[i].to]=i;				dis[e[i].to]=dis[now]+e[i].cost;				if(!inq[e[i].to]){					inq[e[i].to]=true;					que[end++]=e[i].to;end%=maxn;				}			}		}		inq[now]=false;	}	return dis[T]!=INF;}void dfs(){	int flow=INF;	for(int i=pre[T];i;i=pre[e[i].pre]) flow=min(flow,e[i].cap);	for(int i=pre[T];i;i=pre[e[i].pre]) {		e[i].cap-=flow;		e[i^1].cap+=flow;		ans+=e[i].cost*flow;	}}void mcf(){	ans=0;	while(spfa()) dfs();}

int读入挂终极版Plus之改无可改:fread读取内存,每次移动指针减少寻址时间,需要输入Ctrl+Z或者用文件输入

struct io {char buf[1 << 26], *s;io() {fread(s = buf, 1, 1 << 26, stdin);}inline int read() {register int res = 0;while(*s < '0' || *s > '9') s++;while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';return res;}} ip;#define read ip.read

最大流Dinic算法,复杂度上限$O(EV^2)$,朴素无优化

int to[maxm],cap[maxm],nex[maxm];int head[maxn],S,T,nume,ans,dis[maxn];int q[maxn];void add(int a,int b,int c){    to[nume]=b,cap[nume]=c,nex[nume]=head[a];    head[a]=nume++;    to[nume]=a,cap[nume]=0,nex[nume]=head[b];    head[b]=nume++;}bool bfs(){    memset(dis,-1,sizeof dis);    int top=0,end=0;    q[end++]=S;    dis[S]=0;    while(top!=end){        int now=q[top++];top%=maxn;        for(int i=head[now];~i;i=nex[i])            if(dis[to[i]]==-1&&cap[i]){                dis[to[i]]=dis[now]+1;                q[end++]=to[i];end%=maxn;            }    }    return dis[T]!=-1;}int dfs(int now,int last){    if(now==T) return last;    int used=0,flow;    for(int i=head[now];~i;i=nex[i]){        if(cap[i]&&dis[to[i]]==dis[now]+1){            flow=last-used;            flow=dfs(to[i],min(flow,cap[i]));            used+=flow;            cap[i]-=flow;            cap[i^1]+=flow;            if(used==last) return last;        }    }    if(used==0) dis[now]=-1;    return used;}void dinic(){    ans=0;    while(bfs())ans+=dfs(S,0x3f3f3f3f);}

int读入挂终极版:fread读取内存,每次需要单独输入Ctrl+Z作为结束输入

#define tpyeinput intinline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}inline void read(tpyeinput &num1,tpyeinput &num2){read(num1);read(num2);}inline void read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){read(num1);read(num2);read(num3);}inline void read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){read(num1);read(num2);read(num3);read(num4);}

最长不上升子序列和最长上升子序列的O(nlogn)算法 //合唱队列问题

#include 
     
      using namespace std;const int maxn=1e5+10;int casn,n,m,k;int num[maxn];int dp[maxn];int len;int lwb(int now){	int l=0,r=len,ans=0;	while(l
      
       >1;		if(dp[mid]>=now) l=mid+1;		else r=mid;	}	return l;}int lwb2(int now){	int l=0,r=len;	while(l
       
        >1;		if(dp[mid]>=now) r=mid;		else l=mid+1;	}	return l;}int main(){	cin>>n;	for(int i=1;i<=n;i++) cin>>num[i];	for(int i=1;i<=n;i++){		if(dp[len]>=num[i]) dp[++len]=num[i];		else dp[lwb(num[i])]=num[i];	}	cout<
        
         <
        
       
      
     

int读入挂1,可判断文件末尾,重载函数可读入1-4个参数,返回值为是否成功读入

#define tpyeinput intinline bool read(tpyeinput &num){int flag=1,ch=getchar();if(ch==EOF) return false;num=0;while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=num*10+ch-'0',ch=getchar();}num*=flag;return true;}inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}

int读入挂2,返回值为读入值,无法判定文件末尾

#define tpyeinput intinline tpyeinput read(){tpyeinput num=0,flag=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+ch-'0',ch=getchar();}return flag*num;}

非递归最大公因数,最小公倍数,非递归快速幂,求逆元,带取模

const ll mod=1e9+7;ll gcd(ll a,ll b,ll c=mod){while(b)b=((a%b)%c+((a=b)-b)%c)%c;return a;}ll lcm(ll a,ll b,ll c=mod){return (a/gcd(a,b)*b)%mod;}ll powmod(ll a,ll b,ll c=mod,ll ans=1){while(b){if(b&1) ans=(a*ans)%c;a=(a*a)%c,b>>=1;}return ans;}ll inv(ll a){return powmod(a,mod-2);}

最大连续子矩阵/连续子段和

/*poj1050 把二维看成一维先枚举行的起点和终点再把起点行和终点行间每一列的数值压缩到每一个点上然后求一个最长连续字段和复杂度O(n^3)*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=1e3+10;const int maxm=1e6+10;const int INF=0x3f3f3f3f;#define ll long longint casn,n,m,k;int smax(int a[],int len){	int mx=0,sub=0;	for(int i=1;i<=len;i++){		sub=max(a[i],sub+a[i]);		mx=max(sub,mx);	}	return mx;}int arr[maxn];int dp[maxn][maxn];int main(){#define test#ifdef test	freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif	while(~scanf("%d",&n)){		for(int i=1;i<=n;i++){			for(int j=1;j<=n;j++){				scanf("%d",&dp[i][j]);			}		}		int ans=-INF;		for(int i=1;i<=n;i++){			memset(arr,0,sizeof arr);			for(int j=i;j<=n;j++){				for(int k=1;k<=n;k++){					arr[k]+=dp[j][k];				}				ans=max(ans,smax(arr,n));			}		}		printf("%d\n",ans);	}#ifdef test	fclose(stdin);fclose(stdout);system("out.txt");#endif	return 0;}
        
       
      
     

tarjan双边强连通分量缩点,两次dfs求树的直径

#include 
     
      using namespace std;const int maxn=1e5+10;const int maxm=1e6+10;const int INF=0x3f3f3f3f;typedef long long ll;typedef unsigned long long ull;#define tpyeinput intinline bool read(tpyeinput &num){int flag=1,ch=getchar();if(ch==EOF) return false;num=0;while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=num*10+ch-'0',ch=getchar();}num*=flag;return true;}inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}struct node {int to,cost,next;}e[maxm],e2[maxm];int head[maxn],head2[maxn],nume,nume2;void add(int a,int b,int c=1,node *eg=e,int &ne=nume,int hd[]=head){eg[++ne]=(node){b,c,hd[a]};hd[a]=ne;}int casn,n,m,k;int low[maxn],dfn[maxn],stk[maxn];int ins[maxn];int top,numc,numd,belong[maxn];void tjdfs(int now,int pre) {    dfn[now]=low[now]=++numd;    stk[++top]=now;    ins[now]=1;    for(int i=head[now]; i; i=e[i].next) {        int to=e[i].to;        if(to==pre)continue;        if(ins[to]==0) tjdfs(to,now);        low[now]=min(low[now],low[to]);    }    if(low[now]==dfn[now]) {        numc++;        do {            belong[stk[top]]=numc;            ins[stk[top]]=-1;        } while(stk[top--]!=now);    }}void tjmake(){    for(int i=1;i<=n;i++){        int a=belong[i];        for(int j=head[i];j;j=e[j].next){            int to=e[j].to;            int b=belong[to];            if(a==b) continue;            add(a,b,1,e2,nume2,head2);            add(b,a,1,e2,nume2,head2);        }    }}inline void tjinit(){    numc=nume2=numd=0;    top=-1;    memset(ins,0,sizeof ins);    memset(dfn,0,sizeof dfn);    memset(head2,0,sizeof head);    memset(belong,0,sizeof belong);    memset(low,0,sizeof low);    memset(stk,0,sizeof stk);}inline void tarjan(){    tjinit();    for(int i=1;i<=n;i++) if(ins[i]==0){         tjdfs(i,-1);    }    tjmake();}int vis[maxn],cnt=0,pos,ans;void dfs(int now,int dep=0){    vis[now]=1;    if(dep>cnt){        cnt=dep;        pos=now;    }    for(int i=head2[now];i;i=e2[i].next){        int to=e2[i].to;        if(!vis[to]) dfs(to,dep+1);    }}int main(){//#define test#ifdef test    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);#endif    read(casn);    while(casn--){        read(n,m);        memset(head,0,sizeof head);        nume=0;        for(int i=0;i
     

简单的tarjan强连通分量

int stk[maxn],top,cnt,dfn[maxn],low[maxn],numc,belong[maxn],vis[maxn];struct node {int to,cost,next;}e[maxm];int head[maxn],nume;void add(int a,int b,int c=1){e[++nume]=(node){b,c,head[a]};head[a]=nume;}void tdfs(int now){	dfn[now]=low[now]=++cnt;	stk[top++]=now;	vis[now]=1;	for(int i=head[now];i;i=e[i].next){		int to=e[i].to;		if(!dfn[to]){tdfs(to);low[now]=min(low[now],low[to]);}		else if(vis[to]) low[now]=min(low[now],dfn[to]);	}	if(low[now]==dfn[now]){		numc++;		int to;		do{			to=stk[--top];			belong[to]=numc;			vis[to]=0;		}while(to!=now);	}}void tarjan(int numv=n){	for(int i=1;i<=numv;i++){		if(!dfn[i]) tdfs(i);	}}void ginit(){		nume=top=numc=cnt=0;		memset(head,0,sizeof head);		memset(dfn,0,sizeof dfn);		memset(low,0,sizeof low);		memset(belong,0,sizeof belong);		memset(vis,0,sizeof vis);}//只计算强连通分量和归属

tarjan求无向图割点

void tdfs(int now,int pre){	low[now]=dfn[now]=++cnt;	int numt=0;	for(int i=head[now];i;i=e[i].next){		int to=e[i].t;		if(to==pre) continue;		if(!dfn[to]){			numt++;			tdfs(to,now);			low[now]=min(low[to],low[now]);			if(now!=pre&&low[to]>=dfn[now]){				cut[now]=1;			}		}else low[now]=min(low[now],dfn[to]);	}	if(now==pre&&numt>1) cut[now]=1;}

非递归并查集路径压缩,按秩合并

int pre[maxn],rk[maxn];int find(int a){	if(pre[a]==-1) return a;	int t,rt=a;	while(pre[rt]!=-1) rt=pre[rt];	while(a!=rt)t=pre[a],pre[a]=rt,a=t;	return rt;}#define same(a,b) (find(a)==find(b))void unite(int a,int b){	a=find(a),b=find(b);	if(a==b) return;	if(rk[a]>rk[b])		pre[b]=a;	else {		pre[a]=b;		if(rk[a]==rk[b])			rk[b]++;	}}

简单的并查集

int pre[maxn];int find(int a){return !(~pre[a])?a:pre[a]=find(pre[a]);}#define same(a,b) (find(a)==find(b))#define unite(a,b) pre[find(b)]=find(a)

SPFA,SLF优化,链式前向星,数组循环队列

struct node {int to;int cost;int next;}e[maxm];int head[maxn],nume;inline void add(int a,int b,int c=1){e[++nume]=(node){b,c,head[a]};head[a]=nume;}bool vis[maxn];int que[maxn];long long dis[maxn];void spfa(int st=1,int ed=n){  int top=0,end=0,now;  memset(dis,0x3f,sizeof dis);  memset(vis,0,sizeof vis);  que[end++]=st,dis[st]=0;  while(top!=end){    now=que[top++],top%=maxn;    vis[now]=false;    for(int i=head[now];i;i=e[i].next){      int to=e[i].to;      if(now==to) continue;      if(dis[now]+e[i].cost

dijkstra,优先队列优化,链式前向星

typedef pair
     
      p;priority_queue
      
 q;int dis[maxn];void dijkstra(){	int now;	memset(dis,0xc0,sizeof dis);	q.push(p(-INF,st)),tms[st]=1;	dis[st]=0,num[st]=nump[st];	while(!q.empty()){		now=q.top().second,q.pop();		for(int i=head[now];i;i=e[i].next){			int to=e[i].to;			if(now==to) continue;			int cost=dis[now]+e[i].cost;			if(cost
     

树状数组区间求和,单点更新

#define lb(x) (x&(-x))int bt[maxn];inline void upd(int pos,int x){while(pos<=n)bt[pos]+=x,pos+=lb(pos);}inline int psum(int pos,int sum=0){while(pos) sum+=bt[pos],pos-=lb(pos);return sum;}

线段树单点更新区间求和

#define nd lst[now]struct node {	int l,r,sum;}lst[maxm];void maketree(int s=1,int t=n,int now=1){	nd=(node){s,t,0};	if(s==t) return ;	maketree(s,(s+t)>>1,now<<1);	maketree(((s+t)>>1)+1,t,now<<1|1);}void update(int pos,int x,int now=1){	if(pos
     
      nd.r) return ;	nd.sum+=x;	if(nd.r==nd.l) return;	update(pos,x,now<<1);	update(pos,x,now<<1|1);}int query(int s,int t,int now=1){	if(s>nd.r||t
      
       =nd.r) return nd.sum;	return query(s,t,now<<1)+query(s,t,now<<1|1);}
      
     

线段树区间修改求和

#define nd seg[now]#define ndl seg[now<<1]#define ndr seg[now<<1|1]using namespace std;const int maxn=5e5+10;int casn,n,m,k;int num[maxn];struct node {	int l,r;int sum,tag;	int len(){return r-l+1;}}seg[maxn<<2];void pushdown(int now){	if(nd.tag){		ndl.tag+=nd.tag;		ndr.tag+=nd.tag;		ndl.sum+=nd.tag*ndl.len();		ndr.sum+=nd.tag*ndr.len();		nd.tag=0;	}}void pushup(int now){nd.sum=ndl.sum+ndr.sum;}void maketree(int s=1,int t=n,int now=1){	seg[now]=(node){s,t,num[s],0};	if(s==t)return ;	maketree(s,(s+t)>>1,now<<1);	maketree(((s+t)>>1)+1,t,now<<1|1);	pushup(now);}void update(int s,int t,ll x,int now=1){	if(s>nd.r||t
     
      =nd.r){		nd.sum+=nd.len()*x,nd.tag+=x;		return ;	}	pushdown(now);	update(s,t,x,now<<1);	update(s,t,x,now<<1|1);	pushup(now);}int query(int s,int t,int now=1){	if(s>nd.r||t
      
       =nd.r) return nd.sum;	pushdown(now);	return query(s,t,now<<1)+query(s,t,now<<1|1);}
      
     

手写二叉堆

void up(int now){	int t=hp[now];	while(now>1&&hp[now>>1]>hp[now])		hp[now]=hp[now>>1],now>>=1;	hp[now]=t;}void down(int now){	int t=hp[now];	for(int pos=now<<1;pos<=sz;pos<<=1){		pos+=(pos
     
      hp[pos+1]);		if(hp[pos]
     

kruskal

struct node{int from,to,cost;}e[maxm];bool cmp(node &a,node &b){return a.cost

//板子有锅是基本情况