[关闭]
@morehigh 2017-02-25T03:10:11.000000Z 字数 6567 阅读 923

CQUPT 集训队专题训练（线段树）

线段树

【创建线段树（初始化）】：
在完全二叉树中假如一个结点的序号（数组下标）为 I ，那么 （二叉树基本关系）
I 的父亲为 I/2，
I 的另一个兄弟为 I/2*2 或 I/2*2+1
I 的两个孩子为 I*2 (左) I*2+1(右)

区间更新：
lazy操作
void pushdown(int num)
{
if(laz[num]!=0)
{
tre[num*2]+=laz[num];
tre[num*2+1]+=laz[num];
laz[num*2]+=laz[num];
laz[num*2+1]+=laz[num];
laz[num]=0;
}
}
必须在更新完儿子节点的值之后再反过来更新父亲节点。

A - 敌兵布阵
题意：

  1. 有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人
  2. (1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30） 
  3. (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）; 
  4. (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数; 
  5. (4)End 表示结束，这条命令在每组数据最后出现; 
  6. 每组数据最多有40000条命令

解题思路：

  1. 线段树，单点更新，维护区间和问题

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  7. using namespace std;
  8. struct Node
  9. {
  10.     int a,b,sum;
  11. }t[150000];
  12. int r[50010],SUM; 
  13. void make(int x,int y,int num)
  14. {
  15.     t[num].a=x;
  16.     t[num].b=y;
  17.     if(x==y)
  18.     t[num].sum=r[y];
  19.     else
  20.     {
  21.         make(x,(x+y)/2,num*2);
  22.         make((x+y)/2+1,y,num*2+1);
  23.         t[num].sum=t[2*num].sum+t[2*num+1].sum;
  24.     }
  25. }
  26. void query(int x,int y,int num)
  27. {
  28.     if(x<=t[num].a&&y>=t[num].b)
  29.      SUM+=t[num].sum;
  30.      else
  31.      {
  32.         int adv=(t[num].a+t[num].b)/2;
  33.         if(x>adv) query(x,y,num*2+1);
  34.         else if(y<=adv) query(x,y,num*2);
  35.         else
  36.         {
  37.             query(x,y,2*num);
  38.             query(x,y,num*2+1);
  39.          }
  40.      }
  41. }
  42. void add(int x,int y,int num)
  43. {
  44.     t[num].sum+=y;
  45.     if(t[num].a==x&&t[num].b==x)return;
  46.     if(x>(t[num].a+t[num].b)/2)
  47.     add(x,y,2*num+1);
  48.     else
  49.     add(x,y,2*num);
  50. }
  51. void sub(int x,int y,int num)
  52. {
  53.     t[num].sum-=y;
  54.     if(t[num].a==x&&t[num].b==x)return;
  55.     if(x>(t[num].a+t[num].b)/2)
  56.     sub(x,y,2*num+1);
  57.     else
  58.     sub(x,y,2*num);
  59. }
  60. int main()
  61. {
  62.     int t,n;
  63.     char com[10];
  64.     cin>>t;
  65.     int j=1;
  66.     while(t--)
  67.     {
  68.         int temp,a,b;
  69.         scanf("%d",&n);
  70.         r[0]=0;
  71.         for(int i=1;i<=n;i++)
  72.         scanf("%d",&r[i]);
  73.         make(1,n,1);
  74.         cout<<"Case "<<j++<<":"<<endl;
  75.         while(cin>>com)
  76.         {
  77.             if(strcmp(com,"End")==0)
  78.             break;
  79.             if(strcmp(com,"Query")==0)
  80.             {
  81.                 scanf("%d%d",&a,&b);
  82.                 SUM=0;
  83.                 query(a,b,1);
  84.                 cout<<SUM<<endl;
  85.             }
  86.             if(strcmp(com,"Add")==0)
  87.             {
  88.                 scanf("%d%d",&a,&b);
  89.                 add(a,b,1);
  90.             }
  91.             if(strcmp(com,"Sub")==0)
  92.             {
  93.                 scanf("%d%d",&a,&b);
  94.                 sub(a,b,1);
  95.             }
  96.         }
  97.     }
  98.     return 0;
  99. }

B - Color the ball
题意：

  1. N个气球排成一排，接下来N行每行进行一次涂色操作，输入a,b，从气球a开始到气球b依次给每个气球涂一次颜色。求每个气球被涂了几次颜色？

解题思路：

  1. 每次操作更新区间涂色次数，最后将路径区间求和，得到涂色次数

代码：

  1. 树状数组代码
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <algorithm>
  7. using namespace std;
  8. int tree[500003];
  9. int lowbit(int x)
  10. {
  11.     return x&-x;
  12. }
  13. int update(int x,int val)
  14. {
  15.     while(x>0)
  16.     {
  17.         tree[x]+=val;
  18.         x-=lowbit(x);
  19.     }
  20. }
  21. int query(int x,int n)
  22. {
  23.     int ans=0;
  24.     while(x<=n)
  25.     {
  26.         ans+=tree[x];
  27.         x+=lowbit(x);
  28.     }
  29.     return ans;
  30. }
  31. int main()
  32. {
  33.     int n,a,b;
  34.     while(scanf("%d",&n)!=EOF&&n)
  35.     {
  36.         memset(tree,0,sizeof(tree));
  37.         for(int i=1;i<=n;i++)
  38.         {
  39.             scanf("%d%d",&a,&b);
  40.             update(b,1);
  41.             update(a-1,-1);
  42.         }
  43.         for(int i=1;i<=n;i++)
  44.         {
  45.             if(i!=n)
  46.             cout<<query(i,n)<<" ";
  47.             else
  48.             cout<<query(i,n)<<endl;
  49.         }
  50.     }
  51.     return 0;
  52. }
  53. 线段树代码
  54. #include <iostream>
  55. #include <cstdio>
  56. #include <cstring>
  57. #include <algorithm>
  59. using namespace std;
  60. struct Node
  61. {
  62.     int l,r,num;
  63. }tree[1000003];
  64. int ans[1000000];
  65. void build(int l,int r,int i)
  66. {
  67.     tree[i].l=l;
  68.     tree[i].r=r;
  69.     tree[i].num=0;
  70.     if(l!=r){
  71.       int mid=(l+r)/2;
  72.        build(l,mid,2*i);
  73.        build(mid+1,r,2*i+1);
  74.     }
  75. }
  76. void query(int l,int r,int i)
  77. {
  78.     if(l==tree[i].l&&r==tree[i].r)
  79.     tree[i].num+=1;
  80.     else
  81.     {
  82.         int mid=(tree[i].l+tree[i].r)/2;
  83.         if(r<=mid)
  84.         query(l,r,2*i);
  85.         else if(l>mid)
  86.         query(l,r,2*i+1);
  87.         else
  88.         {
  89.             query(l,mid,2*i);
  90.             query(mid+1,r,2*i+1);
  91.         }
  92.     }
  93. }
  94. void solve(int x)
  95. {
  96.     for(int i=tree[x].l;i<=tree[x].r;i++)
  97.     ans[i]+=tree[x].num;
  98.     if(tree[x].l==tree[x].r)
  99.     return;
  100.     solve(2*x+1);
  101.     solve(2*x);
  102. }
  103. int main()
  104. {
  105.     int n,x,y;
  106.     while(scanf("%d",&n)!=EOF&&n)
  107.     {
  108.         build(1,n,1);
  109.         for(int i=1;i<=n;i++)
  110.         {
  111.             scanf("%d%d",&x,&y);
  112.             query(x,y,1);
  113.         }
  114.         memset(ans,0,sizeof(ans));
  115.         solve(1);
  116.         for(int i=1;i<=n;i++)
  117.         {
  118.             if(i!=n)
  119.             cout<<ans[i]<<" ";
  120.             else
  121.             cout<<ans[i]<<endl;
  122.         }
  123.     }
  124.     return 0;
  125. }

D - Tunnel Warfare
题意：

  1. n个村庄，m个事件，三种操作
  2. 1.D x:第x个村庄被摧毁
  3. 2.Q x:输出第x个村庄可以直接和间接相连的村庄个数
  4. 3.R:最后一个被摧毁的村庄重建

解题思路：

  1. 对于一个点，看它是在当前区间的左半还是右半。在左半的话，看看是不是在右端的连续区间内，是的话，还要加上右半区间的左端连续区间。否则的话，只要计算它在左半区间的连接情况即可，在右半的话同理，看看是不是在左端的连续区间内，是的话，还要加上左半区间的右端连续区间。否则的话，只要计算它在右半区间的连接情况即可

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. struct Node
  8. {
  9.     int l,r;
  10.     int ls,rs,ms;
  11. }tree[150000];
  12. int op[50050];
  13. int n,m;
  15. void inittree(int l,int r,int i)
  16. {
  17.     tree[i].l=l;
  18.     tree[i].r=r;
  19.     tree[i].ls=tree[i].rs=tree[i].ms=r-l+1;
  20.     if(l<r)
  21.     {
  22.         int mid=(r+l)/2;
  23.         inittree(l,mid,2*i);
  24.         inittree(mid+1,r,2*i+1);
  25.     }
  26. }
  27. void update(int x,int flag,int i)
  28. {
  29.     if(tree[i].l==tree[i].r)
  30.     {
  31.         if(flag)
  32.         tree[i].ls=tree[i].rs=tree[i].ms=1;
  33.         else
  34.         tree[i].ls=tree[i].rs=tree[i].ms=0;
  35.         return ;
  36.     }
  37.     int mid=(tree[i].l+tree[i].r)/2;
  38.     if(x<=mid)
  39.     update(x,flag,2*i);
  40.     else
  41.     update(x,flag,2*i+1);
  42.     if(tree[2*i].ls==tree[2*i].r-tree[2*i].l+1)
  43.     tree[i].ls=tree[2*i].ls+tree[2*i+1].ls;
  44.     else
  45.     tree[i].ls=tree[2*i].ls;
  46.     if(tree[2*i+1].rs==tree[2*i+1].r-tree[2*i+1].l+1)
  47.        tree[i].rs=tree[2*i].rs+tree[2*i+1].rs;
  48.     else
  49.        tree[i].rs=tree[2*i+1].rs;
  50.     tree[i].ms=max(max(tree[2*i].ms,tree[2*i+1].ms),tree[2*i].rs+tree[2*i+1].ls);
  51. }
  52. int search(int x,int i)
  53. {
  54.     if(tree[i].ms==0||tree[i].l==tree[i].r||tree[i].ms==tree[i].r-tree[i].l+1)
  55.     return tree[i].ms;
  56.     int mid=(tree[i].l+tree[i].r)/2;
  57.     if(x<=mid)
  58.     {
  59.         if(x>=tree[2*i].r-tree[2*i].rs+1)
  60.         return tree[2*i].rs+tree[2*i+1].ls;
  61.         else
  62.         return search(x,2*i);
  63.     }
  64.     else
  65.     {
  66.         if(x<=tree[2*i+1].l+tree[2*i+1].ls-1)
  67.         return tree[2*i].rs+tree[2*i+1].ls;
  68.         else
  69.         return search(x,2*i+1);
  70.     }
  71. }
  72. int main()
  73. {
  74.     char com[5];
  75.     int x;
  76.     while(scanf("%d%d",&n,&m)!=EOF)
  77.     {
  78.         inittree(1,n,1);
  79.         int top=0;
  80.         for(int i=0;i<m;i++)
  81.         {
  82.             scanf("%s",com);
  83.             if(com[0]=='D')
  84.             {
  85.                 scanf("%d",&x);
  86.                 op[++top]=x;
  87.                 update(x,0,1);
  88.             }
  89.             else if(com[0]=='Q')
  90.             {
  91.                 scanf("%d",&x);
  92.                 cout<<search(x,1)<<endl;
  93.             }
  94.             else if(com[0]=='R')
  95.             {
  96.                 if(top>0)
  97.                 {
  98.                     x=op[top--];
  99.                     update(x,1,1);
  100.                 }
  101.             }
  102.         }
  103.     }
  104.     return 0;
  105. }

E - A Simple Problem with Integers
题意：

  1. N个数字，进行Q次操作。（1 ≤ N,Q ≤ 100000） 两种操作方法：
  2. "C a b c"，从第a到b个数字都加上c
  3. "Q a b",查询从a到b所有数字之和

解题思路：

  1. 线段树的区间更新问题。
  2. 在区间更新的时候，为了节约时间，便利到左右儿子的区间在（x,y)之间的话，暂时不做修改，但是要把这个修改动作存在laz[num]里，下次需要的时候再修改。

代码：

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. #define ll long long  
  7. #define CL(a,b) memset(a,b,sizeof(a))  
  8. #define MAXN 100010  
  10. struct node  
  11. {  
  12.     int l,r;  
  13.     ll s,add;//add为每次加的数  
  14. }t[MAXN*4];  
  15. int hh[MAXN];  
  16. int n,q;  
  17. ll ans;  
  19. void build(int l, int r, int i)  
  20. {  
  21.     t[i].l = l;  
  22.     t[i].r = r;  
  23.     t[i].add = 0;  
  24.     if(l == r) return ;  
  25.     int mid = (l+r)/2;  
  26.     build(l, mid, i*2);  
  27.     build(mid+1, r, i*2+1);  
  28.     t[i].s = t[i*2].s+t[i*2+1].s;  
  29. }  
  31. void update(int l, int r, int add, int i)  
  32. {  
  33.     if(t[i].l>r || t[i].r<l) return ;  
  34.     if(t[i].l>=l && t[i].r<=r)  
  35.     {  
  36.         t[i].s += (t[i].r-t[i].l+1)*add;  
  37.         t[i].add += add;  
  38.         return ;  
  39.     }  
  40.     if(t[i].add)  
  41.     {  
  42.         t[i*2].s += (t[i*2].r-t[i*2].l+1)*t[i].add;  
  43.         t[i*2].add += t[i].add;  
  44.         t[i*2+1].s += (t[i*2+1].r-t[i*2+1].l+1)*t[i].add;  
  45.         t[i*2+1].add += t[i].add;  
  46.         t[i].add = 0;  
  47.     }  
  48.     update(l, r, add, i<<1);  
  49.     update(l, r, add, i<<1|1);  
  50.     t[i].s = t[i*2].s+t[i*2+1].s;  
  51. }  
  53. void query(int l, int r, int i)  
  54. {  
  55.     if(t[i].l>r || t[i].r<l) return ;  
  56.     if(t[i].l>=l && t[i].r<=r)  
  57.     {  
  58.         ans += t[i].s;  
  59.         return ;  
  60.     }  
  61.     if(t[i].add)  
  62.     {  
  63.         t[i*2].s += (t[i*2].r-t[i*2].l+1)*t[i].add;  
  64.         t[i*2].add += t[i].add;  
  65.         t[i*2+1].s += (t[i*2+1].r-t[i*2+1].l+1)*t[i].add;  
  66.         t[i*2+1].add += t[i].add;  
  67.         t[i].add = 0;  
  68.     }  
  69.     query(l, r, i*2);  
  70.     query(l, r, i*2+1);  
  71.     t[i].s = t[i*2].s+t[i*2+1].s;  
  72. }  
  74. int main()  
  75. {  
  76.     int a,b,c;  
  77.     ll k;  
  78.     char ch;  
  79.     while(scanf("%d%d",&n,&q)==2)  
  80.     {  
  81.         for(int i=1; i<=n; i++)  
  82.             scanf("%d",&hh[i]);  
  83.         build(1, n, 1);  
  84.         for(int i=1; i<=n; i++)  
  85.             update(i, i, hh[i], 1);  
  86.         while(q--)  
  87.         {  
  88.             getchar();  
  89.             scanf("%c",&ch);  
  90.             if(ch == 'C')  
  91.             {  
  92.                 scanf("%d%d%d",&a,&b,&c);  
  93.                 update(a, b, c, 1);  
  94.             }  
  95.             if(ch == 'Q')  
  96.             {  
  97.                 ans = 0;  
  98.                 scanf("%d%d",&a,&b);  
  99.                 query(a, b, 1);  
  100.                 cout<<ans<<endl;
  101.             }  
  102.         }  
  103.     }  
  104.     return 0;  
  105. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注