写在前面

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define gma(x,y) x=max(x,y)
#define gmi(x,y) x=min(x,y)
using namespace std;
int main(){
    return 0;
}

邻接表

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v){
    node *o=&pool[cnt++];
    o->v=v,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->next=h[v],h[v]=o;
}

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=d,o->next=h[v],h[v]=o;
}

树状数组

struct FenwickTree{
    int p[MAXN];
    void Add(int id,int x){
        while(id<=n)p[id]+=x,id+=id&(-id);
    }
    int Query(int id){
        int s=0;
        while(id)s+=p[id],id-=id&(-id);
        return s;
    }
};

网络流

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next,*rev;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=0,o->next=h[v],h[v]=o;
    h[u]->rev=h[v],h[v]->rev=h[u];
}

并查集

struct UFS{
    int p[MAXN];
    UFS(){memset(p,-1,sizeof(p));}
    void clear(){memset(p,-1,sizeof(p));}
    inline bool Union(int x,int y){x=Find(x),y=Find(y);if(x!=y){p[x]=y;return 1;}return 0;}
    int Find(int x){if(p[x]<0)return x;return p[x]=Find(p[x]);}
};

读入优化（int）

int _(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

读入优化（long long）

long long _(){
    long long x=0;
    int f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

输出优化

void __(ll x){
    if(!x){puts("0");return;}
    char c[30]={};
    int i=0;
    while(x)c[i++]=x%10+'0',x/=10;
    while(i)putchar(c[--i]);
    puts("");
}

线性筛

namespace Mobius{
    int n,t,miu[MAXN],phi[MAXN],pri[MAXN],cnt,d[MAXN];
    void Init(){
        miu[1]=1;
        phi[1]=1;
        for(int i=2;i<=n;i++){
            if(!d[i])pri[++cnt]=i,d[i]=cnt,miu[i]=-1,phi[i]=i-1;
            for(int j=1;i*pri[j]<=n&&j<=d[i];j++){
                t=i*pri[j];
                d[t]=j;
                miu[t]=j<d[i]?-miu[i]:0;
                phi[t]=j<d[i]?phi[i]*(pri[j]-1):phi[i]*pri[j];
            }
        }
    }
}

倍增LCA

#define enu() for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u])

namespace LCA{
    const int LOG=17,MAXL=20;
    int lpnt[MAXN][MAXL];
    void work(int u,int lev){
        if(lpnt[u][lev])lpnt[u][lev+1]=lpnt[lpnt[u][lev]][lev];
        enu()work(o->v,lev);
    }
    int LCA(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        dwn(i,LOG,0)if(lpnt[u][i]&&dep[lpnt[u][i]]>=dep[v])u=lpnt[u][i];
        dwn(i,LOG,0)if(lpnt[u][i]!=lpnt[v][i])u=lpnt[u][i],v=lpnt[v][i];
        if(u==v)return u;return pnt[u];
    }
    void Init(){rep(i,1,n)lpnt[i][0]=pnt[i];rep(i,0,LOG)work(1,i);}
}

ST表LCA

namespace LCA{
    const int LOG=22,MAXL=25;
    int ST[MAXL][2*MAXN],pos[MAXL][2*MAXN],num[MAXN],pnt[MAXN],Log[2*MAXN],Depth[MAXN];
    int dfn;
    void dfs0(int u,int dep){
        num[u]=++dfn,Depth[u]=dep,pos[0][dfn]=u;
        ST[0][dfn]=dep;
        for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u]){
            pnt[o->v]=u;
            dfs0(o->v,dep+1);
            ST[0][++dfn]=dep,pos[0][dfn]=u;
        }
    }
    void Init(){
        for(int i=0;i<=LOG;i++)for(int j=1;j<=2*n;j++)ST[i][j]=0;
        dfn=pnt[1]=0;
        dfs0(1,1);
        for(int i=0;i<=20&&(1<<i)<=dfn;i++)
            for(int j=(1<<i);j<(1<<i+1)&&j<=dfn;j++)Log[j]=i;
        for(int i=1;i<=20;i++)
            for(int j=1;j+(1<<i)<=dfn+1;j++){
                if(ST[i-1][j]<ST[i-1][j+(1<<i-1)])ST[i][j]=ST[i-1][j],pos[i][j]=pos[i-1][j];
                else ST[i][j]=ST[i-1][j+(1<<i-1)],pos[i][j]=pos[i-1][j+(1<<i-1)];
            }
    }
    int LCA(int u,int v){
        if(u==v)return u;
        int x=num[u],y=num[v];
        if(x>y)swap(x,y);
        y++;
        int t=Log[y-x];
        if(ST[t][x]<ST[t][y-(1<<t)])return pos[t][x];else return pos[t][y-(1<<t)];
    }
}