[关闭]
@Chilling 2017-02-16T17:58:28.000000Z 字数 2770 阅读 871

HDU-1166: 敌兵布阵

线段树 树状数组


Problem Description

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

Input

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

Output

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

Sample Output

Case 1:
6
33
59

分析:没有什么好分析的……线段树单点更新,求区间和,也可以用树状数组来做。


线段树

  1. #include<stdio.h>
  2. #define maxn 50005
  3. int a[maxn];
  4. struct node
  5. {
  6. int l,r,sum;
  7. }s[4*maxn];
  8. void build(int id,int l,int r)
  9. {
  10. s[id].l=l;
  11. s[id].r=r;
  12. if(l==r)
  13. s[id].sum=a[l];
  14. else
  15. {
  16. int mid=(l+r)/2;
  17. build(id*2,l,mid);
  18. build(id*2+1,mid+1,r);
  19. s[id].sum=s[id*2].sum+s[id*2+1].sum;
  20. }
  21. }
  22. void rep(int id,int x,int y)
  23. {
  24. if(s[id].l==s[id].r)
  25. s[id].sum+=y;
  26. else
  27. {
  28. int mid=(s[id].l+s[id].r)/2;
  29. if(x<=mid)
  30. rep(id*2,x,y);
  31. else
  32. rep(id*2+1,x,y);
  33. s[id].sum=s[id*2].sum+s[id*2+1].sum;
  34. }
  35. }
  36. int sum(int id,int l,int r)
  37. {
  38. if(l<=s[id].l&&s[id].r<=r)
  39. return s[id].sum;
  40. int mid=(s[id].l+s[id].r)/2;
  41. if(r<=mid)
  42. return sum(id*2,l,r);
  43. else if(l>mid)
  44. return sum(id*2+1,l,r);
  45. else
  46. return sum(id*2,l,r)+sum(id*2+1,l,r);
  47. }
  48. int main()
  49. {
  50. int t,x,y,n,tt=0;
  51. char ch[9];
  52. scanf("%d",&t);
  53. while(t--)
  54. {
  55. tt++;
  56. scanf("%d",&n);
  57. for(int i=1;i<=n;i++)
  58. scanf("%d",&a[i]);
  59. build(1,1,n);
  60. printf("Case %d:\n",tt);
  61. while(scanf("%s",ch)!=EOF)
  62. {
  63. if(ch[0]=='E') break;
  64. else
  65. {
  66. scanf("%d%d",&x,&y);
  67. if(ch[0]=='A')
  68. rep(1,x,y);
  69. if(ch[0]=='S')
  70. rep(1,x,-y);
  71. if(ch[0]=='Q')
  72. printf("%d\n",sum(1,x,y));
  73. }
  74. }
  75. }
  76. return 0;
  77. }

树状数组

  1. #include<stdio.h>
  2. #include<string.h>
  3. int a[50005],n;
  4. int lowbit(int x)
  5. {
  6. return x&(-x);
  7. }
  8. void change(int x,int y)
  9. {
  10. for(int i=x;i<=n;i+=lowbit(i))
  11. a[i]+=y;
  12. }
  13. int query(int x)
  14. {
  15. int sum=0;
  16. for(int i=x;i>0;i-=lowbit(i))
  17. sum+=a[i];
  18. return sum;
  19. }
  20. int main()
  21. {
  22. int t,i,m,j,x,y,cnt=0;
  23. char order[11];
  24. scanf("%d",&t);
  25. while(t--)
  26. {
  27. memset(a,0,sizeof(a));
  28. cnt++;
  29. scanf("%d",&n);
  30. for(i=1;i<=n;i++)
  31. {
  32. scanf("%d",&m);
  33. change(i,m); //在位置为i的地方加上x,数组长度为n
  34. }
  35. printf("Case %d:\n",cnt);
  36. while(scanf("%s",order)!=EOF)
  37. {
  38. if(order[0]=='Q')
  39. {
  40. scanf("%d%d",&x,&y);
  41. printf("%d\n",query(y)-query(x-1));
  42. }
  43. if(order[0]=='A')
  44. {
  45. scanf("%d%d",&x,&y);
  46. change(x,y);
  47. }
  48. if(order[0]=='S')
  49. {
  50. scanf("%d%d",&x,&y);
  51. y=-y;
  52. change(x,y);
  53. }
  54. if(order[0]=='E')
  55. break;
  56. }
  57. }
  58. return 0;
  59. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注