模板集合

Resonate · 2024-05-23 19:57:13 · 个人记录

目标

• [x] 建立
• [ ] 算法基础
• [ ] 搜索
• [ ] 动态规划
• [ ] 字符串
• [ ] 数学
• [ ] 数据结构
• [ ] 图论
• [ ] 计算几何
• [ ] 杂项
• [ ] 专题

字符串

前缀函数与 KMP 算法

P3375 【模板】KMP

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b;
int n,m;
int nxt[1111111];
signed main()
{
    cin>>a>>b;
    n=a.size(),m=b.size();
    a=" "+a;
    b=" "+b;
    nxt[1]=0;
    for(int i=2,j=0;i<=m;i++)
    {
        while(j and b[i]!=b[j+1])
        {
            j=nxt[j];
        }
        if(b[i]==b[j+1])
        {
            j++;
        }
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++)
    {
        while(j and a[i]!=b[j+1])
        {
            j=nxt[j];
        }
        if(a[i]==b[j+1])
        {
            j++;
        }
        if(j==m)
        {
            cout<<i-j+1<<endl;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<nxt[i]<<" ";
    }
}

数据结构

线段树

P3372 【模板】线段树 1

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[111111];
struct node
{
    int l, r, s, lz;
} tr[444444];
void updata(int root)
{
    tr[root].l = tr[root * 2].l;
    tr[root].r = tr[root * 2 + 1].r;
    tr[root].s = tr[root * 2].s + tr[root * 2 + 1].s;
}
void pushdown(int root)
{
    tr[root * 2].lz += tr[root].lz;
    tr[root * 2 + 1].lz += tr[root].lz;
    tr[root * 2].s += tr[root].lz * (tr[root * 2].r - tr[root * 2].l + 1);
    tr[root * 2 + 1].s += tr[root].lz * (tr[root * 2 + 1].r - tr[root * 2 + 1].l + 1);
    tr[root].lz = 0;
}
void build(int root, int l, int r)
{
    if (l == r)
    {
        tr[root].l = l;
        tr[root].r = r;
        tr[root].s = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(root * 2, l, mid);
    build(root * 2 + 1, mid + 1, r);
    updata(root);
}
int search(int root, int l, int r)
{
    if (l == tr[root].l and r == tr[root].r)
    {
        return tr[root].s;
    }
    int s = 0;
    if (tr[root].lz != 0)
    {
        pushdown(root);
    }
    if (r <= tr[root * 2].r)
    {
        s += search(root * 2, l, r);
    }
    else if (l >= tr[root * 2 + 1].l)
    {
        s += search(root * 2 + 1, l, r);
    }
    else
    {
        s += search(root * 2, l, tr[root * 2].r) + search(root * 2 + 1, tr[root * 2 + 1].l, r);
    }
    return s;
}
void change2(int root, int l, int r, int x)
{
    if (l <= tr[root].l and r >= tr[root].r)
    {
        tr[root].lz += x;
        tr[root].s += x * (tr[root].r - tr[root].l + 1);
        return;
    }
    if (tr[root].lz != 0)
    {
        pushdown(root);
    }
    if (r <= tr[root * 2].r)
    {
        change2(root * 2, l, r, x);
    }
    else if (l >= tr[root * 2 + 1].l)
    {
        change2(root * 2 + 1, l, r, x);
    }
    else
    {
        change2(root * 2, l, tr[root * 2].r, x);
        change2(root * 2 + 1, tr[root * 2 + 1].l, r, x);
    }
    updata(root);
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1, op, x, y, z; i <= m; i++)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y >> z;
            change2(1, x, y, z);
        }
        else
        {
            cin >> x >> y;
            cout << search(1, x, y) << endl;
        }
    }
}

二叉搜索树 & 平衡树

P3369 【模板】普通平衡树

旋转 treap

#include<bits/stdc++.h>
#define int long long
using namespace std;
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void print(int x)
{
    if (x<0)
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
const int M=100000000;
struct node{
    int l,r,val,sz,w,cnt;
}tr[222222];
void change(int root)
{
    if(root)
    {
        tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+tr[root].cnt;
    }
}
void zig(int &root)
{
    int tx=tr[root].l;
    tr[root].l=tr[tx].r;
    tr[tx].r=root;
    change(root);
    change(tx);
    root=tx;
}
void zag(int &root)
{
    int tx=tr[root].r;
    tr[root].r=tr[tx].l;
    tr[tx].l=root;
    change(root);
    change(tx);
    root=tx;
}
void tupdate(int &root)
{
    if(tr[root].w<tr[tr[root].l].w)
    {
        zig(root);
    }
    else if(tr[root].w<tr[tr[root].r].w)
    {
        zag(root);
    }
    change(root);
}
int c;
void tinsert(int &root,int x)
{
    if(!root)
    {
        root=++c;
        tr[root].val=x;
        tr[root].cnt++;
        tr[root].sz++;
        tr[root].w=rand()%M;
        return;
    }
    if(x<tr[root].val)
    {
        tinsert(tr[root].l,x);
    }
    else if(x>tr[root].val)
    {
        tinsert(tr[root].r,x);
    }
    else if(x==tr[root].val)
    {
        tr[root].cnt++;
        tr[root].sz++;
    }
    if(root)
    {
        tupdate(root);
    }
}
void tdelete(int &root,int x)
{
    if(tr[root].val==x)
    {
        if(tr[root].cnt>1)
        {
            tr[root].cnt--;
            tr[root].sz--;
        }
        else
        {
            if(!tr[root].l or !tr[root].r)
            {
                root=tr[root].l+tr[root].r;
            }
            else
            {
                if(tr[tr[root].l].w<tr[root].w)
                {
                    zig(root);
                }
                else
                {
                    zag(root);
                }
                tdelete(root,x);
            }
        }
    }
    else if(x<tr[root].val)
    {
        tdelete(tr[root].l,x);
    }
    else if(x>tr[root].val)
    {
        tdelete(tr[root].r,x);
    }
    change(root);
}
int root;
bool tfind(int x)
{
    int rt=root;
    while(rt!=0 and tr[rt].val!=x)
    {
        if(x<tr[rt].val)
        {
            rt=tr[rt].l;
        }
        else
        {
            rt=tr[rt].r;
        }
    }
    return rt;
}
int tx_min(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x<=tr[rt].val)
        {
            rt=tr[rt].l;
        }
        else
        {
            ans+=tr[tr[rt].l].sz+tr[rt].cnt;
            rt=tr[rt].r;
        }
    }
    return ans;
}
int tx_rank(int x)
{
    int rt=root;
    while(rt!=0)
    {
        if(tr[tr[rt].l].sz<x)
        {
            if(tr[tr[rt].l].sz+tr[rt].cnt>=x)
            {
                return rt;
            }
            else
            {
                x-=(tr[tr[rt].l].sz+tr[rt].cnt);
                rt=tr[rt].r;
            }
        }
        else
        {
            rt=tr[rt].l;
        }
    }
    return 0;
}
int tx_q(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x>tr[rt].val)
        {
            ans=rt;
            rt=tr[rt].r;
        }
        else
        {
            rt=tr[rt].l;
        }
    }
    return ans;
}
int tx_h(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x<tr[rt].val)
        {
            ans=rt;
            rt=tr[rt].l;
        }
        else
        {
            rt=tr[rt].r;
        }
    }
    return ans;
}
int n;
signed main()
{
    srand(time(0));
    // cin>>n;
    n=read();
    for(int i=1,op,x;i<=n;i++)
    {
        // cin>>op>>x;
        op=read();
        x=read();
        if(op==1)
        {
            tinsert(root,x);
        }
        else if(op==2)
        {
            if(!tfind(x))
            {
                continue;
            }
            tdelete(root,x);
        }
        else if(op==3)
        {
            // cout<<tx_min(x)+1<<'\n';
            print(tx_min(x)+1);
            puts("");
        }
        else if(op==4)
        {
            // cout<<tr[tx_rank(x)].val<<'\n';
            print(tr[tx_rank(x)].val);
            puts("");
        }
        else if(op==5)
        {
            // cout<<tr[tx_q(x)].val<<'\n';
            print(tr[tx_q(x)].val);
            puts("");
        }
        else
        {
            // cout<<tr[tx_h(x)].val<<'\n';
            print(tr[tx_h(x)].val);
            puts("");
        }
    }
}

无旋 treap

#include<bits/stdc++.h>
#define int long long
using namespace std;
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void print(int x)
{
    if (x<0)
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
mt19937 rd;
const int M=100000000;
struct node{
    int l,r,v,sz,w;
}tr[2222222];
void tupdata(int root)
{
    if(root)
    {
        tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+1;
    }
}
void tsplit(int root,int v,int &x,int &y)
{
    if(!root)
    {
        x=y=0;
        return;
    }
    if(tr[root].v<=v)
    {
        x=root;
        tsplit(tr[root].r,v,tr[x].r,y);
    }
    else
    {
        y=root;
        tsplit(tr[root].l,v,x,tr[y].l);
    }
    tupdata(root);
}
void tmerge(int &root,int x,int y)
{
    if(!x or !y)
    {
        root=x+y;
    }
    else if(tr[x].w>=tr[y].w)
    {
        root=x;
        tmerge(tr[root].r,tr[x].r,y);
    }
    else
    {
        root=y;
        tmerge(tr[root].l,x,tr[y].l);
    }
    tupdata(root);
}
int root,c;
void tinsert(int &root,int v)
{
    int w,x,y,z;
    w=x=y=0;
    z=++c;
    tr[z]={0,0,v,1,rd()%M};
    tsplit(root,v,x,y);
    tmerge(w,x,z);
    tmerge(root,w,y);
}
void tdelete(int v)
{
    int x,y,z,w,p;
    x=y=z=w=p=0;
    tsplit(root,v,x,y);
    tsplit(x,v-1,z,w);
    tmerge(w,tr[w].l,tr[w].r);
    tupdata(x);
    tmerge(p,z,w);
    tmerge(root,p,y);
}
int tx_min(int v)
{
    int x,y;
    x=y=0;
    tsplit(root,v-1,x,y);
    int ans=tr[x].sz+1;
    tmerge(root,x,y);
    return ans;
}
int tx_rank(int root,int x)
{
    if(x<=tr[tr[root].l].sz)
    {
        return tx_rank(tr[root].l,x);
    }
    if(x==tr[tr[root].l].sz+1)
    {
        return tr[root].v;
    }
    return tx_rank(tr[root].r,x-tr[tr[root].l].sz-1);
}
int tx_q(int v)//
{
    int x,y;
    x=y=0;
    tsplit(root,v-1,x,y);
    int ans=tx_rank(x,tr[x].sz);
    tmerge(root,x,y);
    return ans;
}
int tx_h(int v)//
{
    int x,y;
    x=y=0;
    tsplit(root,v,x,y);
    int ans=tx_rank(y,1);
    tmerge(root,x,y);
    return ans;
}
int n;
signed main()
{
    srand(time(0));
    n=read();
    for(int i=1,op,x;i<=n;i++)
    {
        op=read();
        x=read();
        if(op==1)
        {
            tinsert(root,x);
        }
        else if(op==2)
        {
            tdelete(x);
        }
        else if(op==3)
        {
            print(tx_min(x));
            puts("");
        }
        else if(op==4)
        {
            print(tx_rank(root,x));
            puts("");
        }
        else if(op==5)
        {
            print(tx_q(x));
            puts("");
        }
        else
        {
            print(tx_h(x));
            puts("");
        }
    }
}

AVL 树

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
int root;
struct node{
    int l,r,v,h,cnt,sz;
}tr[111111];
void zag(int &root)
{
    int tx=tr[root].r;
    tr[root].r=tr[tx].l;
    tr[tx].l=root;
    tr[root].h=max(tr[tr[root].l].h,tr[tr[root].r].h)+1;
    tr[tx].h=max(tr[tr[tx].l].h,tr[tr[tx].r].h)+1;
    tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+tr[root].cnt;
    tr[tx].sz=tr[tr[tx].l].sz+tr[tr[tx].r].sz+tr[tx].cnt;
    root=tx;
}
void zig(int &root)
{
    int tx=tr[root].l;
    tr[root].l=tr[tx].r;
    tr[tx].r=root;
    tr[root].h=max(tr[tr[root].l].h,tr[tr[root].r].h)+1;
    tr[tx].h=max(tr[tr[tx].l].h,tr[tr[tx].r].h)+1;
    tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+tr[root].cnt;
    tr[tx].sz=tr[tr[tx].l].sz+tr[tr[tx].r].sz+tr[tx].cnt;
    root=tx;
}
void zagzig(int &root)
{
    zag(tr[root].l);
    zig(root);
}
void zigzag(int &root)
{
    zig(tr[root].r);
    zag(root);
}
int c;
void tinsert(int &root,int x)
{
    if(!root)
    {
        root=++c;
        tr[root].v=x;
        tr[root].cnt=tr[root].sz=tr[root].h=1;
        return;
    }
    if(x<tr[root].v)
    {
        tinsert(tr[root].l,x);
        if(tr[tr[root].l].h==tr[tr[root].r].h+2)
        {
            if(x<tr[tr[root].l].v)
            {
                zig(root);
            }
            else
            {
                zagzig(root);
            }
        }
    }
    else if(x>tr[root].v)
    {
        tinsert(tr[root].r,x);
        if(tr[tr[root].l].h==tr[tr[root].r].h-2)
        {
            if(x>tr[tr[root].r].v)
            {
                zag(root);
            }
            else
            {
                zigzag(root);
            }
        }
    }
    else
    {
        tr[root].sz++;
        tr[root].cnt++;
    }
    tr[root].h=max(tr[tr[root].l].h,tr[tr[root].r].h)+1;
    tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+tr[root].cnt;
}
void tupdata(int &root)
{
    if(tr[tr[root].l].h==tr[tr[root].r].h+2)
    {
        int x=tr[root].l;
        if(tr[tr[x].l].h==tr[tr[root].r].h+1)
        {
            zig(root);
        }
        else
        {
            zagzig(root);
        }
    }
    else if(tr[tr[root].l].h==tr[tr[root].r].h-2)
    {
        int x=tr[root].r;
        if(tr[tr[x].r].h==tr[tr[root].l].h+1)
        {
            zag(root);
        }
        else
        {
            zigzag(root);
        }
    }
    tr[root].h=max(tr[tr[root].l].h,tr[tr[root].r].h)+1;
    tr[root].sz=tr[tr[root].l].sz+tr[tr[root].r].sz+tr[root].cnt;
}
pii tdelete(int &root,int x)
{
    int tx,ty;
    if(tr[root].v==x or (tr[root].v<x and tr[root].r==0))
    {
        if(tr[root].v==x and tr[root].cnt>1)
        {
            tr[root].sz--;
            tr[root].cnt--;
        }
        else if(tr[root].l==0 or tr[root].r==0)
        {
            tx=tr[root].v;
            ty=tr[root].cnt;
            root=tr[root].l+tr[root].r;
            return {tx,ty};
        }
        else
        {
            pii tt=tdelete(tr[root].l,x);
            tr[root].v=tt.first;
            tr[root].cnt=tt.second;
        }
    }
    else
    {
        if(x<tr[root].v)
        {
            pii tt=tdelete(tr[root].l,x);
            tx=tt.first;
            ty=tt.second;
        }
        else
        {
            pii tt=tdelete(tr[root].r,x);
            tx=tt.first;
            ty=tt.second;
        }
    }
    if(root!=0)
    {
        tupdata(root);
    }
    return {tx,ty};
}
bool tfind(int x)
{
    int rt=root;
    while(rt!=0 and tr[rt].v!=x)
    {
        if(x<tr[rt].v)
        {
            rt=tr[rt].l;
        }
        else
        {
            rt=tr[rt].r;
        }
    }
    return rt;
}
int tx_min(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x<=tr[rt].v)
        {
            rt=tr[rt].l;
        }
        else
        {
            ans+=tr[tr[rt].l].sz+tr[rt].cnt;
            rt=tr[rt].r;
        }
    }
    return ans;
}
int tx_rank(int x)
{
    int rt=root;
    while(rt!=0)
    {
        if(tr[tr[rt].l].sz<x)
        {
            if(tr[tr[rt].l].sz+tr[rt].cnt>=x)
            {
                return rt;
            }
            else
            {
                x-=(tr[tr[rt].l].sz+tr[rt].cnt);
                rt=tr[rt].r;
            }
        }
        else
        {
            rt=tr[rt].l;
        }
    }
    return 0;
}
int tx_q(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x>tr[rt].v)
        {
            ans=rt;
            rt=tr[rt].r;
        }
        else
        {
            rt=tr[rt].l;
        }
    }
    return ans;
}
int tx_h(int x)
{
    int rt=root,ans=0;
    while(rt!=0)
    {
        if(x<tr[rt].v)
        {
            ans=rt;
            rt=tr[rt].l;
        }
        else
        {
            rt=tr[rt].r;
        }
    }
    return ans;
}
int n;
signed main()
{
    cin>>n;
    for(int i=1,op,x;i<=n;i++)
    {
        cin>>op>>x;
        if(op==1)
        {
            tinsert(root,x);
        }
        else if(op==2)
        {
            if(!tfind(x))
            {
                continue;
            }
            tdelete(root,x);
        }
        else if(op==3)
        {
            cout<<tx_min(x)+1<<'\n';
        }
        else if(op==4)
        {
            cout<<tr[tx_rank(x)].v<<'\n';
        }
        else if(op==5)
        {
            cout<<tr[tx_q(x)].v<<'\n';
        }
        else
        {
            cout<<tr[tx_h(x)].v<<'\n';
        }
    }
}

splay

#include<bits/stdc++.h>
#define int long long
using namespace std;
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void print(int x)
{
    if (x<0)
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
struct node{
    int son[2],fa,v,cnt,sz;
}tr[2222222];
void tupdata(int root)
{
    tr[root].sz=tr[tr[root].son[0]].sz+tr[tr[root].son[1]].sz+tr[root].cnt;
}
void trotate(int x)
{
    int y=tr[x].fa,z=tr[y].fa;
    int op=(tr[y].son[1]==x);
    tr[z].son[tr[z].son[1]==y]=x;
    tr[x].fa=z;
    tr[y].son[op]=tr[x].son[op^1];
    tr[tr[x].son[op^1]].fa=y;
    tr[x].son[op^1]=y;
    tr[y].fa=x;
    tupdata(y);
    tupdata(x);
}
int root,c;
void tsplay(int x,int f)
{
    while(tr[x].fa!=f)
    {
        int y=tr[x].fa,z=tr[y].fa;
        if(z!=f)
        {
            (tr[y].son[0]==x)^(tr[z].son[0]==y)?trotate(x):trotate(y);
        }
        trotate(x);
    }
    if(!f)
    {
        root=x;
    }
}
void tinsert(int x)
{
    int rt=root,p=0;
    while(tr[rt].v!=x and rt)
    {
        p=rt;
        rt=tr[rt].son[x>tr[rt].v];
    }
    if(rt)
    {
        tr[rt].cnt++;
    }
    else
    {
        rt=++c;
        tr[p].son[x>tr[p].v]=rt;
        tr[rt].fa=p;
        tr[rt].v=x;
        tr[rt].cnt=tr[rt].sz=1;
    }
    tsplay(rt,0);
}
void tfind(int x)
{
    int rt=root;
    while(tr[rt].son[x>tr[rt].v] and x!=tr[rt].v)
    {
        rt=tr[rt].son[x>tr[rt].v];
    }
    tsplay(rt,0);
}
int tx_q(int x)
{
    tfind(x);
    int rt=root;
    if(tr[rt].v<x)
    {
        return rt;
    }
    rt=tr[rt].son[0];
    while(tr[rt].son[1])
    {
        rt=tr[rt].son[1];
    }
    tsplay(rt,0);
    return rt;
}
int tx_h(int x)
{
    tfind(x);
    int rt=root;
    if(tr[rt].v>x)
    {
        return rt;
    }
    rt=tr[rt].son[1];
    while(tr[rt].son[0])
    {
        rt=tr[rt].son[0];
    }
    tsplay(rt,0);
    return rt;
}
void tdelete(int x)
{
    int y=tx_q(x),z=tx_h(x);
    tsplay(y,0);
    tsplay(z,y);
    int t=tr[z].son[0];
    if(tr[t].sz>1)
    {
        tr[t].cnt--;
        tsplay(t,0);
    }
    else
    {
        tr[z].son[0]=0;
        tsplay(z,0);
    }
}
int tx_rank(int x)
{
    tinsert(x);
    int ans=tr[tr[root].son[0]].sz;
    tdelete(x);
    return ans;
}
int tx_min(int x)
{
    int rt=root;
    while(rt)
    {
        if(tr[tr[rt].son[0]].sz<x)
        {
            if(tr[tr[rt].son[0]].sz+tr[rt].cnt>=x)
            {
                break;
            }
            else
            {
                x-=tr[tr[rt].son[0]].sz+tr[rt].cnt;
                rt=tr[rt].son[1];
            }
        }
        else
        {
            rt=tr[rt].son[0];
        }
    }
    tsplay(rt,0);
    return rt;
}
int n;
signed main()
{
    tinsert(1145141919);
    tinsert(-1145141919);
    n=read();
    for(int i=1,op,x;i<=n;i++)
    {
        op=read();
        x=read();
        if(op==1)
        {
            tinsert(x);
        }
        else if(op==2)
        {
            tdelete(x);
        }
        else if(op==3)
        {
            print(tx_rank(x));
            puts("");
        }
        else if(op==4)
        {
            print(tr[tx_min(x+1)].v);
            puts("");
        }
        else if(op==5)
        {
            print(tr[tx_q(x)].v);
            puts("");
        }
        else
        {
            print(tr[tx_h(x)].v);
            puts("");
        }
    }
}

可持久化数据结构

可持久化线段树

P3919 【模板】可持久化线段树 1（可持久化数组）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1111111;
int rts;
int a[N],tr[N<<5],ls[N<<5],rs[N<<5],r[N<<5];
void build(int &rt,int l,int rr)
{
    if(!rt)
    {
        rt=++rts;
    }
    if(l==rr)
    {
        tr[rt]=a[l];
        return;
    }
    int mid=(l+rr)/2;
    build(ls[rt],l,mid);
    build(rs[rt],mid+1,rr);
}
void change(int rt1,int &rt2,int l,int rr,int x,int y)
{
    if(!rt2)
    {
        rt2=++rts;
    }
    if(l==rr)
    {
        tr[rt2]=y;
        return;
    }
    int mid=(l+rr)/2;
    if(x<=mid)
    {
        rs[rt2]=rs[rt1];
        change(ls[rt1],ls[rt2],l,mid,x,y);
    }
    else
    {
        ls[rt2]=ls[rt1];
        change(rs[rt1],rs[rt2],mid+1,rr,x,y);
    }
}
int sum(int rt,int l,int rr,int x)
{
    if(l==rr)
    {
        return tr[rt];
    }
    int mid=(l+rr)/2;
    if(x<=mid)
    {
        return sum(ls[rt],l,mid,x);
    }
    else
    {
        return sum(rs[rt],mid+1,rr,x);
    }
}
int n,m;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(r[0],1,n);
    for(int i=1,v,op,loc,val;i<=m;i++)
    {
        cin>>v>>op>>loc;
        if(op==1)
        {
            cin>>val;
            change(r[v],r[i],1,n,loc,val);
        }
        else
        {
            int s=sum(r[v],1,n,loc);
            cout<<s<<'\n';
            r[i]=++rts;
            ls[r[i]]=ls[r[v]];
            rs[r[i]]=rs[r[v]];
        }
    }
}

P3834 【模板】可持久化线段树 2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=222222;
int rts;
int a[N],ls[N<<5],rs[N<<5],r[N<<5],s[N<<5];
void change(int rt1,int &rt2,int l,int rr,int x)
{
    if(!rt2)
    {
        rt2=++rts;
    }
    s[rt2]=s[rt1]+1;
    if(l==rr)
    {
        return;
    }
    int mid=(l+rr)/2;
    if(x<=mid)
    {
        rs[rt2]=rs[rt1];
        change(ls[rt1],ls[rt2],l,mid,x);
    }
    else
    {
        ls[rt2]=ls[rt1];
        change(rs[rt1],rs[rt2],mid+1,rr,x);
    }
}
int sum(int rt1,int rt2,int l,int rr,int x)
{
    if(l==rr)
    {
        return l;
    }
    int ss=s[ls[rt2]]-s[ls[rt1]],mid=(l+rr)/2;
    if(x<=ss)
    {
        return sum(ls[rt1],ls[rt2],l,mid,x);
    }
    else
    {
        return sum(rs[rt1],rs[rt2],mid+1,rr,x-ss);
    }
}
int n,m;
int b[N];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int c=unique(b+1,b+1+n)-b;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+c,a[i])-b;
    }
    for(int i=1;i<=n;i++)
    {
        change(r[i-1],r[i],1,n,a[i]);
    }
    for(int i=1,l,rr,x;i<=n;i++)
    {
        cin>>l>>rr>>x;
        cout<<b[sum(r[l-1],r[rr],1,n,x)]<<'\n';
    }
}

数学

数论

最大公约数

扩展欧几里得算法

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a; 
    }
    int ret=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*x;
    return ret;
}

Stein 算法

int gcd(int a,int b)
{
    if(a<b)
    {
        swap(a,b);
    }
    if(!b)
    {
        return a;
    }
    if(!(a&1) and !(b&1))
    {
        return gcd(a>>1,b>>1)<<1;
    }
    else if((a&1) and !(b&1))
    {
        return gcd(a,b>>1);
    }
    else if(!(a&1) and (b&1))
    {
        return gcd(a>>1,b);
    }
    else
    {
        return gcd(a-b,b);
    }
}

筛法

埃筛

vector<int> prime;
bool is_prime[N];
void Eratosthenes(int n)
{
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<=n;++i)
    {
        is_prime[i]=1;
    }
    for(int i=2;i<=n;++i)
    {
        if(is_prime[i])
        {
            prime.push_back(i);
            if((long long)i*i>n)
            {
                continue;
            }
            for(int j=i*i;j<=n;j+=i)
            {
                is_prime[j]=0;
            }
        }
    }
}

埃筛+bitset优化

vector<int> prime;
bitset<N>is_prime;
void Eratosthenes(int n)
{
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<=n;++i)
    {
        is_prime[i]=1;
    }
    for(int i=2;i<=n;++i)
    {
        if(is_prime[i])
        {
            prime.push_back(i);
            if((long long)i*i>n)
            {
                continue;
            }
            for(int j=i*i;j<=n;j+=i)
            {
                is_prime[j]=0;
            }
        }
    }
}

欧拉筛

vector<int> pri;
bool not_prime[N];
void pre(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!not_prime[i])
        {
            pri.push_back(i);
        }
        for(int pri_j:pri)
        {
            if(i*pri_j>n)
            {
                break;
            }
            not_prime[i*pri_j]=1;
            if(!(i%pri_j))
            {
                break;
            }
        }
    }
}

欧拉筛+bitset优化

vector<int> pri;
bitset<N>not_prime;
void pre(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!not_prime[i])
        {
            pri.push_back(i);
        }
        for(int pri_j:pri)
        {
            if(i*pri_j>n)
            {
                break;
            }
            not_prime[i*pri_j]=1;
            if(!(i%pri_j))
            {
                break;
            }
        }
    }
}

筛法求欧拉函数

vector<int>pri;
bool not_prime[N];
int phi[N];
void pre(int n)
{
    phi[1]=1;
    not_prime[0]=not_prime[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!not_prime[i])
        {
            pri.push_back(i);
            phi[i]=i-1;
        }
        for(auto j:pri)
        {
            if(i*j>n)
            {
                break;
            }
            not_prime[i*j]=1;
            if(i%j==0)
            {
                phi[i*j]=phi[i]*j;
                break;
            }
            phi[i*j]=phi[i]*phi[j];
        }
    }
}

欧拉函数

int euler_phi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%2==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)
            {
                n/=i;
            }
        }
    }
    if(n>1)
    {
        ans=ans/n*(n-1);
    }
    return ans;
}

卢卡斯定理

int lcs(int n,int m)
{
    if(m==0)
    {
        return 1;
    }
    return (c(n%M,m%M)*lcs(n/M,m/M))%M;
}

组合数学

排列组合

C(n,m)

int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%M;
        }
        b>>=1;
        a=a*a%M;
    }
    return ans;
}
int c(int n,int m)
{
    if(n<m)
    {
        return 0;
    }
    int a=1,b=1;
    for(int i=n-m+1;i<=n;i++)
    {
        a=a*i%M;
    }
    for(int i=2;i<=m;i++)
    {
        b=b*i%M;
    }
    return a*qpow(b,M-2)%M;
}

杂项

优化

指令集优化

#define __AVX__ 1
#define __AVX2__ 1
#define __SSE__ 1
#define __SSE2__ 1
#define __SSE2_MATH__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSSE3__ 1

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#include <immintrin.h>
#include <emmintrin.h>

快读

整型

char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

字符串

bool check(char a) { return (a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z'); }
inline string readstr() {
    string s;
    char aa = getchar();
    while (!check(aa)) aa = getchar();
    while (check(aa)) s += aa, aa = getchar();
    return s;
}

快输

整型

inline void print(int x)
{
    if (x<0)
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}

图论

最小生成树

P3366 【模板】最小生成树

#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[222222],cnt=2;
struct node{
    int from,to,nxt,val;
}e[522222];
void add_edge(int x,int y,int z)
{
    e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].val=z,e[cnt].from=x;
}
bool cmp(node a,node b)
{
    return a.val<b.val;
}
int f[222222],w[222222];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int n,m;
signed main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        w[i]=1;
    }
    for(int i=1,x,y,z;i<=m;i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
    }
    int s=0;
    sort(e,e+cnt,cmp);
    for(int i=3;i<=cnt;i++)
    {
        int x=e[i].from,y=e[i].to;
        x=find(x),y=find(y);
        if(x==y)
        {
            continue;
        }
        f[x]=y;
        w[y]+=w[x];
        s+=e[i].val;
    }
    if(w[find(1)]!=n)
    {
        cout<<"orz";
    }
    else
    {
        cout<<s;
    }
}

最短路

Floyd 算法

B3647 【模板】Floyd

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
int n,m,x,y,z;
int dis[105][105];
signed main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j)
            {
                dis[i][j]=0;
            }
            else
            {
                dis[i][j]=inf;
            }
        }
    }
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        dis[x][y]=z;
        dis[y][x]=z;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            cout<<dis[i][j]<<" ";
        }
        cout<<endl;
    }
}

Bellman–Ford 算法

队列优化：SPFA

P3385 【模板】负环

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
void init();
void work();
signed main()
{
    cin>>T;
    while(T--)
    {
        init();
        work();
    }
}
int head[222222];
struct node{
    int to,nxt,v;
}e[222222];
queue<int>q;
bitset<222222>vis;
int cnt1=2;
void add_edge(int x,int y,int z)
{
    e[++cnt1].to=y,e[cnt1].nxt=head[x],head[x]=cnt1,e[cnt1].v=z;
}
int n,m;
int dis[222222];
int cnt[222222];
void init()
{
    cnt1=2;
    while(!q.empty())
    {
        q.pop();
    }
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    vis.reset();
}
void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    vis[s]=1,dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].v)
            {
                dis[y]=dis[x]+e[i].v;
                cnt[y]=cnt[x]+1;
                if(cnt[y]>=n)
                {
                    cout<<"YES";
                    return;
                }
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    cout<<"NO";
}
void work()
{
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
        if(z>=0)
        {
            add_edge(y,x,z);
        }
    }
    spfa(1);
    puts("");
}

队列优化：SPFA(SLF优化)

int head[222222];
struct node{
    int to,nxt,v;
}e[222222];
deque<int>q;
bitset<222222>vis;
int cnt=2;
void add_edge(int x,int y,int z)
{
    e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].v=z;
}
int dis[222222];
void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    vis[s]=1,dis[s]=0;
    q.push_back(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].v)
            {
                dis[y]=dis[x]+e[i].v;
                if(!vis[y])
                {
                    vis[y]=1;
                    if(!q.empty() and dis[q.front()]>dis[y])
                    {
                        q.push_front(y);
                    }
                    else
                    {
                        q.push_back(y);
                    }
                }
            }
        }
    }
}

Dijkstra 算法

P3371 【模板】单源最短路径（弱化版）

P4779 【模板】单源最短路径（标准版）

#include <bits/stdc++.h>
#define int long long
using namespace std;
int head[222222], cnt = 2;
struct node {
    int to, nxt, val;
} e[522222];
void add_edge(int x, int y, int z) { e[++cnt].to = y, e[cnt].nxt = head[x], head[x] = cnt, e[cnt].val = z; }
//
int dis[222222];
void dij(int xx);
void dfs(int x, int dis);
//
int n, m, s;
signed main() {
    memset(head,-1,sizeof(head));
    cin >> n >> m>>s;
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        add_edge(x, y, z);
    }
    dij(s);
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
}
// dij
struct node1 {
    int dis, to;
    bool operator>(const node1 &T) const { return dis > T.dis; }
};
bitset<222222> vis;
priority_queue<node1, vector<node1>, greater<node1> > q;
void dij(int xx) {
    memset(dis, 0x3f, sizeof(dis));
    q.push({ 0, xx });
    vis.reset();
    dis[xx] = 0;
    while (!q.empty()) {
        int x = q.top().to;
        q.pop();
        if (vis[x]) {
            continue;
        }
        vis[x] = 1;
        for (int i = head[x]; i!=-1; i = e[i].nxt) {
            int y = e[i].to;
            if(vis[y])
            {
                continue;
            }
            if (dis[y] > dis[x] + e[i].val) {
                dis[y] = dis[x] + e[i].val;
                q.push({dis[y] ,y});
            }
        }
    }
}

连通性相关

割点和桥

P3388 【模板】割点（割顶）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[222222],cnt=2;
struct node{
    int to,nxt;
}e[222222];
void add_edge(int x,int y)
{
    e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;
}
int ans;
bitset<222222>flag;
int low[222222],dfn[222222],tot;
bitset<222222>vis;
void tarjan(int x,int fa)
{
    vis[x]=1;
    dfn[x]=low[x]=++tot;
    int son=0;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!vis[y])
        {
            son++;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(fa!=x and low[y]>=dfn[x] and !flag[x])
            {
                flag[x]=1;
                ans++;
            }
        }
        else if(y!=fa)
        {
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(fa==x and son>=2 and !flag[x])
    {
        flag[x]=1;
        ans++;
    }
}
int n,m;
signed main()
{
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            tot=0;
            tarjan(i,i);
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    {
        if(flag[i])
        {
            cout<<i<<" ";
        }
    }
}

割边

int ans;
bitset<222222>flag;
int low[222222],dfn[222222],tot;
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tot;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!dfn[y])
        {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
            {
                flag[x]=1;
                ans++;
            }
        }
        else if(y!=fa and dfn[y]<dfn[x])
        {
            low[x]=min(low[x],dfn[y]);
        }
    }
}

双联通分量

P8435 【模板】点双连通分量

#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[6666666],cnt=2;
struct node{
    int to,nxt;
}e[6666666];
void add_edge(int x,int y)
{
    e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;
}
int tot;
int dfn[6666666],low[6666666];
stack<int>q;
int ans;
vector<int>s[6666666];
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tot;
    int son=0;
    q.push(x);
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!dfn[y])
        {
            ++son;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                ans++;
                while(!q.empty() and q.top()!=y)
                {
                    s[ans].push_back(q.top());
                    q.pop();
                }
                s[ans].push_back(x);
                s[ans].push_back(y);
                q.pop();
            }
        }
        else if(y!=fa)
        {
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(son==0 and fa==0)
    {
        s[++ans].push_back(x);
    }
}
int n,m;
signed main()
{
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tot=0;
            tarjan(i,0);
        }
    }
    cout<<ans<<'\n';
    for(int i=1;i<=ans;i++)
    {
        cout<<s[i].size()<<" ";
        for(auto j:s[i])
        {
            cout<<j<<" ";
        }
        cout<<'\n';
    }
}

P8436 【模板】边双连通分量

本文分类参照OI Wiki~