首页 > 代码库 > xianduanshu

xianduanshu

2024-07-18 07:38:33   218人阅读

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
 


 

这是我做的第一题的线段树题，我也是参照别的神牛的代码才敲出来的

没办法，第一次弄完全没头绪，下面就贴出两种代码

 

第一：中规中矩

没什么好讲的，比较容易看懂

 

[cpp] view plaincopyprint?
  1. <PRE class=cpp name="code">#include"stdio.h"  
  2. #include"string.h"   
  3.   
  4.   
  5. struct seg  
  6. {  
  7.     int l;  
  8.     int r;  
  9.     int n;  
  10. } T[150011];  
  11.   
  12.   
  13. void build(int l,int r,int k)  
  14. {  
  15.     int mid;  
  16.     if(l==r)  
  17.     {  
  18.         T[k].l=l;  
  19.         T[k].r=r;  
  20.         T[k].n=0;  
  21.         return ;  
  22.     }  
  23.   
  24.   
  25.     mid=(l+r)/2;  
  26.     T[k].l=l;  
  27.     T[k].r=r;  
  28.     T[k].n=0;  
  29.     build(l,mid,2*k);  
  30.     build(mid+1,r,2*k+1);  
  31. }  
  32.   
  33.   
  34. void insert(int n,int d,int k)  
  35. {  
  36.     int mid;  
  37.     if(T[k].l==T[k].r&&T[k].l==d)  
  38.     {  
  39.         T[k].n+=n;  
  40.         return ;  
  41.     }  
  42.     mid=(T[k].l+T[k].r)>>1;  
  43.     if(d<=mid)   insert(n,d,2*k);  
  44.     else        insert(n,d,2*k+1);  
  45.     T[k].n=T[2*k].n+T[2*k+1].n;  
  46. }  
  47.   
  48.   
  49. int ans;  
  50. void search(int l,int r,int k)  
  51. {  
  52.     int mid;  
  53.     //printf("l = %d,r = %d\n",l);   
  54.     if(T[k].l==l&&T[k].r==r)  
  55.     {  
  56.         ans+=T[k].n;  
  57.         return ;  
  58.     }  
  59.     mid=(T[k].l+T[k].r)>>1;  
  60.     if(r<=mid)       search(l,r,2*k);  
  61.     else if(l>mid)   search(l,r,2*k+1);  
  62.     else  
  63.     {  
  64.         search(l,mid,2*k);  
  65.         search(mid+1,r,2*k+1);  
  66.     }  
  67. }  
  68.   
  69.   
  70. int main()  
  71. {  
  72.     int Case,TT;  
  73.     int n;  
  74.     int i;  
  75.     int temp;  
  76.     char str[11];  
  77.     int a,b;  
  78.     scanf("%d",&TT);  
  79.     for(Case=1; Case<=TT; Case++)  
  80.     {  
  81.         scanf("%d",&n);  
  82.   
  83.         build(1,n,1);  
  84.         for(i=1; i<=n; i++)  
  85.         {  
  86.             scanf("%d",&temp);  
  87.             insert(temp,i,1);  
  88.         }  
  89.   
  90.         printf("Case %d:\n",Case);  
  91.   
  92.         while(scanf("%s",str),strcmp(str,"End"))  
  93.         {  
  94.             scanf("%d%d",&a,&b);  
  95.             if(strcmp(str,"Add")==0)        insert(b,a,1);  
  96.             else if(strcmp(str,"Sub")==0)   insert(-b,a,1);  
  97.             else  
  98.             {  
  99.                 ans=0;  
  100.                 search(a,b,1);  
  101.                 printf("%d\n",ans);  
  102.             }  
  103.         }  
  104.     }  
  105.     return 0;  
  106. }  


联系
我们