[关闭]
@910935974 2019-10-10T11:24:15.000000Z 字数 33421 阅读 517

算法笔记——数据结构

算法 数据结构

栈

  1. #include<stack>
  2. stack<int>stk;

同时也可以用数组模拟栈。

1.进栈：

  1. stk.push(x);

2.出栈（弹出栈顶元素）：

  1. stk.pop();

3.检查栈是否非空（空返回0，非空返回1）：

  1. stk.empty();

4.输出栈顶元素：

  1. stk.top();

5.输出栈中元素个数：

  1. stk.size();
  1. #include<cstdio>
  2. #define maxn 100005
  3. using namespace std;
  5. int n;
  6. int top,a[maxn],stk[maxn];
  8. int main()
  9. {
  10.     scanf("%d",&n);
  11.     for(int i=1;i<=n;++i)
  12.     scanf("%d",&a[i]);
  13.     for(int i=1;i<=n;++i)
  14.     {
  15.         while(top&&a[i]<stk[top])top--;
  16.         stk[++top]=a[i];
  17.     }
  18.     for(int i=1;i<=top;++i)
  19.     printf("%d ",stk[i]);
  20.     return 0;
  21. }

队列

  1. #include<queue>
  2. queue<int>que;
  1. queue.push(x);

2.删除:

  1. queue.pop();

3.访问队首元素：

  1. queue.front();

4.访问队尾元素：

  1. queue.back();

5.判断队列是否为空：

  1. queue.empty();

6.询问队列的元素个数：

  1. queue.size();
  1. #include<bits/stdc++.h>
  2. #define M 1000005
  3. using namespace std;
  4. int n,k,a[M],q[M],f[M],f_mx[M];//q数组存下标
  5. int main()
  6. {
  7.     scanf("%d%d",&n,&k);
  8.     for(int i=1;i<=n;i++)
  9.     scanf("%d",&a[i]);
  10.     if(k==1)
  11.     {
  12.         for(int i=1;i<=n;i++)
  13.         printf("%d ",a[i]);
  14.         printf("\n");
  15.         for(int i=1;i<=n;i++)
  16.         printf("%d ",a[i]);
  17.         return 0;
  18.     }
  19.     int h=1,t=0;//定义头，尾指针
  20.     for(int i=1;i<=n;i++)
  21.     {
  22.         while(h<=t&&i-q[h]>=k)h++;//判断队首有没有超过区间范围
  23.         if(i>=k)f[i-k+1]=min(a[q[h]],a[i]);//求解
  24.         while(h<=t&&a[i]<=a[q[t]])t--;//判断队尾是否大于队首
  25.         q[++t]=i;
  26.     }//求最小值
  27.     h=1,t=0;
  28.     for(int i=1;i<=n;i++)
  29.     {
  30.         while(h<=t&&i-q[h]>=k)h++;//判断队首有没有超过区间范围
  31.         if(i>=k)f_mx[i-k+1]=max(a[q[h]],a[i]);//求解
  32.         while(h<=t&&a[i]>=a[q[t]])t--;//判断队尾是否大于队首
  33.         q[++t]=i;
  34.     }
  35.     for(int i=1;i<=n-k+1;i++)
  36.     printf("%d ",f[i]);
  37.     printf("\n");
  38.     for(int i=1;i<=n-k+1;i++)
  39.     printf("%d ",f_mx[i]);
  40.     return 0;
  41. }

堆

  1. #include<queue>
  2. priority_queue<int,vector<int>,greater<int> >que;

2.插入：

  1. que.push(x);

3.删除堆顶元素：

  1. que.pop();

4.输出堆顶元素：

  1. que.top();
  1. #include<cstdio>
  2. #include<queue>
  3. #include<algorithm>
  4. using namespace std;
  6. priority_queue<int,vector<int>,greater<int> >que;
  7. int n;
  9. int main()
  10. {
  11.     scanf("%d",&n);
  12.     for(int i=1;i<=n;++i)
  13.     {
  14.         int x;
  15.         scanf("%d",&x);
  16.         if(x==1)
  17.         {
  18.             int y;
  19.             scanf("%d",&y);
  20.             que.push(y);
  21.         }
  22.         if(x==2)
  23.         printf("%d\n",que.top());
  24.         if(x==3)
  25.         que.pop();
  26.     }
  27.     return 0;
  28. }

2.左偏树：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define maxn 150005
  4. #define lid tr[x].ch[0]
  5. #define rid tr[x].ch[1]
  6. using namespace std;
  8. struct node
  9. {
  10.     int val,dis,fa,ch[2];
  11. }tr[maxn];//定义堆数组
  12. int n,m;
  14. int getfa(int x)
  15. {
  16.     if(tr[x].fa!=x)return tr[x].fa=getfa(tr[x].fa); 
  17.     return x;
  18. }//找根(路径压缩)
  20. int merge(int x,int y)
  21. {
  22.     if(x==0||y==0)
  23.     return x+y;
  24.     if(tr[x].val>tr[y].val||(tr[x].val==tr[y].val&&x>y))
  25.     swap(x,y);
  26.     rid=merge(rid,y);
  27.     if(tr[lid].dis<tr[rid].dis)
  28.     swap(lid,rid);
  29.     tr[lid].fa=tr[rid].fa=tr[x].fa=x;
  30.     tr[x].dis=tr[rid].dis+1;
  31.     return x;
  32. }//左偏树的合并
  34. void pop(int x)
  35. {
  36.     tr[x].val=-1;
  37.     tr[lid].fa=lid;
  38.     tr[rid].fa=rid;
  39.     tr[x].fa=merge(lid,rid);
  40. }
  42. int main()
  43. {
  44.     scanf("%d%d",&n,&m);
  45.     tr[0].dis=-1;
  46.     for(int i=1;i<=n;++i)
  47.     {
  48.         scanf("%d",&tr[i].val);
  49.         tr[i].fa=i;
  50.     }
  51.     for(int i=1;i<=m;++i)
  52.     {
  53.         int op;
  54.         scanf("%d",&op);
  55.         if(op==1)
  56.         {
  57.             int x,y;
  58.             scanf("%d%d",&x,&y);
  59.             if(tr[x].val==-1||tr[y].val==-1)
  60.             continue;
  61.             if(x==y)
  62.             continue;
  63.             x=getfa(x);
  64.             y=getfa(y);
  65.             if(x!=y)
  66.             tr[x].fa=tr[y].fa=merge(x,y);
  67.         }
  68.         else if(op==2)
  69.         {
  70.             int x;
  71.             scanf("%d",&x);
  72.             if(tr[x].val==-1)
  73.             printf("-1\n");
  74.             else
  75.             {
  76.                 int y=getfa(x);
  77.                 printf("%d\n",tr[y].val);
  78.                 pop(y);
  79.             }
  80.         }
  81.     }
  82.     return 0;
  83. }

ST表

  1. #include<cstdio>
  2. #define maxn 1000005
  3. using namespace std;
  5. int n,m;
  6. int a[maxn],st[maxn][4],log[maxn];
  8. int max(int x,int y)
  9. {
  10.     return x>y?x:y;
  11. }
  13. int main()
  14. {
  15.     scanf("%d%d",&n,&m);
  16.     for(int i=1;i<=n;++i)
  17.     scanf("%d",&a[i]);
  18.     log[0]=-1;
  19.     for(int i=1;i<=n;++i)
  20.     {
  21.         st[i][0]=a[i];
  22.         log[i]=log[i>>1]+1;
  23.     }//预处理
  24.     for(int j=1;j<=20;++j)
  25.     {
  26.         for(int i=1;i+(1<<j)-1<=n;++i)
  27.         st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
  28.     }
  29.     for(int i=1;i<=m;++i)
  30.     {
  31.         int l,r;
  32.         scanf("%d%d",&l,&r);
  33.         int s=log[r-l+1];
  34.         printf("%d\n",max(st[l][s],st[r-(1<<s)+1][s]));
  35.     }
  36.     return 0;
  37. }

树状数组

1.求lowbit

  1. int lowbit(int n)
  2. {
  3.     return n&(-n);
  4. }//求lowbit

2.修改操作

  1. void add(int x,int y)
  2. {
  3.     while(x<=n)
  4.     {
  5.         c[x]+=y;
  6.         x+=lowbit(x);
  7.     }
  8. }//修改树状数组

3.查询操作

  1. int query(int x)
  2. {
  3.     int sum=0;
  4.     while(x)
  5.     {
  6.         sum+=c[x];
  7.         x-=lowbit(x);
  8.     }
  9.     return sum;
  10. }//输出前缀和

完整代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int s[500005],c[500005],tot[500005],t,m,n;
  4. int lowbit(int n)
  5. {
  6.     return n&(-n);
  7. }//求lowbit
  8. void add(int x,int y)
  9. {
  10.     while(x<=n)
  11.     {
  12.         c[x]+=y;
  13.         x+=lowbit(x);
  14.     }
  15. }//修改树状数组
  16. int query(int x)
  17. {
  18.     int sum=0;
  19.     while(x)
  20.     {
  21.         sum+=c[x];
  22.         x-=lowbit(x);
  23.     }
  24.     return sum;
  25. }//输出前缀和
  26. int main()
  27. {
  28.     scanf("%d%d",&n,&m);
  29.     for(int i=1;i<=n;i++)
  30.     {
  31.         scanf("%d",&s[i]);
  32.         add(i,s[i]);
  33.     }
  34.     for(int i=1;i<=m;i++)
  35.     {
  36.         int a,x,y;
  37.         scanf("%d%d%d",&a,&x,&y);
  38.         if(a==1)
  39.         add(x,y);
  40.         if(a==2)
  41.         tot[++t]=query(y)-query(x-1);   
  42.     }
  43.     for(int i=1;i<=t;i++)
  44.     printf("%d\n",tot[i]);
  45.     return 0;
  46. }

支持区间修改的树状数组：差分树状数组
只需要小小的修改：
1.读入数据时：

  1. for(int i=1;i<=n;i++)
  2. scanf("%d",&s1[i]);
  3. for(int i=1;i<=n;i++)
  4. {
  5.     s2[i]=s1[i]-s1[i-1];
  6.     add(i,s2[i]);
  7. }//建立差分数组

2.区间修改时：

  1. int x,y,z;
  2. scanf("%d%d%d",&x,&y,&z);
  3. add(x,z);
  4. add(y+1,-z);

ok！

线段树

1.普通线段树
a.建树

  1. void build(ll k,ll l,ll r)
  2. {
  3.     tr[k].l=l;
  4.     tr[k].r=r;
  5.     tr[k].flag1=0;
  6.     tr[k].flag2=1;
  7.     if(l==r)
  8.     {
  9.         tr[k].sum=a[l];
  10.         return;
  11.     }
  12.     ll mid=(l+r)>>1;
  13.     build(lid,l,mid);
  14.     build(rid,mid+1,r);
  15.     update(k);
  16. }//建树

b.区间加

  1. void modify1(ll k,ll l,ll r,ll del)
  2. {
  3.     if(tr[k].l>=l&&tr[k].r<=r)
  4.     {
  5.         tr[k].sum+=del*(tr[k].r-tr[k].l+1);
  6.         tr[k].flag1+=del;
  7.         return;
  8.     }
  9.     ll mid=(tr[k].l+tr[k].r)>>1;
  10.     if(tr[k].flag2!=1||tr[k].flag1)
  11.     pushdown(k);
  12.     if(l<=mid)
  13.     modify1(lid,l,r,del);
  14.     if(r>mid)
  15.     modify1(rid,l,r,del);
  16.     update(k);
  17. }//区间加

c.区间乘

  1. void modify2(ll k,ll l,ll r,ll del)
  2. {
  3.     if(tr[k].l>=l&&tr[k].r<=r)
  4.     {
  5.         tr[k].sum*=del;
  6.         tr[k].flag1*del;
  7.         tr[k].flag2*=del;
  8.         return;
  9.     }
  10.     ll mid=(tr[k].l+tr[k].r)>>1;
  11.     if(tr[k].flag2!=1||tr[k].flag1)
  12.     pushdown(k);
  13.     if(l<=mid)
  14.     modify2(lid,l,r,del);
  15.     if(r>mid)
  16.     modify2(rid,l,r,del);
  17.     update(k);
  18. }//区间乘

d.标记下放（难点）

  1. void pushdown(ll k)
  2. {
  3.     ll l=tr[k].l,r=tr[k].r;
  4.     ll mid=(l+r)>>1;
  5.     tr[lid].flag2*=tr[k].flag2;
  6.     tr[lid].flag1*=tr[k].flag2;
  7.     tr[lid].sum*=tr[k].flag2;
  8.     tr[rid].flag2*=tr[k].flag2;
  9.     tr[rid].flag1*=tr[k].flag2;
  10.     tr[rid].sum*=tr[k].flag2;
  11.     tr[k].flag2=1;
  12.     tr[lid].flag1+=tr[k].flag1;
  13.     tr[rid].flag1+=tr[k].flag1;
  14.     tr[lid].sum+=(mid-l+1)*tr[k].flag1;
  15.     tr[rid].sum+=(r-mid)*tr[k].flag1;
  16.     tr[k].flag1=0;
  17. }

e.区间和查询

  1. ll query(ll k,ll l,ll r)
  2. {
  3.     if(tr[k].l>=l&&tr[k].r<=r)
  4.     return tr[k].sum;
  5.     ll ret=0;
  6.     ll mid=(tr[k].l+tr[k].r)>>1;
  7.     if(tr[k].flag2!=1||tr[k].flag1)
  8.     pushdown(k);
  9.     if(l<=mid)
  10.     ret+=query(lid,l,r);
  11.     if(r>mid)
  12.     ret+=query(rid,l,r);
  13.     return ret;
  14. }//区间求和

f.所谓的上传(update)

  1. void update(ll k)
  2. {
  3.     tr[k].sum=tr[lid].sum+tr[rid].sum;
  4. }

完整代码：

  1. #include<cstdio>
  2. #define ll long long
  3. #define maxn 1000005
  4. #define lid (k<<1)
  5. #define rid (k<<1|1)
  6. using namespace std;
  8. struct node
  9. {
  10.     ll l,r;
  11.     ll flag1,flag2;
  12.     ll sum;
  13. }tr[maxn*4];
  14. ll n,m,mod;
  15. ll a[maxn];
  17. void update(ll k)
  18. {
  19.     tr[k].sum=tr[lid].sum+tr[rid].sum;
  20. }
  22. void pushdown(ll k)
  23. {
  24.     ll l=tr[k].l,r=tr[k].r;
  25.     ll mid=(l+r)>>1;
  26.     tr[lid].flag2*=tr[k].flag2;
  27.     tr[lid].flag1*=tr[k].flag2;
  28.     tr[lid].sum*=tr[k].flag2;
  29.     tr[rid].flag2*=tr[k].flag2;
  30.     tr[rid].flag1*=tr[k].flag2;
  31.     tr[rid].sum*=tr[k].flag2;
  32.     tr[k].flag2=1;
  33.     tr[lid].flag1+=tr[k].flag1;
  34.     tr[rid].flag1+=tr[k].flag1;
  35.     tr[lid].sum+=(mid-l+1)*tr[k].flag1;
  36.     tr[rid].sum+=(r-mid)*tr[k].flag1;
  37.     tr[k].flag1=0;
  38. }
  40. void build(ll k,ll l,ll r)
  41. {
  42.     tr[k].l=l;
  43.     tr[k].r=r;
  44.     tr[k].flag1=0;
  45.     tr[k].flag2=1;
  46.     if(l==r)
  47.     {
  48.         tr[k].sum=a[l];
  49.         return;
  50.     }
  51.     ll mid=(l+r)>>1;
  52.     build(lid,l,mid);
  53.     build(rid,mid+1,r);
  54.     update(k);
  55. }//建树
  57. void modify1(ll k,ll l,ll r,ll del)
  58. {
  59.     if(tr[k].l>=l&&tr[k].r<=r)
  60.     {
  61.         tr[k].sum+=del*(tr[k].r-tr[k].l+1);
  62.         tr[k].flag1+=del;
  63.         return;
  64.     }
  65.     ll mid=(tr[k].l+tr[k].r)>>1;
  66.     if(tr[k].flag2!=1||tr[k].flag1)
  67.     pushdown(k);
  68.     if(l<=mid)
  69.     modify1(lid,l,r,del);
  70.     if(r>mid)
  71.     modify1(rid,l,r,del);
  72.     update(k);
  73. }//区间加
  75. void modify2(ll k,ll l,ll r,ll del)
  76. {
  77.     if(tr[k].l>=l&&tr[k].r<=r)
  78.     {
  79.         tr[k].sum*=del;
  80.         tr[k].flag1*del;
  81.         tr[k].flag2*=del;
  82.         return;
  83.     }
  84.     ll mid=(tr[k].l+tr[k].r)>>1;
  85.     if(tr[k].flag2!=1||tr[k].flag1)
  86.     pushdown(k);
  87.     if(l<=mid)
  88.     modify2(lid,l,r,del);
  89.     if(r>mid)
  90.     modify2(rid,l,r,del);
  91.     update(k);
  92. }//区间乘
  94. ll query(ll k,ll l,ll r)
  95. {
  96.     if(tr[k].l>=l&&tr[k].r<=r)
  97.     return tr[k].sum;
  98.     ll ret=0;
  99.     ll mid=(tr[k].l+tr[k].r)>>1;
  100.     if(tr[k].flag2!=1||tr[k].flag1)
  101.     pushdown(k);
  102.     if(l<=mid)
  103.     ret+=query(lid,l,r);
  104.     if(r>mid)
  105.     ret+=query(rid,l,r);
  106.     return ret;
  107. }//区间求和
  109. ll main()
  110. {
  111.     scanf("%d%d",&n,&m);
  112.     for(ll i=1;i<=n;++i)
  113.     scanf("%d",&a[i]);
  114.     build(1,1,n);
  115.     for(ll i=1;i<=m;++i)
  116.     {
  117.         ll opt;
  118.         ll x,y,k;
  119.         scanf("%d",&opt);
  120.         switch (opt)
  121.         {
  122.             case 1:
  123.                 scanf("%d%d%d",&x,&y,&k);
  124.                 modify2(1,x,y,k);
  125.                 break;
  126.             case 2:
  127.                 scanf("%d%d%d",&x,&y,&k);
  128.                 modify1(1,x,y,k);
  129.                 break;
  130.             case 3:
  131.                 scanf("%d%d",&x,&y);
  132.                 printf("%d\n",query(1,x,y));
  133.                 break;
  134.         }
  135.     }
  136.     return 0;
  137. }

模板题：
a.【模板】线段树 1;
b.【模板】线段树 2；

2.可持久化线段树（主席树）
与普通的线段树不同的是，主席树可以询问历史版本，因而在代码上(主要是建树)略有不同。

  1. #include<cstdio>
  2. #define maxn 1000005
  3. using namespace std;
  4. int m,n,ndnum,tot,lc[maxn*24],rc[maxn*24],root[maxn];
  5. int val[maxn],sum[maxn*24],answer[maxn];
  6. void copynode(int a,int b)
  7. {
  8.     lc[a]=lc[b],rc[a]=rc[b],sum[a],sum[b];
  9. }
  10. void build(int x,int l,int r)
  11. {
  12.     if(l==r)
  13.     {
  14.         sum[x]=val[l];
  15.         return;
  16.     }
  17.     int mid=(l+r)>>1;
  18.     build(lc[x]=++ndnum,l,mid);
  19.     build(rc[x]=++ndnum,mid+1,r);
  20.     sum[x]=sum[lc[x]]+sum[rc[x]];
  21. }
  22. int modify(int rt,int l,int r,int pos,int del)
  23. {
  24.     int t=++ndnum;
  25.     copynode(t,rt);
  26.     if(l==r)
  27.     {
  28.         sum[t]=del;
  29.         return t;
  30.     }
  31.     int mid=(l+r)>>1;
  32.     if(pos<=mid)
  33.     lc[t]=modify(lc[t],l,mid,pos,del);
  34.     else
  35.     rc[t]=modify(rc[t],mid+1,r,pos,del);
  36.     sum[t]=sum[lc[t]]+sum[rc[t]];
  37.     return t;
  38. }
  39. int query(int x,int l,int r,int pos)
  40. {
  41.     if(l==r)
  42.     return sum[x];
  43.     int mid=(l+r)>>1;
  44.     if(pos<=mid)return query(lc[x],l,mid,pos);
  45.     else return query(rc[x],mid+1,r,pos);
  46. }
  47. int main()
  48. {
  49.     scanf("%d%d",&n,&m);
  50.     for(int i=1;i<=n;i++)
  51.     scanf("%d",&val[i]);
  52.     build(root[0]=++ndnum,1,n);
  53.     for(int i=1;i<=m;i++)
  54.     {
  55.         int v,stp;
  56.         scanf("%d%d",&v,&stp);
  57.         if(stp==1)
  58.         {
  59.             int x;
  60.             int y;
  61.             scanf("%d%d",&x,&y);
  62.             root[i]=modify(root[v],1,n,x,y);
  63.         }
  64.         if(stp==2)
  65.         {
  66.             int x;
  67.             scanf("%d",&x);
  68.             answer[++tot]=query(root[v],1,n,x);
  69.             root[i]=root[v];
  70.         }
  71.     }
  72.     for(int i=1;i<=tot;i++)
  73.     printf("%d\n",answer[i]);
  74.     return 0;
  75. }

模板题：
a.【模板】可持久化线段树 1（主席树）；
b.【模板】可持久化数组（可持久化线段树/平衡树）；

  1. #include<cstdio>
  2. #define maxn 100005
  3. #define maxm 300005
  4. using namespace std;
  6. int n,m,q,ndnum;
  7. int lc[maxn*24],rc[maxn*24],sum[maxn*24],num[maxn*24];
  8. int root[maxn],fa[maxn];
  9. char op[15];
  11. void update(int k)
  12. {
  13.     sum[k]=sum[lc[k]]+sum[rc[k]];
  14. }
  16. int build(int k,int l,int r,int del,int nu)
  17. {
  18.     if(!k)k=++ndnum;
  19.     if(l==r)
  20.     {
  21.         num[k]=nu;
  22.         sum[k]++;
  23.         return k;
  24.     }
  25.     int mid=(l+r)>>1;
  26.     if(del<=mid)
  27.     lc[k]=build(lc[k],l,mid,del,nu);
  28.     else
  29.     rc[k]=build(rc[k],mid+1,r,del,nu);
  30.     update(k);
  31.     return k;
  32. }//建立值域线段树
  34. int merge(int x,int y,int l,int r)
  35. {
  36.     if(!x)return y;
  37.     if(!y)return x;
  38.     if(x==y)
  39.     {
  40.         if(num[y])
  41.         {
  42.             num[x]=num[y];
  43.             sum[x]+=sum[y];
  44.         }
  45.         return x;
  46.     }
  47.     int mid=(l+r)>>1;
  48.     lc[x]=merge(lc[x],lc[y],l,mid);
  49.     rc[x]=merge(rc[x],rc[y],mid+1,r);//合并子树
  50.     update(x);
  51.     return x;
  52. }
  54. int find(int x)
  55. {
  56.     if(x!=fa[x])
  57.     return fa[x]=find(fa[x]);
  58.     return fa[x];
  59. }
  61. void unionn(int x,int y)
  62. {
  63.     x=find(x);
  64.     y=find(y);
  65.     if(x==y)return;
  66.     fa[y]=x;//并查集合并
  67.     root[x]=merge(root[x],root[y],1,n);//线段树合并
  68. }
  70. int query(int rt,int del,int l,int r)
  71. {
  72.     if(sum[rt]<del||!rt)return 0;
  73.     if(l==r)return num[rt];
  74.     int mid=(l+r)>>1,ret=0;
  75.     if(del<=sum[lc[rt]])
  76.     ret=query(lc[rt],del,l,mid);
  77.     else
  78.     ret=query(rc[rt],del-sum[lc[rt]],mid+1,r);
  79.     return ret;
  80. }
  82. int main()
  83. {
  84.     scanf("%d%d",&n,&m);
  85.     for(int i=1;i<=n;++i)
  86.     {
  87.         int x;
  88.         scanf("%d",&x);
  89.         fa[i]=i;
  90.         root[i]=build(root[i],1,n,x,i);
  91.     }//建树
  92.     for(int i=1;i<=m;++i)
  93.     {
  94.         int x,y;
  95.         scanf("%d%d",&x,&y);
  96.         unionn(x,y);//建桥(合并并查集和线段树)
  97.     }
  98.     scanf("%d",&q);
  99.     for(int i=1;i<=q;++i)
  100.     {
  101.         int x,y;
  102.         scanf("%s",op);
  103.         if(op[0]=='B')
  104.         {
  105.             scanf("%d%d",&x,&y);
  106.             unionn(x,y);//建桥
  107.         }
  108.         else
  109.         {
  110.             scanf("%d%d",&x,&y);
  111.             x=find(x);
  112.             int ans=query(root[x],y,1,n);
  113.             if(!ans)printf("-1\n");
  114.             else printf("%d\n",ans);
  115.         }
  116.     }
  117.     return 0;
  118. }

习题：
1.The Child and Sequence;
2.[SHOI2015]脑洞治疗仪；
3.CPU监控;
4.楼房重建；

树链剖分

1.建树：

  1. void add(int x,int y)
  2. {
  3.     tot++;
  4.     tr[tot].v=y;
  5.     tr[tot].next=head[x];
  6.     head[x]=tot;
  7. }

2.找重儿子：

  1. void dfs1(int x)
  2. {
  3.     size[x]=1;
  4.     for(int t=head[x];t;t=tr[t].next)
  5.     {
  6.         int y=tr[t].v;
  7.         if(y==fa[x])continue;
  8.         fa[y]=x;
  9.         dep[y]=dep[x]+1;
  10.         dfs1(y);
  11.         size[x]+=size[y];
  12.         if(size[y]>size[son[x]])
  13.         son[x]=y;//找重儿子
  14.     }
  15. }//确立父节点、深度，找重孩子

3.求dfs序及当前点走重儿子能走到的最浅的点：

  1. void dfs2(int x,int tp)
  2. {
  3.     in[x]=++idc;//dfs序 
  4.     seq[idc]=x;
  5.     top[x]=tp;
  6.     if(son[x])dfs2(son[x],tp);
  7.     for(int t=head[x];t;t=tr[t].next)
  8.     {
  9.         int y=tr[t].v;
  10.         if(y==fa[x]||y==son[x])continue;
  11.         dfs2(y,y);
  12.     }
  13.     out[x]=idc;
  14. }//寻找当前点走重儿子能走到的最浅的点

4.建立线段树（注意根据的是dfs序建立）：

  1. void build(int k,int l,int r)
  2. {
  3.     pool[k].l=l;
  4.     pool[k].r=r;
  5.     if(l==r)
  6.     {
  7.         pool[k].sum=val[seq[l]];
  8.         pool[k].flag=0;
  9.         return;
  10.     }
  11.     int mid=(l+r)>>1;
  12.     build(lid,l,mid);
  13.     build(rid,mid+1,r);
  14.     pool[k].sum=pool[lid].sum+pool[rid].sum;
  15.     pool[k].flag=0;
  16. }//建树

5.区间修改（一毛一样）

  1. void modify(int k,int l,int r,int del)
  2. {
  3.     if(pool[k].l>=l&&pool[k].r<=r)
  4.     {
  5.         pool[k].sum+=(pool[k].r-pool[k].l+1)*del;
  6.         pool[k].flag+=del;
  7.         return;
  8.     }
  9.     int mid=(pool[k].l+pool[k].r)>>1;
  10.     pushdown(k);
  11.     if(l<=mid)
  12.     modify(lid,l,r,del);
  13.     if(r>mid)
  14.     modify(rid,l,r,del);
  15.     update(k);
  16. }//区间修改

6.区间查询（一毛一样）

  1. int query(int k,int l,int r)
  2. {
  3.     if(pool[k].l>=l&&pool[k].r<=r)
  4.     return pool[k].sum;
  5.     int mid=(pool[k].l+pool[k].r)>>1,ret=0;
  6.     pushdown(k);
  7.     if(l<=mid)
  8.     ret+=query(lid,l,r);
  9.     if(r>mid)
  10.     ret+=query(rid,l,r);
  11.     update(k);
  12.     return ret;
  13. }//区间查询

完整代码：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define ll long long
  4. #define maxn 100005
  5. #define lid (k<<1)
  6. #define rid (k<<1|1)
  7. using namespace std;
  9. struct node
  10. {
  11.     int v,next;
  12. }tr[maxn<<1];
  13. struct tree
  14. {
  15.     int l,r;
  16.     int sum,flag;
  17. }pool[maxn*4];
  18. int n,m,r;
  19. int tot,head[maxn];
  20. int idc,size[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn],in[maxn],out[maxn],seq[maxn];//树链剖分数组
  21. ll val[maxn];
  23. void pushdown(int k)
  24. {
  25.     int l,r,mid,flag;
  26.     l=pool[k].l;
  27.     r=pool[k].r;
  28.     flag=pool[k].flag;
  29.     mid=(l+r)>>1;
  30.     if(!flag)return;
  31.     pool[lid].flag+=flag;
  32.     pool[lid].sum+=(mid-l+1)*flag;
  33.     pool[rid].flag+=flag;
  34.     pool[rid].sum+=(r-mid)*flag;
  35.     pool[k].flag=0;
  36. }//下放标记
  38. void update(int k)
  39. {
  40.     pool[k].sum=pool[lid].sum+pool[rid].sum;
  41. }
  43. void add(int x,int y)
  44. {
  45.     tot++;
  46.     tr[tot].v=y;
  47.     tr[tot].next=head[x];
  48.     head[x]=tot;
  49. }
  51. void dfs1(int x)
  52. {
  53.     size[x]=1;
  54.     for(int t=head[x];t;t=tr[t].next)
  55.     {
  56.         int y=tr[t].v;
  57.         if(y==fa[x])continue;
  58.         fa[y]=x;
  59.         dep[y]=dep[x]+1;
  60.         dfs1(y);
  61.         size[x]+=size[y];
  62.         if(size[y]>size[son[x]])
  63.         son[x]=y;//找重儿子
  64.     }
  65. }//确立父节点、深度，找重孩子
  67. void dfs2(int x,int tp)
  68. {
  69.     in[x]=++idc;//dfs序 
  70.     seq[idc]=x;
  71.     top[x]=tp;
  72.     if(son[x])dfs2(son[x],tp);
  73.     for(int t=head[x];t;t=tr[t].next)
  74.     {
  75.         int y=tr[t].v;
  76.         if(y==fa[x]||y==son[x])continue;
  77.         dfs2(y,y);
  78.     }
  79.     out[x]=idc;
  80. }//寻找当前点走重儿子能走到的最浅的点
  82. void build(int k,int l,int r)
  83. {
  84.     pool[k].l=l;
  85.     pool[k].r=r;
  86.     if(l==r)
  87.     {
  88.         pool[k].sum=val[seq[l]];
  89.         pool[k].flag=0;
  90.         return;
  91.     }
  92.     int mid=(l+r)>>1;
  93.     build(lid,l,mid);
  94.     build(rid,mid+1,r);
  95.     pool[k].sum=pool[lid].sum+pool[rid].sum;
  96.     pool[k].flag=0;
  97. }//建树
  99. void modify(int k,int l,int r,int del)
  100. {
  101.     if(pool[k].l>=l&&pool[k].r<=r)
  102.     {
  103.         pool[k].sum+=(pool[k].r-pool[k].l+1)*del;
  104.         pool[k].flag+=del;
  105.         return;
  106.     }
  107.     int mid=(pool[k].l+pool[k].r)>>1;
  108.     pushdown(k);
  109.     if(l<=mid)
  110.     modify(lid,l,r,del);
  111.     if(r>mid)
  112.     modify(rid,l,r,del);
  113.     update(k);
  114. }//区间修改
  116. int query(int k,int l,int r)
  117. {
  118.     if(pool[k].l>=l&&pool[k].r<=r)
  119.     return pool[k].sum;
  120.     int mid=(pool[k].l+pool[k].r)>>1,ret=0;
  121.     pushdown(k);
  122.     if(l<=mid)
  123.     ret+=query(lid,l,r);
  124.     if(r>mid)
  125.     ret+=query(rid,l,r);
  126.     update(k);
  127.     return ret;
  128. }//区间查询
  130. void add1(int x,int y,int z)
  131. {
  132.     while(top[x]!=top[y])
  133.     {
  134.         if(dep[top[x]]<dep[top[y]])swap(x,y);
  135.         modify(1,in[top[x]],in[x],z);
  136.         x=fa[top[x]];
  137.     }
  138.     if(dep[x]<dep[y])swap(x,y);
  139.     modify(1,in[y],in[x],z);
  140. }//树从x到y结点最短路径上所有节点的值都加上z
  142. int add2(int x,int y)
  143. {
  144.     int ret=0;
  145.     while(top[x]!=top[y])
  146.     {
  147.         if(dep[top[x]]<dep[top[y]])swap(x,y);
  148.         ret+=query(1,in[top[x]],in[x]);
  149.         x=fa[top[x]];
  150.     }
  151.     if(dep[x]<dep[y])swap(x,y);
  152.     ret+=query(1,in[y],in[x]);
  153.     return ret;
  154. }//从x到y结点最短路径上所有节点的值之和
  156. void add3(int x,int z)
  157. {
  158.     modify(1,in[x],out[x],z);
  159. }//x为根节点的子树内所有节点值都加上z
  161. int add4(int x)
  162. {
  163.     return query(1,in[x],out[x]);
  164. }//以x为根节点的子树内所有节点值之和
  166. int main()
  167. {
  168.     scanf("%d%d%d",&n,&m,&r);
  169.     for(int i=1;i<=n;++i)
  170.     scanf("%d",&val[i]);
  171.     for(int i=1;i<n;++i)
  172.     {
  173.         int x,y;
  174.         scanf("%d%d",&x,&y);
  175.         add(x,y);
  176.         add(y,x);
  177.     }
  178.     dep[r]=1;
  179.     fa[r]=0;
  180.     dfs1(r);
  181.     dfs2(r,r);
  182.     build(1,1,idc);
  183.     for(int i=1;i<=m;++i)
  184.     {
  185.         int op,x,y,z;
  186.         scanf("%d",&op);
  187.         switch (op)
  188.         {
  189.             case 1:
  190.                 scanf("%d%d%d",&x,&y,&z);
  191.                 add1(x,y,z);
  192.                 break;
  193.             case 2:
  194.                 scanf("%d%d",&x,&y);
  195.                 printf("%d\n",add2(x,y));
  196.                 break;
  197.             case 3:
  198.                 scanf("%d%d",&x,&z);
  199.                 add3(x,z);
  200.                 break;
  201.             case 4:
  202.                 scanf("%d",&x);
  203.                 printf("%d\n",add4(x));
  204.                 break;
  205.         }
  206.     }
  207.     return 0;
  208. }

平衡树

1.Treap平衡树
特点：操作简单，码量小。
缺点：有限制，不能做区间反转等。

a.建树：

  1. struct treap
  2. {
  3.     int l,r;
  4.     int val,dat;//val是实际权值,dap是随机权值
  5.     int size,cnt;//size是子树大小,cnt是元素个数
  6. }tr[maxn];

b.更新：

  1. void update(int p)
  2. {
  3.     tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
  4. }//更新子树大小

c.建立新节点：

  1. int New(int val)
  2. {
  3.     tot++;
  4.     tr[tot].val=val;
  5.     tr[tot].dat=rand();//赋予随机值
  6.     tr[tot].cnt=tr[tot].size=1;
  7.     return tot;
  8. }//建立新节点

d.右旋(zig)：

  1. void zig(int &p)
  2. {
  3.     int q=tr[p].l;
  4.     tr[p].l=tr[q].r;
  5.     tr[q].r=p;
  6.     p=q;
  7.     update(tr[p].r);
  8.     update(p);
  9. }//右旋操作

e.左旋(zag):

  1. void zag(int &p)
  2. {
  3.     int q=tr[p].r;
  4.     tr[p].r=tr[q].l;
  5.     tr[q].l=p;
  6.     p=q;
  7.     update(tr[p].l);
  8.     update(p);
  9. }//左旋操作

f.建立初始节点（防止越界）：

  1. void build()
  2. {
  3.     New(-inf),New(inf);
  4.     root=1;
  5.     tr[1].r=2;
  6.     update(root);
  7. }//初始化操作

g.插入节点：

  1. void insert(int &p,int val)
  2. {
  3.     if(p==0)
  4.     {
  5.         p=New(val);
  6.         return;
  7.     }
  8.     if(val==tr[p].val)
  9.     {
  10.         tr[p].cnt++;
  11.         update(p);
  12.         return;
  13.     }
  14.     if(val<tr[p].val)
  15.     {
  16.         insert(tr[p].l,val);//插入左子树
  17.         if(tr[p].dat<tr[tr[p].l].dat)zig(p);//不满足堆的性质,右旋
  18.     }
  19.     else
  20.     {
  21.         insert(tr[p].r,val);//插入右子树
  22.         if(tr[p].dat<tr[tr[p].r].dat)zag(p);//不满足堆的性质,左旋
  23.     }
  24.     update(p);
  25. }//插入节点

h.删除节点：

  1. void remove(int &p,int val)
  2. {
  3.     if(p==0)return;
  4.     if(val==tr[p].val)
  5.     {
  6.         if(tr[p].cnt>1)
  7.         {
  8.             tr[p].cnt--;
  9.             update(p);
  10.             return;
  11.         }//有重复
  12.         if(tr[p].l||tr[p].r)
  13.         {
  14.             if(tr[p].r==0||tr[tr[p].l].dat>tr[tr[p].r].dat)
  15.             {
  16.                 zig(p);
  17.                 remove(tr[p].r,val);
  18.             }//空右节点就把当前节点移到右节点
  19.             else
  20.             {
  21.                 zag(p);
  22.                 remove(tr[p].l,val);
  23.             }//空左节点就把当前节点移到左节点
  24.             update(p);
  25.         }//不是叶子节点,向下旋转
  26.         else p=0;//没有子树,直接删除
  27.         return;
  28.     }
  29.     val<tr[p].val?remove(tr[p].l,val):remove(tr[p].r,val);
  30.     update(p);
  31.     return;
  32. }//删除节点

i.求节点的排名：

  1. int getrank(int &p,int val)
  2. {
  3.     if(p==0)return 0;
  4.     if(val==tr[p].val)return tr[tr[p].l].size+1;//直接返回
  5.     if(val<tr[p].val)return getrank(tr[p].l,val);//向左子树查找
  6.     return getrank(tr[p].r,val)+tr[tr[p].l].size+tr[p].cnt;//向右子树查找,并加上左子树和当前节点的大小
  7. }//求节点的排名

j.求排名为rank的节点：

  1. int getval(int &p,int rank)
  2. {
  3.     if(p==0)return inf;
  4.     if(tr[tr[p].l].size>=rank)return getval(tr[p].l,rank);//向左查找
  5.     if(tr[tr[p].l].size+tr[p].cnt>=rank)return tr[p].val;//确定排名为rank的节点就是当前节点
  6.     return getval(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);//向右查找
  7. }//求排名为rank的节点

k.求前驱：

  1. int getpre(int val)
  2. {
  3.     int ans=1,p=root;//tr[1].val==-inf
  4.     while(p)
  5.     {
  6.         if(val==tr[p].val)
  7.         {
  8.             if(tr[p].l>0)
  9.             {
  10.                 p=tr[p].l;
  11.                 while(tr[p].r>0)p=tr[p].r;
  12.                 ans=p;
  13.             }
  14.             break;
  15.         }//先向左走一步,再一直向右走
  16.         if(tr[p].val<val&&tr[p].val>tr[ans].val)ans=p;//更新最优节点
  17.         p=val<tr[p].val?tr[p].l:tr[p].r;
  18.     }
  19.     return tr[ans].val;
  20. }//求前驱

l.求后继：

  1. int getnext(int val)
  2. {
  3.     int p=root,ans=2;//tr[2].val==inf
  4.     while(p)
  5.     {
  6.         if(val==tr[p].val)
  7.         {
  8.             if(tr[p].r>0)
  9.             {
  10.                 p=tr[p].r;
  11.                 while(tr[p].l>0)p=tr[p].l;
  12.                 ans=p;
  13.             }//先向右走一步,再一直向左走
  14.             break;
  15.         }
  16.         if(tr[p].val>val&&tr[p].val<tr[ans].val)ans=p;//更新最优节点
  17.         p=val<tr[p].val?tr[p].l:tr[p].r;
  18.     }
  19.     return tr[ans].val;
  20. }//求后继

完整代码：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define maxn 100005
  4. #define inf 1000000007
  5. using namespace std;
  7. struct treap
  8. {
  9.     int l,r;
  10.     int val,dat;//val是实际权值,dap是随机权值
  11.     int size,cnt;//size是子树大小,cnt是元素个数
  12. }tr[maxn];
  13. int n;
  14. int tot,root;
  16. void update(int p)
  17. {
  18.     tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
  19. }//更新子树大小
  21. int New(int val)
  22. {
  23.     tot++;
  24.     tr[tot].val=val;
  25.     tr[tot].dat=rand();//赋予随机值
  26.     tr[tot].cnt=tr[tot].size=1;
  27.     return tot;
  28. }//建立新节点
  30. void zig(int &p)
  31. {
  32.     int q=tr[p].l;
  33.     tr[p].l=tr[q].r;
  34.     tr[q].r=p;
  35.     p=q;
  36.     update(tr[p].r);
  37.     update(p);
  38. }//右旋操作
  40. void zag(int &p)
  41. {
  42.     int q=tr[p].r;
  43.     tr[p].r=tr[q].l;
  44.     tr[q].l=p;
  45.     p=q;
  46.     update(tr[p].l);
  47.     update(p);
  48. }//左旋操作
  50. void build()
  51. {
  52.     New(-inf),New(inf);
  53.     root=1;
  54.     tr[1].r=2;
  55.     update(root);
  56. }//初始化操作
  58. void insert(int &p,int val)
  59. {
  60.     if(p==0)
  61.     {
  62.         p=New(val);
  63.         return;
  64.     }
  65.     if(val==tr[p].val)
  66.     {
  67.         tr[p].cnt++;
  68.         update(p);
  69.         return;
  70.     }
  71.     if(val<tr[p].val)
  72.     {
  73.         insert(tr[p].l,val);//插入左子树
  74.         if(tr[p].dat<tr[tr[p].l].dat)zig(p);//不满足堆的性质,右旋
  75.     }
  76.     else
  77.     {
  78.         insert(tr[p].r,val);//插入右子树
  79.         if(tr[p].dat<tr[tr[p].r].dat)zag(p);//不满足堆的性质,左旋
  80.     }
  81.     update(p);
  82. }//插入节点
  84. void remove(int &p,int val)
  85. {
  86.     if(p==0)return;
  87.     if(val==tr[p].val)
  88.     {
  89.         if(tr[p].cnt>1)
  90.         {
  91.             tr[p].cnt--;
  92.             update(p);
  93.             return;
  94.         }//有重复
  95.         if(tr[p].l||tr[p].r)
  96.         {
  97.             if(tr[p].r==0||tr[tr[p].l].dat>tr[tr[p].r].dat)
  98.             {
  99.                 zig(p);
  100.                 remove(tr[p].r,val);
  101.             }//空右节点就把当前节点移到右节点
  102.             else
  103.             {
  104.                 zag(p);
  105.                 remove(tr[p].l,val);
  106.             }//空左节点就把当前节点移到左节点
  107.             update(p);
  108.         }//不是叶子节点,向下旋转
  109.         else p=0;//没有子树,直接删除
  110.         return;
  111.     }
  112.     val<tr[p].val?remove(tr[p].l,val):remove(tr[p].r,val);
  113.     update(p);
  114.     return;
  115. }//删除节点
  117. int getrank(int &p,int val)
  118. {
  119.     if(p==0)return 0;
  120.     if(val==tr[p].val)return tr[tr[p].l].size+1;//直接返回
  121.     if(val<tr[p].val)return getrank(tr[p].l,val);//向左子树查找
  122.     return getrank(tr[p].r,val)+tr[tr[p].l].size+tr[p].cnt;//向右子树查找,并加上左子树和当前节点的大小
  123. }//求节点的排名
  125. int getval(int &p,int rank)
  126. {
  127.     if(p==0)return inf;
  128.     if(tr[tr[p].l].size>=rank)return getval(tr[p].l,rank);//向左查找
  129.     if(tr[tr[p].l].size+tr[p].cnt>=rank)return tr[p].val;//确定排名为rank的节点就是当前节点
  130.     return getval(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);//向右查找
  131. }//求排名为rank的节点
  133. int getpre(int val)
  134. {
  135.     int ans=1,p=root;//tr[1].val==-inf
  136.     while(p)
  137.     {
  138.         if(val==tr[p].val)
  139.         {
  140.             if(tr[p].l>0)
  141.             {
  142.                 p=tr[p].l;
  143.                 while(tr[p].r>0)p=tr[p].r;
  144.                 ans=p;
  145.             }
  146.             break;
  147.         }//先向左走一步,再一直向右走
  148.         if(tr[p].val<val&&tr[p].val>tr[ans].val)ans=p;//更新最优节点
  149.         p=val<tr[p].val?tr[p].l:tr[p].r;
  150.     }
  151.     return tr[ans].val;
  152. }//求前驱
  154. int getnext(int val)
  155. {
  156.     int p=root,ans=2;//tr[2].val==inf
  157.     while(p)
  158.     {
  159.         if(val==tr[p].val)
  160.         {
  161.             if(tr[p].r>0)
  162.             {
  163.                 p=tr[p].r;
  164.                 while(tr[p].l>0)p=tr[p].l;
  165.                 ans=p;
  166.             }//先向右走一步,再一直向左走
  167.             break;
  168.         }
  169.         if(tr[p].val>val&&tr[p].val<tr[ans].val)ans=p;//更新最优节点
  170.         p=val<tr[p].val?tr[p].l:tr[p].r;
  171.     }
  172.     return tr[ans].val;
  173. }//求后继
  175. int main()
  176. {
  177.     scanf("%d",&n);
  178.     build();
  179.     for(int i=1;i<=n;++i)
  180.     {
  181.         int opt,x;
  182.         scanf("%d%d",&opt,&x);
  183.         switch(opt)
  184.         {
  185.             case 1:
  186.                 insert(root,x);
  187.                 break;
  188.             case 2:
  189.                 remove(root,x);
  190.                 break;
  191.             case 3:
  192.                 printf("%d\n",getrank(root,x)-1);
  193.                 break;
  194.             case 4:
  195.                 printf("%d\n",getval(root,x+1));
  196.                 break;
  197.             case 5:
  198.                 printf("%d\n",getpre(x));
  199.                 break;
  200.             case 6:
  201.                 printf("%d\n",getnext(x));
  202.                 break;
  203.         }
  204.     }
  205.     return 0;
  206. }

模板题：【模板】普通平衡树;

2.Splay平衡树

特点：无左右旋操作，可打标记。
缺点：难理解。
a.建树:

  1. struct node
  2. {
  3.     int fa,ch[2];
  4.     int val,cnt;
  5.     int size,rev;
  6. }tr[maxn];//fa是父亲,son是儿子,val为节点的权值,cnt为节点重复的个数,size是节点的子树大小,rev为翻转标记;

b.返回儿子是左儿子还是右儿子:

  1. int get(int x)
  2. {
  3.     int f=tr[x].fa;
  4.     return x==tr[f].ch[1];
  5. }//返回该节点是左儿子还是右儿子

c.更新子树大小：

  1. void update(int x)
  2. {
  3.     int l=tr[x].ch[0],r=tr[x].ch[1];
  4.     tr[x].size=tr[x].cnt+tr[l].size+tr[r].size;
  5. }//更新节点的子树大小

d.标记下传（区间翻转操作可用）:

  1. void pushdown(int x)
  2. {
  3.     if(tr[x].rev)
  4.     {
  5.         int l=tr[x].ch[0],r=tr[x].ch[1];
  6.         swap(tr[x].ch[0],tr[x].ch[1]);
  7.         tr[l].rev^=1;
  8.         tr[r].rev^=1;
  9.         tr[x].rev=0;
  10.     }
  11. }//标记下传

e.旋转操作（关键）：

  1. void rotate(int x)
  2. {
  3.     int f=tr[x].fa,ff=tr[f].fa,k=get(x),s=tr[x].ch[k^1];
  4.     tr[f].ch[k]=s;
  5.     tr[s].fa=f;
  6.     tr[ff].ch[get(f)]=x;
  7.     tr[x].fa=ff;
  8.     tr[x].ch[k^1]=f;
  9.     tr[f].fa=x;
  10.     update(x);
  11.     update(f);
  12. }//旋转操作

f.Splay操作（关键）:

  1. void splay(int x,int k=0)
  2. {
  3.     while(tr[x].fa!=k)
  4.     {
  5.         int f=tr[x].fa,ff=tr[f].fa;
  6.         if(ff!=k)
  7.         {
  8.             if(get(x)==get(f))rotate(f);
  9.             else rotate(x);
  10.         }
  11.         rotate(x);
  12.     }
  13.     if(!k)root=x;
  14. }//将某一节点旋转到k节点的子节点

g.插入节点(顺便把节点变成根节点)：

  1. void insert(int x)
  2. {
  3.     int k=root,p=0;
  4.     while(k&&tr[k].val!=x)
  5.     {
  6.         p=k;
  7.         k=tr[k].ch[x>tr[k].val];
  8.     }
  9.     if(k)
  10.     tr[k].cnt++;//有该节点了
  11.     else
  12.     {
  13.         k=++tot;
  14.         if(p)tr[p].ch[x>tr[p].val]=k;
  15.         tr[k].ch[0]=tr[k].ch[1]=0;
  16.         tr[k].fa=p;
  17.         tr[k].val=x;
  18.         tr[k].cnt=tr[k].size=1;
  19.     }
  20.     splay(k);
  21. }//插入节点

h.删除节点：

  1. void remove(int x)
  2. {
  3.     int last=getpre(x),next=getnext(x);
  4.     splay(last);
  5.     splay(next,last);//将x节点移到后继的左子节点
  6.     int del=tr[next].ch[0];//提取该节点
  7.     if(tr[del].cnt>1)
  8.     {
  9.         tr[del].cnt--;
  10.         splay(del);
  11.     }
  12.     else
  13.     {
  14.         tr[next].ch[0]=0;
  15.         update(next);
  16.         update(root);
  17.     }
  18. }//删除

i.find操作：

  1. void find(int x)
  2. {
  3.     int k=root;
  4.     while(tr[k].ch[x>tr[k].val]&&tr[k].val!=x)
  5.     k=tr[k].ch[x>tr[k].val];
  6.     splay(k);
  7. }//将最大的小于等于x的数所在的节点splay到根

j.查询排名为x的节点：

  1. int getval(int x)
  2. {
  3.     int k=root;
  4.     while(1)
  5.     {
  6.         pushdown(k);
  7.         int l=tr[k].ch[0];
  8.         if(l&&x<=tr[l].size)
  9.         k=tr[k].ch[0];
  10.         else if(x>tr[l].size+tr[k].cnt)
  11.         {
  12.             x-=tr[l].size+tr[k].cnt;
  13.             k=tr[k].ch[1];
  14.         }
  15.         else
  16.         return k;
  17.     }
  18. }//查询排名x的节点

k.求前驱：

  1. int getpre(int x)
  2. {
  3.     find(x);
  4.     if(tr[root].val<x)return root;
  5.     int k=tr[root].ch[0];
  6.     while(tr[k].ch[1])
  7.     k=tr[k].ch[1];
  8.     return k;
  9. }//求x的前驱

l.求后继：

  1. int getnext(int x)
  2. {
  3.     find(x);
  4.     if(tr[root].val>x)return root;
  5.     int k=tr[root].ch[1];
  6.     while(tr[k].ch[0])
  7.     k=tr[k].ch[0];
  8.     return k;
  9. }//求x的后继

m.区间翻转打标记：

  1. void reverse(int l,int r)
  2. {
  3.     int x=getval(l),y=getval(r+2);
  4.     splay(x);//将x转到根
  5.     splay(y,x);//将y转到x的子节点 
  6.     tr[tr[y].ch[0]].rev^=1;
  7. }//区间翻转

完整代码：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define oo 0x3f3f3f3f
  4. #define maxn 100005
  5. using namespace std;
  7. struct node
  8. {
  9.     int fa,ch[2];
  10.     int val,cnt;
  11.     int size,rev;
  12. }tr[maxn];//fa是父亲,son是儿子,val为节点的权值,cnt为节点重复的个数,size是节点的子树大小,rev为翻转标记;
  13. int root,tot;
  14. int n,op,x;
  16. int get(int x)
  17. {
  18.     int f=tr[x].fa;
  19.     return x==tr[f].ch[1];
  20. }//返回该节点是左儿子还是右儿子
  22. void update(int x)
  23. {
  24.     int l=tr[x].ch[0],r=tr[x].ch[1];
  25.     tr[x].size=tr[x].cnt+tr[l].size+tr[r].size;
  26. }//更新节点的子树大小
  28. void pushdown(int x)
  29. {
  30.     if(tr[x].rev)
  31.     {
  32.         int l=tr[x].ch[0],r=tr[x].ch[1];
  33.         swap(tr[x].ch[0],tr[x].ch[1]);
  34.         tr[l].rev^=1;
  35.         tr[r].rev^=1;
  36.         tr[x].rev=0;
  37.     }
  38. }//标记下传
  40. void rotate(int x)
  41. {
  42.     int f=tr[x].fa,ff=tr[f].fa,k=get(x),s=tr[x].ch[k^1];
  43.     tr[f].ch[k]=s;
  44.     tr[s].fa=f;
  45.     tr[ff].ch[get(f)]=x;
  46.     tr[x].fa=ff;
  47.     tr[x].ch[k^1]=f;
  48.     tr[f].fa=x;
  49.     update(x);
  50.     update(f);
  51. }//旋转操作
  53. void splay(int x,int k=0)
  54. {
  55.     while(tr[x].fa!=k)
  56.     {
  57.         int f=tr[x].fa,ff=tr[f].fa;
  58.         if(ff!=k)
  59.         {
  60.             if(get(x)==get(f))rotate(f);
  61.             else rotate(x);
  62.         }
  63.         rotate(x);
  64.     }
  65.     if(!k)root=x;
  66. }//将某一节点旋转到k节点的子节点
  68. void insert(int x)
  69. {
  70.     int k=root,p=0;
  71.     while(k&&tr[k].val!=x)
  72.     {
  73.         p=k;
  74.         k=tr[k].ch[x>tr[k].val];
  75.     }
  76.     if(k)
  77.     tr[k].cnt++;//有该节点了
  78.     else
  79.     {
  80.         k=++tot;
  81.         if(p)tr[p].ch[x>tr[p].val]=k;
  82.         tr[k].ch[0]=tr[k].ch[1]=0;
  83.         tr[k].fa=p;
  84.         tr[k].val=x;
  85.         tr[k].cnt=tr[k].size=1;
  86.     }
  87.     splay(k);
  88. }//插入节点
  90. void find(int x)
  91. {
  92.     int k=root;
  93.     while(tr[k].ch[x>tr[k].val]&&tr[k].val!=x)
  94.     k=tr[k].ch[x>tr[k].val];
  95.     splay(k);
  96. }//将最大的小于等于x的数所在的节点splay到根
  98. int getval(int x)
  99. {
  100.     int k=root;
  101.     while(1)
  102.     {
  103.         pushdown(k);
  104.         int l=tr[k].ch[0];
  105.         if(l&&x<=tr[l].size)
  106.         k=tr[k].ch[0];
  107.         else if(x>tr[l].size+tr[k].cnt)
  108.         {
  109.             x-=tr[l].size+tr[k].cnt;
  110.             k=tr[k].ch[1];
  111.         }
  112.         else
  113.         return k;
  114.     }
  115. }//查询排名x的节点
  117. void reverse(int l,int r)
  118. {
  119.     int x=getval(l),y=getval(r+2);
  120.     splay(x);//将x转到根
  121.     splay(y,x);//将y转到x的子节点 
  122.     tr[tr[y].ch[0]].rev^=1;
  123. }//区间翻转
  125. int getpre(int x)
  126. {
  127.     find(x);
  128.     if(tr[root].val<x)return root;
  129.     int k=tr[root].ch[0];
  130.     while(tr[k].ch[1])
  131.     k=tr[k].ch[1];
  132.     return k;
  133. }//求x的前驱
  135. int getnext(int x)
  136. {
  137.     find(x);
  138.     if(tr[root].val>x)return root;
  139.     int k=tr[root].ch[1];
  140.     while(tr[k].ch[0])
  141.     k=tr[k].ch[0];
  142.     return k;
  143. }//求x的后继
  145. void remove(int x)
  146. {
  147.     int last=getpre(x),next=getnext(x);
  148.     splay(last);
  149.     splay(next,last);//将x节点移到后继的左子节点
  150.     int del=tr[next].ch[0];//提取该节点
  151.     if(tr[del].cnt>1)
  152.     {
  153.         tr[del].cnt--;
  154.         splay(del);
  155.     }
  156.     else
  157.     {
  158.         tr[next].ch[0]=0;
  159.         update(next);
  160.         update(root);
  161.     }
  162. }//删除
  164. int main()
  165. {
  166.     scanf("%d",&n);
  167.     insert(oo);
  168.     insert(-oo);
  169.     for(int i=1;i<=n;++i)
  170.     {
  171.         scanf("%d%d",&op,&x);
  172.         switch (op)
  173.         {
  174.             case 1:insert(x);break;
  175.             case 2:remove(x);break;
  176.             case 3:find(x);printf("%d\n",tr[tr[root].ch[0]].size);break;
  177.             case 4:printf("%d\n",tr[getval(x+1)].val);break;
  178.             case 5:printf("%d\n",tr[getpre(x)].val);break;
  179.             case 6:printf("%d\n",tr[getnext(x)].val);break;
  180.         }
  181.     }
  182.     return 0;
  183. }

模板题：
1.【模板】普通平衡树;
2.【模板】文艺平衡树（Splay）;（区间翻转模板题）

1.[TJOI2013]最长上升子序列;
2.[NOI2005]维护数列;

LCT

  1. struct node
  2. {
  3.     int fa,size,rev,ch[2];
  4. }tr[maxn];//size记录字数异或和,rev记录翻转标记

2.信息更新：

  1. void update(int x)
  2. {
  3.     int l=tr[x].ch[0],r=tr[x].ch[1];
  4.     tr[x].size=tr[l].size^tr[r].size^val[x];
  5. }//更新节点的子树异或和

3.标记下传：

  1. void filp(int x)
  2. {
  3.     swap(tr[x].ch[0],tr[x].ch[1]);
  4.     tr[x].rev^=1;
  5. }
  7. void pushdown(int x)
  8. {
  9.     if(tr[x].rev)
  10.     {
  11.         int l=tr[x].ch[0],r=tr[x].ch[1];
  12.         if(l)filp(l);
  13.         if(r)filp(r);
  14.         tr[x].rev=0;
  15.     }
  16. }//标记下传

4.旋转操作：

  1. void rotate(int x)
  2. {
  3.     int f=tr[x].fa,ff=tr[f].fa,k=(tr[f].ch[1]==x),s=tr[x].ch[k^1];
  4.     if(get(f))tr[ff].ch[tr[ff].ch[1]==f]=x;
  5.     if(s)tr[s].fa=f;
  6.     tr[f].ch[k]=s;
  7.     tr[x].ch[k^1]=f;
  8.     tr[x].fa=ff;
  9.     tr[f].fa=x;
  10.     update(x);
  11.     update(f);
  12. }//旋转操作(与splay略有不同)

5.Splay操作：

  1. void splay(int x)
  2. {
  3.     int y=x,top=0;
  4.     hep[++top]=y;
  5.     while(get(y))
  6.     {
  7.         y=tr[y].fa;
  8.         hep[++top]=y;
  9.     }
  10.     while(top)
  11.     pushdown(hep[top--]);
  12.     while(get(x))
  13.     {
  14.         y=tr[x].fa;
  15.         top=tr[y].fa;
  16.         if(get(y))
  17.         {
  18.             if((tr[y].ch[0]==x)^(tr[top].ch[0]==y))rotate(x);
  19.             else rotate(y);
  20.         }
  21.         rotate(x);
  22.     }
  23.     update(x);
  24.     return;
  25. }//将x节点旋转到splay中的根

6.将x到树根的路径设为实链

  1. void access(int x)
  2. {
  3.     int y=0;
  4.     while(x)
  5.     {
  6.         splay(x);
  7.         tr[x].ch[1]=y;
  8.         update(x);
  9.         y=x;
  10.         x=tr[x].fa;
  11.     }
  12. }//将x到树根的路径设为实链

7.找树根:

  1. int findroot(int x)
  2. {
  3.     access(x);
  4.     splay(x);
  5.     while(tr[x].ch[0])
  6.     {
  7.         pushdown(x);
  8.         x=tr[x].ch[0];
  9.     }
  10.     return x;
  11. }//找树根

8.把x设为树根:s

  1. void makeroot(int x)
  2. {
  3.     access(x);
  4.     splay(x);
  5.     filp(x);
  6. }//把x设为树根

9.split操作：

  1. void split(int x,int y)
  2. {
  3.     makeroot(x);
  4.     access(y);
  5.     splay(y);
  6. }

10.动态加边：

  1. void link(int x,int y)
  2. {
  3.     makeroot(x);
  4.     if(findroot(y)!=x)tr[x].fa=y;
  5. }//x,y建边

11.动态删边：

  1. void cut(int x,int y)
  2. {
  3.     makeroot(x);
  4.     if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1])
  5.     {
  6.         tr[x].fa=tr[y].ch[0]=0;
  7.         update(y);
  8.     }
  9.     return;
  10. }//去掉x,y之间的边

完整代码：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define maxn 300005
  4. #define oo 0x3f3f3f3f
  5. using namespace std;
  7. struct node
  8. {
  9.     int fa,size,rev,ch[2];
  10. }tr[maxn];//size记录字数异或和,rev记录翻转标记
  11. int n,m;
  12. int val[maxn],hep[maxn];
  14. int get(int x)
  15. {
  16.     int f=tr[x].fa;
  17.     return tr[f].ch[0]==x||tr[f].ch[1]==x;
  18. }//返回该节点是左儿子还是右儿子
  20. void update(int x)
  21. {
  22.     int l=tr[x].ch[0],r=tr[x].ch[1];
  23.     tr[x].size=tr[l].size^tr[r].size^val[x];
  24. }//更新节点的子树异或和
  26. void filp(int x)
  27. {
  28.     swap(tr[x].ch[0],tr[x].ch[1]);
  29.     tr[x].rev^=1;
  30. }
  32. void pushdown(int x)
  33. {
  34.     if(tr[x].rev)
  35.     {
  36.         int l=tr[x].ch[0],r=tr[x].ch[1];
  37.         if(l)filp(l);
  38.         if(r)filp(r);
  39.         tr[x].rev=0;
  40.     }
  41. }//标记下传
  43. void rotate(int x)
  44. {
  45.     int f=tr[x].fa,ff=tr[f].fa,k=(tr[f].ch[1]==x),s=tr[x].ch[k^1];
  46.     if(get(f))tr[ff].ch[tr[ff].ch[1]==f]=x;
  47.     if(s)tr[s].fa=f;
  48.     tr[f].ch[k]=s;
  49.     tr[x].ch[k^1]=f;
  50.     tr[x].fa=ff;
  51.     tr[f].fa=x;
  52.     update(x);
  53.     update(f);
  54. }//旋转操作(与splay略有不同)
  56. void splay(int x)
  57. {
  58.     int y=x,top=0;
  59.     hep[++top]=y;
  60.     while(get(y))
  61.     {
  62.         y=tr[y].fa;
  63.         hep[++top]=y;
  64.     }
  65.     while(top)
  66.     pushdown(hep[top--]);
  67.     while(get(x))
  68.     {
  69.         y=tr[x].fa;
  70.         top=tr[y].fa;
  71.         if(get(y))
  72.         {
  73.             if((tr[y].ch[0]==x)^(tr[top].ch[0]==y))rotate(x);
  74.             else rotate(y);
  75.         }
  76.         rotate(x);
  77.     }
  78.     update(x);
  79.     return;
  80. }//将x节点旋转到splay中的根
  82. void access(int x)
  83. {
  84.     int y=0;
  85.     while(x)
  86.     {
  87.         splay(x);
  88.         tr[x].ch[1]=y;
  89.         update(x);
  90.         y=x;
  91.         x=tr[x].fa;
  92.     }
  93. }//将x到树根的路径设为实链
  95. int findroot(int x)
  96. {
  97.     access(x);
  98.     splay(x);
  99.     while(tr[x].ch[0])
  100.     {
  101.         pushdown(x);
  102.         x=tr[x].ch[0];
  103.     }
  104.     return x;
  105. }//找树根
  107. void makeroot(int x)
  108. {
  109.     access(x);
  110.     splay(x);
  111.     filp(x);
  112. }//把x设为树根
  114. void split(int x,int y)
  115. {
  116.     makeroot(x);
  117.     access(y);
  118.     splay(y);
  119. }
  121. void link(int x,int y)
  122. {
  123.     makeroot(x);
  124.     if(findroot(y)!=x)tr[x].fa=y;
  125. }//x,y建边
  127. void cut(int x,int y)
  128. {
  129.     makeroot(x);
  130.     if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1])
  131.     {
  132.         tr[x].fa=tr[y].ch[0]=0;
  133.         update(y);
  134.     }
  135.     return;
  136. }//去掉x,y之间的边
  138. int main()
  139. {
  140.     scanf("%d%d",&n,&m);
  141.     for(int i=1;i<=n;++i)
  142.     scanf("%d",&val[i]);
  143.     for(int i=1;i<=m;++i)
  144.     {
  145.         int op,x,y;
  146.         scanf("%d%d%d",&op,&x,&y);
  147.         switch (op)
  148.         {
  149.             case 0:split(x,y);printf("%d\n",tr[y].size);break;
  150.             case 1:link(x,y);break;
  151.             case 2:cut(x,y);break;
  152.             case 3:splay(x);val[x]=y;break;
  153.         }
  154.     }
  155.     return 0;
  156. }

模板题：
1.【模板】Link Cut Tree （动态树）；
2.[SDOI2008]洞穴勘测；

树套树

并查集

1.查找父亲：

  1. int find(int x)
  2. {
  3.     while(father[x]!=x)x=father[x];
  4.     return father[x];
  5. }

路径压缩：

  1. int find(int x)
  2. {
  3.     if(father[x]!=x)return father[x]=find(father[x]);
  4.     return father[x];
  5. }

2.合并集合:

  1. void unionn(int x,int y)
  2. {
  3.     x=find(x),y=find(y);
  4.     father[y]=x;
  5. }

3.询问两个元素是否在同一个集合中：

  1. int judge(int x,int y)
  2. {
  3.     x=find(x),y=find(y);
  4.     if(x==y)
  5.     return 1;
  6.     else return 0;
  7. }

完整代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,q,father[20005],ans[1000005];
  4. int find(int x)
  5. {
  6.     while(father[x]!=x)x=father[x];
  7.     return father[x];
  8. }
  9. void unionn(int x,int y)
  10. {
  11.     x=find(x),y=find(y);
  12.     father[y]=x;
  13. }
  14. int judge(int x,int y)
  15. {
  16.     x=find(x),y=find(y);
  17.     if(x==y)
  18.     return 1;
  19.     else return 0;
  20. }
  21. int main()
  22. {
  23.     scanf("%d%d",&n,&m);
  24.     for(int i=1;i<=n;i++)
  25.     father[i]=i;
  26.     for(int i=1;i<=m;i++)
  27.     {
  28.         int a,b;
  29.         scanf("%d%d",&a,&b);
  30.         unionn(a,b);
  31.     }
  32.     scanf("%d",&q);
  33.     for(int i=1;i<=q;i++)
  34.     {
  35.         int a,b;
  36.         scanf("%d%d",&a,&b);
  37.         ans[i]=judge(a,b);
  38.     }
  39.     for(int i=1;i<=q;i++)
  40.     if(ans[i]==1)
  41.     printf("Yes\n");
  42.     else printf("No\n");
  43.     return 0;
  44. }

模板题：亲戚；
还有一道带权并查集好题：一盘大棋；

线段树分治

CDQ分治

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define maxn 200005
  4. using namespace std;
  6. struct node
  7. {
  8.     int a,b,c,cnt,ans;
  9. }s1[maxn],s2[maxn];
  10. int n,m,k,mx,top,su[maxn];
  11. int c[maxn];//树状数组
  13. bool cmp1(node x,node y)
  14. {
  15.     if(x.a==y.a)
  16.     {
  17.         if(x.b==y.b)return x.c<y.c;
  18.         else return x.b<y.b;
  19.     }
  20.     else return x.a<y.a;
  21. }//第一维排序
  23. bool cmp2(node x,node y)
  24. {
  25.     if(x.b==y.b)
  26.     return x.c<y.c;
  27.     else return x.b<y.b;
  28. }//第二维排序
  30. int lowbit(int x)
  31. {
  32.     return x&(-x);
  33. }
  35. void add(int x,int y)
  36. {
  37.     while(x<=mx)
  38.     {
  39.         c[x]+=y;
  40.         x+=lowbit(x);
  41.     }
  42. }//树状数组单点加
  44. int query(int x)
  45. {
  46.     int sum=0;
  47.     while(x)
  48.     {
  49.         sum+=c[x];
  50.         x-=lowbit(x);
  51.     }
  52.     return sum;
  53. }//求单点前缀和
  55. void cdq(int l,int r)
  56. {
  57.     if(l==r)return;
  58.     int mid=(l+r)>>1;
  59.     cdq(l,mid);
  60.     cdq(mid+1,r);//类似于归并排序
  61.     sort(s2+l,s2+mid+1,cmp2);
  62.     sort(s2+mid+1,s2+r+1,cmp2);//第二维为关键字排序
  63.     int i,j=l;
  64.     for(i=mid+1;i<=r;++i)
  65.     {
  66.         while(s2[i].b>=s2[j].b&&j<=mid)
  67.         {
  68.             add(s2[j].c,s2[j].cnt);//在s2[j]位置加上s2[j]的个数
  69.             j++;
  70.         }
  71.         s2[i].ans+=query(s2[i].c);//保证树状数组里的数一定符合条件
  72.     }//类似归并
  73.     for(i=l;i<j;++i)
  74.     add(s2[i].c,-s2[i].cnt);//清空树状数组
  75. }//cdq分治
  77. int main()
  78. {
  79.     scanf("%d%d",&n,&k);
  80.     mx=k;//树状数组的区间
  81.     for(int i=1;i<=n;++i)
  82.     {
  83.         int a,b,c;
  84.         scanf("%d%d%d",&a,&b,&c);
  85.         s1[i].a=a;
  86.         s1[i].b=b;
  87.         s1[i].c=c;
  88.     }//初始化输入
  89.     sort(s1+1,s1+1+n,cmp1);//第一维为关键字排序
  90.     for(int i=1;i<=n;++i)
  91.     {
  92.         top++;
  93.         if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c)
  94.         {
  95.             m++;
  96.             s2[m].a=s1[i].a;
  97.             s2[m].b=s1[i].b;
  98.             s2[m].c=s1[i].c;
  99.             s2[m].cnt=top;
  100.             top=0;
  101.         }
  102.     }//第一维已有序,合并相同节点
  103.     cdq(1,m);//caq分治
  104.     for(int i=1;i<=m;++i)
  105.     su[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
  106.     for(int i=0;i<n;++i)
  107.     printf("%d\n",su[i]);
  108.     return 0;
  109. }

整体二分

点分治

分块

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define maxn 50005
  6. #define maxm 305
  7. using namespace std;
  9. struct node
  10. {
  11.     int l,r;
  12. }blo[maxm];//记录块的范围
  13. struct tree
  14. {
  15.     int past,now,num;
  16. }a[maxn];
  17. int n,m,tot,sum,nw,ans,len,num_all;
  18. int cnt[maxm][maxn],all[maxm][maxn],tong[maxn];//cnt[i][j]表示第i块j(离散化后)的个数,tong[i]表示离散化后i对应的原数
  19. int pos[maxn],wai[maxn],tab[maxn];;//pos[i]表示节点i所在的块
  21. inline int read()
  22. {
  23.     char ch;
  24.     while((ch=getchar())<'0'||ch>'9');
  25.     int res=ch-48;
  26.     while((ch=getchar())>='0'&&ch<='9')
  27.     res=res*10+ch-48;
  28.     return res;
  29. } //读入优化
  31. void print(int x)
  32. {
  33.     if(x<0)//负数
  34.     {
  35.         putchar('-');
  36.         x=-x;
  37.     }
  38.     if(x>9)
  39.         print(x/10);
  40.     putchar(x%10+'0');
  41. }
  43. bool cmp1(tree x,tree y)
  44. {
  45.     return x.past<y.past;
  46. }
  48. bool cmp2(tree x,tree y)
  49. {
  50.     return x.num<y.num;
  51. }
  53. int ask(int l,int r)
  54. {
  55.     memset(wai,0,sizeof(wai));
  56.     int p=pos[l],q=pos[r],ans=0,mx,nww=0;
  57.     if(p==q)
  58.     {
  59.         for(int i=l;i<=r;++i)
  60.         wai[a[i].now]++;
  61.         for(int i=1;i<=num_all;++i)
  62.         {
  63.             if(wai[i]>ans)
  64.             {
  65.                 ans=wai[i];
  66.                 mx=i;
  67.             }
  68.         }
  69.     }//在同一块内
  70.     else
  71.     {
  72.         for(int j=1;j<=num_all;++j)
  73.         wai[j]=all[q-1][j]-all[p][j];
  74.         for(int i=l;i<=blo[p].r;++i)
  75.         wai[a[i].now]++;
  76.         for(int i=blo[q].l;i<=r;++i)
  77.         wai[a[i].now]++;
  78.         for(int i=1;i<=num_all;++i)
  79.         {
  80.             if(wai[i]>ans)
  81.             {
  82.                 ans=wai[i];
  83.                 mx=i;
  84.             }
  85.         }
  86.     }
  87.     return tab[mx];
  88. }//分块
  90. int main()
  91. {
  92.     n=read();m=read();
  93.     for(int i=1;i<=n;++i)
  94.     {
  95.         a[i].past=read();
  96.         a[i].num=i;
  97.     }
  98.     sort(a+1,a+1+n,cmp1);
  99.     for(int i=1;i<=n;++i)
  100.     {
  101.         a[i].now=a[i-1].now;
  102.         if(a[i].past!=a[i-1].past)
  103.         {
  104.             a[i].now++;
  105.             num_all++;
  106.             tab[num_all]=a[i].past;
  107.         }
  108.     }//离散化
  109.     sort(a+1,a+1+n,cmp2);
  110.     tot=sqrt(n);
  111.     if(tot*tot<n)tot++;//统计块的个数
  112.     for(int i=1;i<=n;i+=tot)
  113.     {
  114.         blo[++nw].l=i;
  115.         blo[nw].r=i+tot-1;
  116.     }
  117.     if(nw<tot)
  118.     {
  119.         blo[++nw].l=nw*tot+1;
  120.         blo[nw].r=n;
  121.     }//统计块的范围
  122.     if(blo[nw].r>n)blo[nw].r=n;
  123.     for(int i=1;i<=tot;++i)
  124.     {
  125.         for(int j=blo[i].l;j<=blo[i].r;++j)
  126.         {
  127.             cnt[i][a[j].now]++;
  128.             pos[j]=i;
  129.         }
  130.     }//预处理出每个块不同数出现的个数
  131.     for(int i=1;i<=tot;++i)
  132.     {
  133.         for(int j=1;j<=num_all;++j)
  134.         all[i][j]=all[i-1][j]+cnt[i][j];
  135.     }
  136.     for(int i=1;i<=m;++i)
  137.     {
  138.         int l,r;
  139.         l=read();r=read();
  140.         l=(l+ans-1)%n;
  141.         r=(r+ans-1)%n;
  142.         l++;r++;
  143.         if(l>r)
  144.         swap(l,r);
  145.         ans=ask(l,r);
  146.         print(ans);
  147.         putchar('\n');
  148.     }
  149.     return 0;
  150. }

模板题：
1.蒲公英；
2.弹飞绵羊；

莫队

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<algorithm>
  4. #define ll long long
  5. #define maxn 50005
  6. using namespace std;
  8. struct node
  9. {
  10.     ll l,r,num;
  11. }que[maxn];
  12. struct answer
  13. {
  14.     ll mom,son;
  15. }ans[maxn];
  16. ll n,m,tot,mom,sum,total,cntt;
  17. ll co[maxn],son[maxn],cnt[maxn];
  19. bool cmp(node x,node y)
  20. {
  21.     return (x.l/tot)^(y.l/tot)?x.l<y.l:((x.l/tot)&1)?x.r<y.r:x.r>y.r;
  22. }//玄学奇偶性排序
  24. ll gcd(ll x,ll y)
  25. {
  26.     return (!y)?x:gcd(y,x%y);
  27. }
  29. void add(ll x)
  30. {
  31.     if(!x)return;
  32.     ll v=co[x];
  33.     total+=2*cnt[v];
  34.     cnt[v]++;
  35.     mom+=2*sum;
  36.     sum++;
  37. }
  39. void del(ll x)
  40. {
  41.     if(!x)return;
  42.     ll v=co[x];
  43.     total-=2*cnt[v]-2;
  44.     cnt[v]--;
  45.     mom-=2*sum-2;
  46.     sum--;
  47. }
  49. int main()
  50. {
  51.     scanf("%lld%lld",&n,&m);
  52.     for(ll i=1;i<=n;++i)
  53.     scanf("%lld",&co[i]);
  54.     for(ll i=1;i<=m;++i)
  55.     {
  56.         ll l,r;
  57.         scanf("%lld%lld",&l,&r);
  58.         if(l==r)
  59.         {
  60.             ans[i].son=0;
  61.             ans[i].mom=1;
  62.             continue;
  63.         }
  64.         cntt++;
  65.         que[cntt].l=l;
  66.         que[cntt].r=r;
  67.         que[cntt].num=i;
  68.     }
  69.     tot=n/sqrt(cntt*2/3);
  70.     sort(que+1,que+1+cntt,cmp);
  71.     ll l=0,r=0;
  72.     for(ll i=1;i<=m;++i)
  73.     {
  74.         ll ql=que[i].l,qr=que[i].r,nw=que[i].num;
  75.         while(l<ql)del(l++);
  76.         while(l>ql)add(--l);
  77.         while(r<qr)add(++r);
  78.         while(r>qr)del(r--);
  79.         ans[nw].mom=mom;
  80.         ans[nw].son=total;
  81.     }
  82.     for(ll i=1;i<=m;++i)
  83.     {
  84.         ll r=gcd(ans[i].son,ans[i].mom);
  85.         ans[i].son/=r;
  86.         ans[i].mom/=r;
  87.         printf("%lld/%lld\n",ans[i].son,ans[i].mom);
  88.     }
  89.     return 0;
  90. }

模板题： [国家集训队]小Z的袜子；

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注