模板太多了，写啥更新啥，顺便当自己的存档

码风很乱，见谅

---

 

单点修改树状数组

#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg register#define l() i&-iusing namespace std;int n,m,a[500010],tree[500010],c,x,y;inline int lowbit(int x){    return x&(-x);}inline void updata(int x,int k){    for(int i=x;i<=n;i+=lowbit(x))        tree[i]+=k;}inline int query(int x){    int ans=0;    for(int i=x;i;i-=lowbit(x))        ans+=tree[i];    return ans;}inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}int main(){    n=read();    m=read();    for(int i=1;i<=n;i++)    {        a[i]=read();        updata(i,a[i]);    }    for(int i=1;i<=m;i++)    {        c=read();        if(c==1)        {            x=read();            y=read();            updata(x,y);        }        else        {            x=read();            y=read();            cout<
        
         <
        
       
      
     

 

区间修改树状数组

#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg register#define l() i&-iusing namespace std;int n,x,y,z,k,tree[500010],a,m,last=0;inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}inline int lowbit(int x){    return x&(-x);}inline void add(int x,int k){    for(int i=x;i<=n;i+=lowbit(i))        tree[i]+=k;}inline long long query(int x){    long long ans=0;    for(int i=x;i;i-=lowbit(i))        ans+=tree[i];    return ans;}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)    {        a=read();        add(i,a-last);        last=a;    }    for(int i=1;i<=m;i++)    {        cin>>x;        if(x==1)        {            cin>>y>>z>>k;            add(y,k);            add(z+1,-k);        }        if(x==2)        {            cin>>y;            cout<
        
         <
        
       
      
     

可持久化线段树（主席树）

#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg registerusing namespace std;inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}int n,q,m,T[200001],tot,a[200001],b[200001];struct cym{    int l,r,val;}tree[8000001];inline int bulid(int l,int r)// 建树操作 {    int bj=++tot;    tree[bj].val=0;    int mid=(l+r)>>1;    if(l>r)    {        tree[bj].l=bulid(l,mid);        tree[bj].r=bulid(mid+1,r);    }    return bj;}inline int change(int pre,int l,int r,int zone)// 修改 {    int bj=++tot;    tree[bj].l=tree[pre].l;    tree[bj].r=tree[pre].r;    tree[bj].val=tree[pre].val+1;    int mid=(l+r)>>1;    if(l
        
         >1;    if(x>=k)        return cx(tree[from].l,tree[to].l,l,mid,k);    else        return cx(tree[from].r,tree[to].r,mid+1,r,k-x);}int main(){    n=read(),q=read();    for(rg int i=1;i<=n;i++)    {        a[i]=read();        b[i]=a[i];    }    sort(b+1,b+n+1);// 排序     m=unique(b+1,b+n+1)-b-1;// 看一共有多少个不重复的元素     T[0]=bulid(1,m);// 把最后一个点建在 主席树数组T[0]的位置      for(rg int i=1;i<=n;i++)    {        int t=lower_bound(b+1,b+m+1,a[i])-b;// 第一个比a[i] 大的树的位置         T[i]=change(T[i-1],1,m,t);    }    for(rg int i=1;i<=q;i++)    {        int l=read(),r=read(),k=read();        int anss=cx(T[l-1],T[r],1,m,k);        printf("%d\n",b[anss]);    }}
        
       
      
     

 ST表

#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN=1e6+10;inline int read(){    char c=getchar();int x=0,f=1;    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;}int Max[MAXN][21];int Query(int l,int r){    int k=log2(r-l+1);     return max(Max[l][k],Max[r-(1<
       
      
     

 Kruskal

/*            Kruskal            并查集            结构体存边             luogu P3366 模板 */#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg registerusing namespace std;int n,m,ans,now_e,now_v,cnt;inline int read()// 读入优化 {    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}struct Node{    int start,end,power;    // start为起始点    // end 为终点     // power 为权值 }edge[2000010];// 存边 int fa[6666];//并查集 int cmp(Node a,Node b){    return a.power
       
      
     

 Prim

/*            Prim            链式前向星存图 */#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg register#define inf 0x7ffffffusing namespace std;int head[5005],dis[5005],cnt,n,m,tot,now=1,ans;bool vis[5005];inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}struct Node{    int v,w,next;}e[400010];inline void add(int u,int v,int w){    e[++cnt].v=v;    e[cnt].w=w;    e[cnt].next=head[u];    head[u]=cnt;}inline int prim(){    for(rg int i=2;i<=n;i++)        dis[i]=inf;    for(rg int i=head[1];i;i=e[i].next)    {        dis[e[i].v]=min(dis[e[i].v],e[i].w);    }    while(++tot
        
         dis[i])            {                minn=dis[i];                now=i;            }         }          ans+=minn;         //枚举now的连边，更新dis          for(rg int i=head[now];i;i=e[i].next)         {            rg int v=e[i].v;            if(dis[v]>e[i].w&&!vis[v])            {                dis[v]=e[i].w;                }             }              }      return ans;}int main(){    n=read(),m=read();    for(rg int i=1,u,v,w;i<=m;i++)    {        u=read(),v=read(),w=read();        add(u,v,w),add(v,u,w);//无向图     }    printf("%d",prim());}
        
       
      
     

稀疏图：Kruskal

稠密图：Prim

 Dijkstra

/*            Dijkstra            朴素：O(n^2)            堆优化：O((n+m)log^2n)            不可以处理负边权的图            luogu P4799 模板 */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long long#define rg registerusing namespace std;inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}struct Node{    int v,w,next;}e[500010];int head[100010],dis[100010],cnt;bool vis[100010];int n,m,s;inline void add(int u,int v,int dis){    e[++cnt].v=v;    e[cnt].w=dis;    e[cnt].next=head[u];    head[u]=cnt;}struct node{    int dis;// 值     int pos;// 位置     bool operator <( const node &x)const    {        return x.dis
         
          q;inline void dij()//名字太长了 容易打错 简写dij {    dis[s]=0;    q.push((node){
    0,s});    while(!q.empty())    {        node tmp=q.top();        q.pop();        int x=tmp.pos,d=tmp.dis;         if(vis[x])            continue;        vis[x]=1;        for(int i=head[x];i;i=e[i].next)        {            int y=e[i].v;            if(dis[y]>dis[x]+e[i].w)            {                dis[y]=dis[x]+e[i].w;            //    if(!vis[y])                //{
                        q.push(node{dis[y],y});            //    }            }        }    }} int main(){    n=read(),m=read(),s=read();    for(rg int i=1;i<=n;i++)        dis[i]=2147482647;// 尽量赋值大一点 防止答案超过这个数！！！    for(rg int i=1,u,v,d;i<=m;i++)    {        u=read(),v=read(),d=read();        add(u,v,d);    }    dij();    for(int i=1;i<=n;i++)        printf("%d ",dis[i]);}
         
        
       
      
     

 倍增版LCA

/*            LCA            倍增 */#include 
     
      #include 
      
       #include 
       
        #define ll long long#define rg registerusing namespace std;inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}struct cym{    int t,nex;}e[1000001];int depth[500001],fa[500001][22],lg[500001],head[500001],n,m,s;int cnt;inline void add(int x,int y){    e[++cnt].t=y;    e[cnt].nex=head[x];    head[x]=cnt;}void dfs(int f,int fath)// f 表示当前的节点，fath 表示他的父亲节点 {    depth[f]=depth[fath]+1;    fa[f][0]=fath;    for(rg int i=1;(1<
        
         <=depth[f];i++)        fa[f][i]=fa[fa[f][i-1]][i-1];// 核心转移         // f的2^i祖先=f的2^(i-1)的祖先的2(i-1)祖先        //2^i=2^(i-1)+2^(i-1)    for(rg int i=head[f];i;i=e[i].nex)        if(e[i].t!=fath)            dfs(e[i].t,f); }inline int lca(int x,int y){    if(depth[x]
         
          =y的深度        swap(x,y);    while(depth[x]>depth[y])        x=fa[x][lg[depth[x]-depth[y]]-1];//先跳到同一深度    if(x==y)        return x;// 如果x是y的祖先，那他们的lca就是x    for(rg int k=lg[depth[x]]-1;k>=0;k--)    {        if(fa[x][k]!=fa[y][k])            x=fa[x][k],y=fa[y][k];    }     return fa[x][0];//返回父节点 }int main(){    n=read(),m=read(),s=read();    for(rg int i=1,x,y;i<=n-1;i++)    {        x=read(),y=read();        add(x,y);        add(y,x);    }    dfs(s,0);    for(rg int i=1;i<=n;i++)        lg[i]=lg[i-1]+(1<
         
        
       
      
     

 区间M的最小值（单调队列优化Dp）

 

#include 
     
      #include 
      
       #include 
       
        //#include 
        
         #define ll long long#define rg register#define ull unsigned long long using namespace std;int n,m;int k,tot,head=1,tail=0;int a[2000009],q[2000009];inline int read(){    int x=0,f=1;    char ch;    while (ch < '0' || ch > '9')  {
   if (ch=='-')f = -1;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}    return f*x;}int main(){    n=read(),m=read();    for(rg int i=1;i<=n;i++)        a[i]=read();    for(rg int i=1;i<=n;i++)    {        printf("%d\n",a[q[head]]);        while(i-q[head]+1>m&&head<=tail)                head++;        while(a[i]
         
          <=tail)            tail--;        q[++tail]=i;    }    //system("pause");    return 0;}