[关闭]
@wwwqeqeqeqe 2017-03-27T11:54:33.000000Z 字数 2451 阅读 954

寒假训练专题二（线段树）

A

题目大意

先输入一个数T，表示有T组数据。在每组数据中，第一行给出一个数N，表示有N个工兵营地。接着输入N个数，表示第i个工兵营地里有ai个人，然后输入命令，命令的种类一共有四种，分别表示增加，减少人数，查询一个范围内工兵营地的总人数，以及一个结束语句。让你输出每个查询语句中工兵营地的总人数。

解题思路

裸的线段树模板，减少人数可以表示为增加负数的人数。

AC代码

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=1e5+5;
  10. struct node
  11. {
  12.     int l,r,val;
  13. };
  15. int T,N,a[maxn];
  16. char s[15];
  17. node tree[maxn*4];
  19. void pushup(int x)
  20. {
  21.     tree[x].val=tree[x<<1].val+tree[x<<1|1].val;
  22. }
  24. void build(int l,int r,int x,int a[])
  25. {
  26.     tree[x].l=l;
  27.     tree[x].r=r;
  28.     if(l==r)
  29.         tree[x].val=a[l];
  30.     else
  31.     {
  32.         int mid=(l+r)>>1;
  33.         build(l,mid,x<<1,a);
  34.         build(mid+1,r,x<<1|1,a);
  35.         pushup(x);
  36.     }
  37. }
  39. void add(int pos,int v,int x)
  40. {
  41.     if(tree[x].l==tree[x].r)
  42.         tree[x].val+=v;
  43.     else
  44.     {
  45.         int mid=(tree[x].l+tree[x].r)>>1;
  46.         if(pos<=mid)
  47.             add(pos,v,x<<1);
  48.         else
  49.             add(pos,v,x<<1|1);
  50.         pushup(x);
  51.     }
  52. }
  54. int Query(int l,int r,int x)
  55. {
  56.     if(tree[x].l>=l&&tree[x].r<=r)
  57.         return tree[x].val;
  58.     int ans=0;
  59.     int mid=(tree[x].l+tree[x].r)>>1;
  60.     if(l<=mid)
  61.         ans+=Query(l,r,x<<1);
  62.     if(mid<r)
  63.         ans+=Query(l,r,x<<1|1);
  64.     return ans;
  65. }
  67. int main()
  68. {
  69.     int z,y;
  70.     scanf("%d",&T);
  71.     int casee=0;
  72.     while(T--)
  73.     {
  74.         memset(tree,0,sizeof(tree));
  75.         memset(a,0,sizeof(a));
  76.         scanf("%d",&N);
  77.         for(int i=1;i<=N;i++)
  78.             scanf("%d",&a[i]);
  79.         build(1,N,1,a);
  80.         printf("Case %d:\n",++casee);
  81.         while(~scanf("%s",s))
  82.         {
  83.             if(s[0]=='E')
  84.                 break;
  85.             else if(s[0]=='Q')
  86.             {
  87.                 scanf("%d%d",&z,&y);
  88.                 printf("%d\n",Query(z,y,1));
  89.             }
  90.             else if(s[0]=='A')
  91.             {
  92.                 scanf("%d%d",&z,&y);
  93.                 add(z,y,1);
  94.             }
  95.             else if(s[0]=='S')
  96.             {
  97.                 scanf("%d%d",&z,&y);
  98.                 add(z,-y,1);
  99.             }
  100.         }
  101.     }
  102.     return 0;
  103. }

B

题目大意

先给你N个数，表示气球的总数，在接下来的若干行中，输入两个数a和b，表示从第a个气球到第b个气球每个气球上了一次颜色，最后输出每个气球一共被上了几次颜色。

解题思路

可以通过线段树解决这个问题。在进行上色的过程中，通过判断左右边界是否相等来进行数据增加记录，在mid左边就查找x*2，右边的就查找x*2+1，最后查找的过程同样如此，最后找到每个气球被上色的数量。

AC代码

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=1e5+5;
  10. struct node
  11. {
  12.     int l,r,val;
  13. };
  15. node tree[maxn*4];
  16. int N,t;
  18. void build(int l,int r,int x)
  19. {
  20.     tree[x].l=l;
  21.     tree[x].r=r;
  22.     tree[x].val=0;
  23.     if(l!=r)
  24.     {
  25.         int mid=(l+r)>>1;
  26.         build(l,mid,x<<1);
  27.         build(mid+1,r,x<<1|1);
  28.     }
  29. }
  31. void add(int l,int r,int x)
  32. {
  33.     if(tree[x].l==l&&tree[x].r==r)
  34.         tree[x].val++;
  35.     else
  36.     {
  37.         int mid=(tree[x].l+tree[x].r)>>1;
  38.         if(l<=mid&&r>mid)
  39.         {
  40.              add(l,mid,x<<1);
  41.              add(mid+1,r,x<<1|1);
  42.         }
  43.         else
  44.         {
  45.             if(r<=mid)
  46.                 add(l,r,x<<1);
  47.             else
  48.                 add(l,r,x<<1|1);
  49.         }
  50.     }
  51. }
  53. int Query(int pos,int x)
  54. {
  55.     t+=tree[x].val;
  56.     if(tree[x].l!=tree[x].r)
  57.     {
  58.         int mid=tree[x].l+tree[x].r>>1;
  59.         if(pos<=mid)
  60.             Query(pos,x<<1);
  61.         else
  62.             Query(pos,x<<1|1);
  63.     }
  64.     return t;
  65. }
  67. int main()
  68. {
  69.     int a,b;
  70.     while(~scanf("%d",&N)&&N)
  71.     {
  72.         memset(tree,0,sizeof(tree));
  73.         build(1,N,1);
  74.         for(int i=0; i<N; i++)
  75.         {
  76.             scanf("%d%d",&a,&b);
  77.             add(a,b,1);
  78.         }
  79.         for(int i=1;i<N;i++)
  80.         {
  81.             t=0;
  82.             printf("%d ",Query(i,1));
  83.         }
  84.         t=0;
  85.         printf("%d\n",Query(N,1));
  86.     }
  87.     return 0;
  88. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注