LCA

Tarjan代码：

#include
    
     using namespace std;#define RG registerinline int read(){    int sum = 0;    char c = getchar();    while(c<'0' || c>'9')        c = getchar();    while(c>='0' && c<='9')        sum = sum*10+c-'0', c = getchar();    return sum;}const int N = 500010;struct node{    int to, next;}g[N*2];struct nod{    int to, next, num;}a[N*2];int fa[N], last[N], gl, bj[N], n, m, s, ans[N], al, la[N];int find(int x){    if(fa[x] == x)        return x;    return fa[x] = find(fa[x]);}void add(int x, int y){    g[++gl].to = y;    g[gl].next = last[x];    last[x] = gl;}void add2(int x, int y, int i){    a[++al].to = y;    a[al].next = la[x];    a[al].num = i;    la[x] = al;}void tarjan(int x, int lat){    fa[x] = x;    bj[x] = 1;    for(int i = last[x]; i; i = g[i].next)    {        int to = g[i].to;        if(to == lat) continue;        tarjan(to, x);        fa[to] = x;    }    for(int i = la[x]; i; i=a[i].next)        if(bj[a[i].to])            ans[a[i].num] = find(a[i].to);    return ;}void write(int x){    if(x)    {        write(x/10);        putchar((x%10+'0'));    }    return ;}int main(){    n = read(), m = read(), s = read();    for(RG int i = 1; i < n; i++)    {        int x=read(),y=read();        add(x,y);add(y,x);    }    for(RG int i = 1; i <= m; i++)    {        int x=read(),y=read();        add2(x, y, i), add2(y, x, i);    }    tarjan(s, 0);    for(RG int i = 1; i <= m; i++)        write(ans[i]), putchar('\n');    return 0;}
    

倍增代码：

#include
    
     using namespace std;#define RG registerinline int read(){    int sum = 0;    char c = getchar();    while(c<'0' || c>'9')        c = getchar();    while(c>='0' && c<='9')        sum = sum*10+c-'0', c = getchar();    return sum;}void write(int x){    if(x)    {        write(x/10);        putchar((x%10+'0'));    }    return ;}const int N = 500010;struct node{    int to, next;}g[N*2];int last[N], gl;void add(int x, int y){    g[++gl] = (node){y, last[x]};    last[x] = gl;}int anc[N][21], fa[N], deep[N];void work(int x){    anc[x][0] = fa[x];    for(int i=1; (1<
     
      <= deep[x]; i++)        anc[x][i] = anc[anc[x][i-1]][i-1];    for(int i = last[x]; i; i = g[i].next)        if(fa[x] != g[i].to)        {            fa[g[i].to] = x;            deep[g[i].to] = deep[x]+1;            work(g[i].to);        }    return ;}int lca(int x, int y){    if(deep[x] < deep[y])        swap(x, y); //x比y深    for(int i = 20; i >= 0; i--)        if(deep[y] <= deep[x]-(1<
      
       = 0; i--)    {        if(anc[x][i]!=anc[y][i])        {            x=anc[x][i];            y=anc[y][i];        }    }    return anc[x][0];//最后一次肯定跳一个点}int main(){    int n = read(), m = read(), s = read();    for(RG int i = 1; i < n; i++)    {        int x=read(),y=read();        add(x,y);add(y,x);    }    work(s);    for(RG int i = 1; i <= m; i++)    {        int x=read(), y=read();        write(lca(x,y));        putchar('\n');    }    return 0;}
      
     
    

【模板】单源最短路径Dijkstra+堆优化

#include
    
     using namespace std;const int N = 100010;const int M = 200010;struct Edge{    int to, next, w;}g[M];int last[N], gl;void add(int x, int y, int z){    g[++gl] = (Edge){y, last[x], z};    last[x] = gl;}int dis[N];struct node{    int dist, num;    bool operator < (node z)    const    {        return dist > z.dist;    }};priority_queue
     
       q;bool bj[N];int main(){    int n, m, s;    scanf("%d%d%d", &n, &m, &s);    for(int i = 1; i <= m; i++)    {        int x, y, z;        scanf("%d%d%d", &x, &y, &z);        add(x, y, z);    }    memset(dis, 127, sizeof(dis));    dis[s] = 0;    q.push((node){0, s});    while(!q.empty())    {        while(!q.empty() && bj[q.top().num])            q.pop();        if(q.empty()) break;        int u = q.top().num;        bj[u] = 1;        q.pop();        for(int i = last[u]; i; i = g[i].next)        {            int v = g[i].to;            if(dis[v] > dis[u]+g[i].w)            {                dis[v] = dis[u]+g[i].w;                q.push((node){dis[v], v});            }        }    }    for(int i = 1; i <= n; i++)        printf("%d ", dis[i]);    printf("\n");    return 0;}
     
    

【模板】树链剖分

#include
    
     #define LL long longconst int N = 1e5+10;using namespace std;inline void Swap(int &x, int &y){int z = x^y; y ^= z; x ^= z;return ;}inline int gi(){int sum = 0, f = 1;char c = getchar();while(c!='-' && (c < '0' || c > '9'))c = getchar();if(c == '-') f = -1, c = getchar();while(c>='0' && c<='9') sum = sum*10+c-'0', c = getchar();return sum*f;}int n, m, r, p, w[N];struct tree{    int to, next;}g[N*2];int last[N], gl;inline void add(int x, int y){g[++gl] = (tree){y, last[x]};last[x] = gl;return;}int dep[N], siz[N], top[N], id[N], cnt, son[N], fa[N], t[N];void dfs1(int x, int f, int depth){    dep[x] = depth;    fa[x] = f;    siz[x] = 1;    int MAX = 0;    for(int i = last[x]; i; i = g[i].next)    {        int to = g[i].to;        if(to != f)        {            dfs1(to, x, depth+1);            siz[x] += siz[to];            if(siz[to] > MAX) MAX = siz[to], son[x] = to;        }    }    return ;}void dfs2(int x, int topf){    id[x] = ++cnt;    top[x] = topf;    t[cnt] = w[x];    if(!son[x]) return ;    dfs2(son[x], topf);    for(int i = last[x]; i; i = g[i].next)    {        int to = g[i].to;        if(to != fa[x] && to != son[x])            dfs2(to, to);    }    return ;}struct node{    int v, lazy;}st[N*4];inline void pushdown(int l, int r, int rt){    if(st[rt].lazy)    {        int lazy = st[rt].lazy, mid = (l+r) >> 1, ls = rt<<1, rs = rt<<1|1;        st[rt].lazy = 0;        st[ls].lazy += lazy;        st[ls].lazy %= p;        st[ls].v += lazy*(mid-l+1);        st[ls].v %= p;        st[rs].lazy += lazy;        st[ls].lazy %= p;        st[rs].v += lazy*(r-mid);        st[rs].v %= p;    }    return ;}void build(int l, int r, int rt){    if(l == r)    {        st[rt].v = t[l]%p;        return ;    }    int mid = (l+r) >> 1;    build(l, mid, rt<<1);    build(mid+1, r, rt<<1|1);    st[rt].v = (st[rt<<1].v + st[rt<<1|1].v)%p;    return ;}void update(int l, int r, int L, int R, int rt, int k){    if(L <= l && r <= R)    {        st[rt].lazy += k;        st[rt].lazy %= p;        st[rt].v += k*(r-l+1);        st[rt].v %= p;        return ;    }    int mid = (l+r) >> 1;    pushdown(l, r, rt);    if(L <= mid)        update(l, mid, L, R, rt<<1, k);    if(R > mid)        update(mid+1, r, L, R, rt<<1|1, k);    st[rt].v = (st[rt<<1].v + st[rt<<1|1].v)%p;    return ;}int query(int l, int r, int L, int R, int rt){    if(L <= l && r <= R)        return st[rt].v;    int ans = 0, mid = (l+r) >> 1;    pushdown(l, r, rt);    if(L <= mid)        ans = query(l, mid, L, R, rt<<1);    if(R > mid)        ans += query(mid+1, r, L, R, rt<<1|1);    return ans%p;}inline void upway(int x, int y, int z){    z %= p;    while(top[x] != top[y])    {        if(dep[top[x]] < dep[top[y]]) Swap(x, y);        update(1, n, id[top[x]], id[x], 1, z);        x = fa[top[x]];    }    if(dep[x] > dep[y]) Swap(x, y);    update(1, n, id[x], id[y], 1, z);    return ;}inline int qway(int x, int y){    int ans = 0;    while(top[x] != top[y])    {        if(dep[top[x]] < dep[top[y]]) Swap(x, y);        ans += query(1, n, id[top[x]], id[x], 1);        ans %= p;        x = fa[top[x]];    }    if(dep[x] > dep[y]) Swap(x, y);    ans += query(1, n, id[x], id[y], 1);    return ans%p;}inline void upsub(int x, int k){    update(1, n, id[x], id[x]+siz[x]-1, 1, k);    return ;}inline int qsub(int x){    return query(1, n, id[x], id[x]+siz[x]-1, 1);}int main(){    n = gi(); m = gi(); r = gi(); p = gi();    for(int i = 1; i <= n; i++) w[i] = gi()%p;    for(int i = 1; i < n; i++)    {        int x = gi(), y = gi();        add(x, y); add(y, x);    }    dfs1(r, 0, 1);    dfs2(r, r);    build(1, n, 1);    for(int i = 1; i <= m; i++)    {        int k = gi();        if(k == 1)        {            int x = gi(), y = gi(), z = gi();            upway(x, y, z);        }        else        if(k == 2)        {            int x = gi(), y = gi();            printf("%d\n", qway(x, y));        }        else        if(k == 3)        {            int x = gi(), y = gi();            upsub(x, y);        }        else        {            int x = gi();            printf("%d\n", qsub(x));        }    }    return 0;}
    

Splay模板

文艺平衡树

// luogu-judger-enable-o2#include
    
     using namespace std;const int N = 100010;struct Splay {    int v, ch[2], f, s;    bool o;}t[N];void up(int x) {    t[x].s = t[t[x].ch[0]].s + t[t[x].ch[1]].s + 1;}inline void rotate(int x) {    int y = t[x].f, z = t[y].f, k = (t[y].ch[1] == x);    t[z].ch[(t[z].ch[1]==y)] = x; t[x].f = z;    t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].f = y;    t[x].ch[k^1] = y; t[y].f = x;       up(y);    return ;}int rt;inline void pushdown(int x) {    if (t[x].o) {        swap(t[x].ch[0], t[x].ch[1]);        t[x].o = 0;        t[t[x].ch[0]].o ^= 1;        t[t[x].ch[1]].o ^= 1;    }    return ;}inline int K(int z) {    int x = rt;    while (1) {        pushdown(x);        int l = t[x].ch[0];        if (t[l].s+1 < z) {            x = t[x].ch[1];            z -= (t[l].s+1);        }        else {            if (t[l].s >= z)                x = l;            else return x;        }       }}inline void splay(int x, int goal) {    while (t[x].f != goal) {        int y = t[x].f, z = t[y].f;        if (z != goal)            (t[z].ch[1] == y) == (t[y].ch[1] == x) ? rotate(y) : rotate(x);        rotate(x);    }    up(x);    if (!goal) rt = x;      return ;}int cnt;void insert(int k) {    int x = rt, f = 0;    while (x)        f = x, x = t[x].ch[(t[x].v < k)];    t[++cnt].f = f; t[cnt].v = k;    t[f].ch[t[f].v < k] = cnt;    splay(cnt, 0);    return ;}void reverse(int L, int R) {    int l = K(L), r = K(R+2);    splay(l, 0); splay(r, l);    t[t[t[rt].ch[1]].ch[0]].o ^= 1;    return ;}int n;void write(int x) {    pushdown(x);    if (t[x].ch[0]) write(t[x].ch[0]);    if (t[x].v > 1 && t[x].v < n+2) printf("%d ", t[x].v-1);    if (t[x].ch[1]) write(t[x].ch[1]);    return ;}int main() {    int m;    scanf("%d%d", &n, &m);    for (int i = 1; i <= n+2; i++) insert(i);    for (int i = 1; i <= m; i++) {        int l, r;        scanf("%d%d", &l, &r);        reverse(l, r);    }    write(rt);    return 0;}
    

平衡树

// luogu-judger-enable-o2#include
    
     #define N 500010const int INF = 2147483647;using namespace std;inline int gi() {    register int x=0,t=1;    char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-'){t=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}    return x*t;}int r, tot;struct node {    int ch[2], f, cnt, v, s;}t[N];inline void up(int x) {    t[x].s = t[t[x].ch[0]].s + t[t[x].ch[1]].s + t[x].cnt;    return ;}inline void rotate(int x) {    int y = t[x].f; int z = t[y].f, k = (t[y].ch[1] == x);    t[z].ch[t[z].ch[1] == y] = x; t[x].f = z;    t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].f = y;    t[x].ch[k^1] = y; t[y].f = x;    up(y);    return ;}void splay(int x, int goal) {    while (t[x].f != goal) {        int y = t[x].f; int z = t[y].f;        if (z != goal)            if ((t[y].ch[1] == x) == (t[z].ch[1] == y)) rotate(x); else rotate(y);        rotate(x);    }    up(x);    if (!goal) r = x;    return ;}void insert(int x) {    int rt = r, f = 0;    while (rt && t[rt].v != x) {        f = rt;        rt = t[rt].ch[t[rt].v
     
       x) || (!bj && t[rt].v < x)) return rt;    rt = t[rt].ch[bj];    bj ^= 1;    while (t[rt].ch[bj]) rt = t[rt].ch[bj];    return rt;}void del(int x) {    int a = Next(x, 0), b = Next(x, 1);    splay(a, 0); splay(b, a);    int c = t[b].ch[0];    if (t[c].cnt > 1) {        t[c].cnt--;        splay(c, 0);    }    else t[b].ch[0] = 0;    return ;}int K(int x) {    int rt = r;    while (1) {        int l = t[rt].ch[0];        if (t[l].s + t[rt].cnt < x) {            x -= (t[rt].cnt + t[l].s);            rt = t[rt].ch[1];        }        else             if (t[l].s >= x)                rt = l;            else return t[rt].v;    }}int main() {    insert(INF); insert(-INF);    int T = gi();    while (T--) {        int k = gi();        if (k == 1) insert(gi());        else if (k == 2) del(gi());        else if (k == 3) {            find(gi());            printf("%d\n", t[t[r].ch[0]].s);        }        else if (k == 4)            printf("%d\n", K(gi()+1));        else if (k == 5) printf("%d\n", t[Next(gi(), 0)].v);        else printf("%d\n", t[Next(gi(), 1)].v);    }    return 0;}
     
    

KMP模板

#include
    
     using namespace std;inline int gi() {    char ch=getchar(); int x=0,q=0;    while(ch<'0'||ch>'9') q=ch=='-'?1:q,ch=getchar();    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return q?-x:x;}const int N = 1000010;char s1[N], s2[N];int l1, l2, nxt[N];void kmp() {    int j = 0;    for (int i = 1; i <= l1; i++) {        while (j && s1[i-1] != s2[j]) j = nxt[j];        if (s1[i-1] == s2[j]) j++;        if (j == l2)            printf("%d\n", i-l2+1), j = nxt[j];    }    return ;}int main() {    cin>>s1>>s2;    l1 = strlen(s1); l2 = strlen(s2);    nxt[1] = 0;    for (int i = 2; i <= l2; i++) {        int j = nxt[i-1];        while (j && s2[i-1] != s2[j])            j = nxt[j];        if (s2[i-1] == s2[j]) j++;        nxt[i] = j;    }    kmp();    for (int i = 1; i <= l2; i++)        printf("%d ", nxt[i]);    printf("\n");    return 0;}
    

二分图匹配(匈牙利算法)模板

#include
    
     using namespace std;inline int gi() {    int f = 1, s = 0;    char c = getchar();    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') f = -1, c = getchar();    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();    return f == 1 ? s : -s;}const int N = 1000010;struct node {    int to, next;}g[N];int match[1010], gl, last[1010], used[1010];inline int pp(int x) {    for (int i = last[x]; i; i = g[i].next) {        int v = g[i].to;        if (used[v]) continue;        used[v] = 1;        if (!match[v] || pp(match[v])) {            match[v] = x;            return 1;        }    }    return 0;}void add(int x, int y) {    g[++gl] = (node) {y, last[x]};    last[x] = gl;}int main() {    int n = gi(), m = gi(), e = gi();    for (int i = 1; i <= e; i++) {        int x = gi(), y = gi();        if (x <= n && y <= m) add(x, y);    }    int ans = 0;    for (int i = 1; i <= n; i++) {        memset(used, 0, sizeof(used));        ans += pp(i);    }    printf("%d\n", ans);    return 0;}
    

求区间第K大(主席树模板)

#include
    
     using namespace std;inline int gi() {    int f = 1, s = 0;    char c = getchar();    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') f = -1, c = getchar();    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();    return f == 1 ? s : -s;}const int N = 200010;struct node {    int v, id;    bool operator < (node z) const {        return v < z.v;    }}a[N];int b[N], cnt;struct tree {    int lc, rc, v;}t[N*20];int root[N], ans[N];void update(int l, int r, int pos, int &now) {    t[++cnt] = t[now];    now = cnt;    t[now].v++;    if (l == r) return ;    int mid = (l + r) >> 1;    if (pos <= mid)        update(l, mid, pos, t[now].lc);    else update(mid+1, r, pos, t[now].rc);    return ;}int query(int l, int r, int rt1, int rt2, int k) {    if (l == r) return l;    int s = t[t[rt2].lc].v - t[t[rt1].lc].v, mid = (l + r) >> 1;    if (s >= k)        return query(l, mid, t[rt1].lc, t[rt2].lc, k);    else return query(mid+1, r, t[rt1].rc, t[rt2].rc, k - s);}int main() {    int n = gi(), m = gi();    for (int i = 1; i <= n; i++) {        a[i].v = gi(); a[i].id = i;    }    sort(a+1, a+1+n);    int v = 1;    b[a[1].id] = v; ans[v] = a[1].v;    for (int i = 2; i <= n; i++) {        if (a[i].v != a[i-1].v) v++;        b[a[i].id] = v; ans[v] = a[i].v;    }    for (int i = 1; i <= n; i++) {        root[i] = root[i-1];        update(1, n, b[i], root[i]);    }    while (m--) {        int l = gi(), r = gi(), k = gi();        printf("%d\n", ans[query(1, n, root[l-1], root[r], k)]);    }    return 0;}
    

【模板】三维偏序（陌上花开）

//cdq套cdq#include
    
     using namespace std;const int N = 100010;struct node {    int a, b, c, id;    bool flag;    bool operator < (node z) const {        return a < z.a || (a == z.a && b < z.b) || (a == z.a && b == z.b && c < z.c);    }}s[N], b[N], c[N];int ans[N], d[N];void merge2(int l, int r) {    if (l == r) return;    int mid = (l + r) >> 1, cnt = 0;//cnt记前面和当前点满足条件的个数    merge2(l, mid); merge2(mid+1, r);    for (int i = l, j = mid+1, k = l; k <= r; k++) {        if ((j > r || b[j].c >= b[i].c) && i <= mid) {            c[k] =  b[i++];            cnt += c[k].flag;//是前半部分的点就+1        }        else {            c[k] = b[j++];            if (!c[k].flag) ans[c[k].id] += cnt;//在后半部分表明当前点的b大于前半部分的任意一个点的b        }    }    for (int i = l; i <= r; i++)        b[i] = c[i];    return ;}void merge(int l, int r) {    if (l == r) return ;    int mid = (l + r) >> 1;    merge(l, mid); merge(mid+1, r);    for (int i = l, j = mid+1, k = l; k <= r; k++) {        if ((j > r || s[j].b >= s[i].b) && i <= mid) {            b[k] = s[i++];            b[k].flag = 1;//当前点为前半部分        }        else {            b[k] = s[j++];            b[k].flag = 0;        }    }    for (int i = l; i <= r; i++) s[i] = b[i];    merge2(l, r);    return ;}int main() {    int n, k;    scanf("%d%d", &n, &k);    for (int i = 1; i <= n; i++) {        scanf("%d%d%d", &s[i].a, &s[i].b, &s[i].c);        s[i].id = i;    }    sort(s+1, s+1+n);    for (int i = n-1; i >= 1; i--)         if (s[i].a == s[i+1].a && s[i].b == s[i+1].b && s[i].c == s[i+1].c) ans[s[i].id] = ans[s[i+1].id]+1;//对于完全相等的,i > j 的点对在cdq分治中已经求了,所以只用求 i < j 的点对个数    merge(1, n);    for (int i = 1; i <= n; i++) d[ans[i]]++;    for (int i = 0; i < n; i++) printf("%d\n", d[i]);    return 0;}
    

//cdq+树状数组#include
    
     using namespace std;const int N = 100010;struct node {    int a, b, c, cnt, id;    bool operator <(const node &z) const {        return a < z.a || (a == z.a && b < z.b) || (a == z.a && b == z.b && c < z.c);    }}s[N], tmp[N];int t[200010], n, k;#define lowbit(x) (x&(-x))void add(int x, int z) {    while (x <= k) {        t[x] += z;        x += lowbit(x);    }    return ;}int sum(int x) {    int sm = 0;    while (x) {        sm += t[x];        x -= lowbit(x);    }    return sm;}int ans[N], cnt[N];void cdq(int l, int r) {    if (l == r) return ;    int mid = (l + r) >> 1;    cdq(l, mid); cdq(mid+1, r);    for (int i = l, j = mid+1, k = l; k <= r; k++) {        if (i <= mid && (j > r || s[i].b <= s[j].b)) {            add(s[i].c, s[i].cnt);            tmp[k] = s[i++];        }        else {            ans[s[j].id] += sum(s[j].c);            tmp[k] = s[j++];        }    }    for (int i = l; i <= mid; i++) add(s[i].c, -s[i].cnt);    for (int i = l; i <= r; i++) s[i] = tmp[i];    return ;}int main() {    scanf("%d%d", &n, &k);    for (int i = 1; i <= n; i++) scanf("%d%d%d", &s[i].a, &s[i].b, &s[i].c), s[i].id = i;    sort(s+1, s+1+n);    int z = 1, num = 0;    for (int i = 1; i <= n; i++) {        int z = i;        while (s[z].a == s[z+1].a && s[z].b == s[z+1].b && s[z].c == s[z+1].c)            z++;        s[i].cnt = z-i+1;        s[++num] = s[i];        i = z;    }    cdq(1, num);    for (int i = 1; i <= num; i++) cnt[ans[s[i].id]+s[i].cnt-1]+=s[i].cnt;    for (int i = 0; i < n; i++) printf("%d\n", cnt[i]);    return 0;}
    

Link-cut tree模板

#include
    
     #define LL long long#define RG registerconst int N = 300010;using namespace std;inline int gi() {    RG int x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();    return f ? -x : x;}struct node {    int v, s, fa, ch[2];    bool rev;}t[N];int S[N], top;void putrev(int x) {    swap(t[x].ch[0], t[x].ch[1]);    t[x].rev ^= 1;    return ;}#define pushup(x) (t[x].s = (t[x].v^t[t[x].ch[0]].s^t[t[x].ch[1]].s))void pushdown(int x) {    if (t[x].rev) {        if (t[x].ch[0]) putrev(t[x].ch[0]);        if (t[x].ch[1]) putrev(t[x].ch[1]);        t[x].rev = 0;    }    return ;}#define get(x) (t[t[x].fa].ch[1]==x)bool isroot(int x) {    return (t[t[x].fa].ch[0] != x) && (t[t[x].fa].ch[1] != x);}void rotate(int x) {    int k = get(x), y = t[x].fa, z = t[y].fa;    if (!isroot(y)) t[z].ch[get(y)] = x;    t[x].fa = z;    t[t[x].ch[k^1]].fa = y, t[y].ch[k] = t[x].ch[k^1];    t[y].fa = x, t[x].ch[k^1] = y;    pushup(y);    return ;}void splay(int x) {    S[top = 1] = x;    for (RG int i = x; !isroot(i); i = t[i].fa) S[++top] = t[i].fa;    for (RG int i = top; i; i--) pushdown(S[i]);    while (!isroot(x)) {        int y = t[x].fa;        if (!isroot(y))            (get(x) ^ get(y)) ? rotate(x) : rotate(y);        rotate(x);    }    pushup(x);    return ;}void access(int x) {    for (int y = 0; x; y = x, x = t[x].fa)        splay(x), t[x].ch[1] = y, pushup(x);    return ;}void makeroot(int x) {    access(x); splay(x);putrev(x);    return ;}inline int findroot(int x) {    access(x); splay(x);    while (t[x].ch[0]) pushdown(x), x = t[x].ch[0];    return x;}void link(int x, int y) {    makeroot(x);    if (findroot(y) == x) return ;    t[x].fa = y;    return ;}void split(int x, int y) {    makeroot(x), access(y), splay(y);    return ;}void cut(int x, int y) {    makeroot(x);    if (findroot(y) == x && t[x].fa == y && !t[x].ch[1])        t[x].fa = t[y].ch[0] = 0, pushup(y);    return ;}int main() {    int n = gi(), T = gi();    for (RG int i = 1; i <= n; i++) t[i].v = gi();    while (T--) {        int op = gi(), x = gi(), y = gi();        if (!op) {            split(x, y);            printf("%d\n", t[y].s);        }        else if (op == 1) link(x, y);        else if (op == 2) cut(x, y);        else {            access(x); splay(x); t[x].v = y; pushup(x);        }    }    return 0;}
    

左偏树模板

#include
    
     #define LL long long#define RG registerusing namespace std;inline int gi() {    RG int x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();    return f ? -x : x;}const int N = 100010;int fa[N], ch[N][2], a[N], dis[N];inline int merge(int x, int y) {    if (!x || !y) return x+y;    if (a[x] > a[y] || (a[x] == a[y] && x > y))        swap(x, y);    ch[x][1] = merge(ch[x][1], y);    fa[ch[x][1]] = x;    if (dis[ch[x][1]] > dis[ch[x][0]]) swap(ch[x][1], ch[x][0]);    dis[x] = dis[ch[x][1]]+1;    return x;}inline int get(int x) {    while (fa[x]) x = fa[x];    return x;}bool flag[N];inline void del(int x) {    x = get(x);    printf("%d\n", a[x]);    flag[x] = 1;    fa[ch[x][0]] = fa[ch[x][1]] = 0;    merge(ch[x][0], ch[x][1]);}int main() {    //freopen(".in", "r", stdin);    //freopen(".out", "w", stdout);    int n = gi(), m = gi();    dis[0] = -1;    for (int i = 1; i <= n; i++) a[i] = gi();    while (m--) {        int opt = gi();        if (opt == 1) {            int x = gi(), y = gi();            if (flag[x] || flag[y]) continue;            x = get(x); y = get(y);            if (x == y) continue;            merge(x, y);        }        else {            int x = gi();            if (flag[x]) printf("-1\n");            else del(x);        }    }    return 0;}
    

【模板】杜教筛（Sum）

\(g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor \frac{n}{i} \rfloor)\)

其中\(g = f*1\)

#include
    
     #define LL long long#define RG registerusing namespace std;inline int gi() {    RG int x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();    return f ? -x : x;}const int N = 6000000;int p[N], tot;LL phi[N+1], mu[N+1];bool zs[N+1];void init() {    mu[1] = 1; phi[1] = 1;    for (int i = 2; i <= N; i++) {        if (!zs[i]) {            p[++tot] = i;            mu[i] = -1;            phi[i] = i-1;        }        for (int j = 1; j <= tot && p[j]*i <= N; j++) {            zs[p[j]*i] = 1;            if (!(i%p[j])) {                phi[i*p[j]] = phi[i]*p[j];                break;            }            mu[i*p[j]] = -mu[i];            phi[i*p[j]] = phi[i]*(p[j]-1);        }    }    for (int i = 2; i <= N; i++)        mu[i] += mu[i-1], phi[i] += phi[i-1];    return ;}map
     
       M1, M2;LL getphi(int x) {    if (x <= N) return phi[x];    if (M1[x]) return M1[x];    LL S = (x+1)*1ll*x/2;    for (int l = 2, r; l <= x; l = r+1) {        r = (x/(x/l));        S -= getphi(x/l)*(r-l+1);    }    return M1[x] = S; }LL getmu(int x) {    if (x <= N) return mu[x];    if (M2[x]) return M2[x];    LL S = 1;    for (int l = 2, r; l <= x; l = r+1) {        r = (x/(x/l));        S -= getmu(x/l)*(r-l+1);    }    return M2[x] = S;}int main() {    //freopen(".in", "r", stdin);    //freopen(".out", "w", stdout);    int t = gi();    init();    while (t--) {        int n = gi();        printf("%lld %lld\n", getphi(n), getmu(n));    }    return 0;}
     
    

【模板】扩展中国剩余定理（EXCRT）

#include
    
     #define LL long long#define RG registerusing namespace std;inline int gi() {    RG int x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();    return f ? -x : x;}const int N = 100010;LL M[N], C[N];LL gcd(LL x, LL y) {    return !y ? x : gcd(y, x%y);}void exgcd(LL a, LL b, LL &x, LL &y) {    if (!b) {x = 1, y = 0; return ;}    exgcd(b, a%b, y, x);    y -= a/b*x;    return ;}inline long long multi(long long x,long long y,long long mod) {     long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);     return tmp<0 ? tmp+mod : tmp; }LL inv(LL a, LL b) {    LL x, y;    exgcd(a, b, x, y);    while (x < 0) x += b;    return x;}int main() {    int n = gi();    for (int i = 1; i <= n; i++) scanf("%lld%lld", &M[i], &C[i]);    for (int i = 2; i <= n; i++) {        LL M1 = M[i-1], M2 = M[i], C1 = C[i-1], C2 = C[i], d = gcd(M1, M2);        if ((C2-C1)%d) {            puts("-1");            return 0;        }        M[i] = M1/d * M2;        C[i] = (multi(multi(inv(M1/d, M2/d)%(M2/d), (C2-C1)/d, (M2/d)), M1, M[i]) + C1) % M[i];        C[i] = (C[i] + M[i]) % M[i];    }    printf("%lld\n", C[n]);    return 0;}
    

【模板】扩展卢卡斯

#include
    
     #define LL long long#define RG registerLL ksm(LL x, LL y, LL M) {    LL s = 1;    while (y) {        if (y&1) s = s*x%M;        x = x*x%M;        y >>= 1;    }    return s;}using namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}void exgcd(LL a, LL b, LL &x, LL &y) {    if (!b) {x = 1, y = 0; return ;}    exgcd(b, a%b, y, x);    y -= a/b*x;    return ;}LL inv(LL a, LL M) {    if (!a) return 0;    LL x, y; exgcd(a, M, x, y);    if (x < 0) x += M;    x %= M;    return x;}LL calc(LL n, LL pi, LL pk) {    if (!n) return 1;    LL ans = 1;    for (LL i = 2; i <= pk; i++)        if (i%pi) ans = ans*i%pk;    ans = ksm(ans, n/pk, pk);    for (LL i = 2; i <= n%pk; i++)        if (i%pi) ans = ans*i%pk;    return ans*calc(n/pi, pi, pk)%pk;}LL C(LL n, LL m, LL Mod, LL pi, LL pk) {    if (m > n) return 0;    LL a = calc(n, pi, pk), b = calc(m, pi, pk), c = calc(n-m, pi, pk), k = 0;    for (LL i = n; i; i /= pi) k += i/pi;    for (LL i = m; i; i /= pi) k -= i/pi;    for (LL i = n-m; i; i /= pi) k-= i/pi;    return a*inv(b, pk)%pk*inv(c, pk)%pk*ksm(pi, k, pk)%pk;}LL lucas(LL n, LL m, LL Mod) {    LL ans = 0, x = Mod;    for (LL i = 2; i <= x; i++)        if (!(x%i)) {            LL pk = 1;            while (!(x%i)) pk *= i, x /= i;            ans = (ans+C(n, m, Mod, i, pk)*(Mod/pk)%Mod*inv(Mod/pk, pk)) % Mod;        }    return ans;}int main() {    //freopen(".in", "r", stdin);    //freopen(".out", "w", stdout);    LL n, m, Mod;    read(n); read(m); read(Mod);    write(lucas(n, m, Mod));    return 0;}
      
     
    

【模板】网络最大流（Dinic+当前弧优化）

// luogu-judger-enable-o2#include
    
     #define LL long long#define RG registerusing namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}const int M = 200010, N = 10010, inf = 2147483647;int n, m, s, t;struct node {    int to, nxt, w;}g[M];int last[N], gl = 1, cur[N];void add(int x, int y, int z) {    g[++gl] = (node) {y, last[x], z};    last[x] = gl;}queue
       
         q;int dep[N];bool bfs() {    q.push(s);    memset(dep, 0, sizeof(dep));    dep[s] = 1;    while (!q.empty()) {        int u = q.front(); q.pop();        for (int i = last[u]; i; i = g[i].nxt) {            int v = g[i].to;            if (g[i].w && !dep[v])                dep[v] = dep[u]+1, q.push(v);        }    }    return dep[t] ? 1 : 0;}int dfs(int u, int d) {    if (u == t) return d;    for (int &i = cur[u]; i; i = g[i].nxt) {        int v = g[i].to;        if (dep[v] == dep[u]+1 && g[i].w) {            int di = dfs(v, min(d, g[i].w));            if (di) {                g[i].w -= di;                g[i^1].w += di;                return di;            }        }    }    return 0;}int main() {    read(n); read(m); read(s); read(t);    for (int i = 1; i <= m; i++) {        int u, v, w; read(u); read(v); read(w);        add(u, v, w); add(v, u, 0);    }    int ans = 0;    while (bfs()) {        for (int i = 1; i <= n; i++)            cur[i] = last[i];        while (int d = dfs(s, inf))            ans += d;    }    printf("%d\n", ans);    return 0;}
       
      
     
    

【模板】最小费用最大流

#include
    
     #define LL long long#define RG registerusing namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}const int N = 5010, M = 100010, inf = 2147483647;int n, m, s, t;struct node {    int to, nxt, w, v;}g[M];int last[N], gl = 1;void add(int x, int y, int w, int v) {    g[++gl] = (node) {y, last[x], w, v};    last[x] = gl;}int pre[N], from[N], dis[N];bool vis[N];queue
       
         q;bool spfa() {    for (int i = 1; i <= n; i++) dis[i] = inf;    memset(vis, 0, sizeof(vis));    q.push(s);    dis[s] = 0;     while (!q.empty()) {        int u = q.front(); q.pop();        vis[u] = 0;        for (int i = last[u]; i; i = g[i].nxt) {            int v = g[i].to;            if (g[i].w && dis[v] > dis[u]+g[i].v) {                dis[v] = dis[u]+g[i].v;                from[v] = i; pre[v] = u;                if (!vis[v]) {                    vis[v] = 1;                    q.push(v);                }            }        }    }    return !(dis[t] == inf);}int main() {    read(n); read(m); read(s); read(t);    for (int i = 1; i <= m; i++) {        int u, v, w, va; read(u), read(v), read(w), read(va);        add(u, v, w, va), add(v, u, 0, -va);    }    int flow = 0, cost = 0;    while (spfa()) {        int di = inf;        for (int i = t; i != s; i = pre[i])            di = min(di, g[from[i]].w);        flow += di; cost += di*dis[t];        for (int i = t; i != s; i = pre[i])            g[from[i]].w -= di, g[from[i]^1].w += di;    }    printf("%d %d\n", flow, cost);    return 0;}
       
      
     
    

AC自动机

#include
    
     #define LL long long#define RG registerusing namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}struct Tree {    int fail, end;    int s[26];}t[1000000];int cnt = 0;char s[1000010];void insert() {    int len = strlen(s), now = 0;    for (int i = 0; i < len; i++) {        if (!t[now].s[s[i]-'a'])            t[now].s[s[i]-'a'] = ++cnt;        now = t[now].s[s[i]-'a'];    }    t[now].end++;    return ;}queue
       
         q;   void get_fail() {    for (int i = 0; i < 26; i++)        if (t[0].s[i]) {            t[t[0].s[i]].fail = 0;            q.push(t[0].s[i]);        }    while (!q.empty()) {        int x = q.front(); q.pop();        for (int i = 0; i < 26; i++)            if (t[x].s[i]) {                t[t[x].s[i]].fail = t[t[x].fail].s[i];                q.push(t[x].s[i]);            }            else t[x].s[i] = t[t[x].fail].s[i];    }}int query() {    int len = strlen(s), now = 0, ans = 0;    for (int i = 0; i < len; i++) {        now = t[now].s[s[i]-'a'];        for (int j = now; j && t[j].end != -1; j = t[j].fail) {            ans += t[j].end;            t[j].end = -1;        }    }    return ans;}int main() {    int n;    read(n);    for (int i = 1; i <= n; i++) {        scanf("%s", s);        insert();    }    get_fail();    scanf("%s", s);    write(query());    return 0;}