比赛 数列操作练习题 评测结果 AAAAAAAAAAAAAAA
题目名称 数列操作A 最终得分 100
用户昵称 rvalue 运行时间 0.172 s
代码语言 C++ 内存使用 0.42 MiB
提交时间 2017-03-18 19:29:19
显示代码纯文本
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. const int INF=0x7FFFFFFF;
  7. const int MAXN=100010;
  8.  
  9. int n;
  10. int m;
  11. int a[MAXN];
  12. int c[MAXN];
  13.  
  14. void Initialize();
  15. int Query(int);
  16. void Add(int,int);
  17. void Build();
  18. int LowBit(int);
  19.  
  20. int Main(){
  21. char buf[10];
  22. int from;
  23. int to;
  24.  
  25. Initialize();
  26. scanf("%d",&m);
  27. for(int i=0;i<m;i++){
  28. scanf("%s",buf);
  29. switch(buf[0]){
  30. case 'A':
  31. scanf("%d%d",&from,&to);
  32. Add(from,to);
  33. break;
  34. case 'S':
  35. scanf("%d%d",&from,&to);
  36. if(from>to)
  37. swap(from,to);
  38. printf("%d\n",Query(to)-Query(from-1));
  39. break;
  40. }
  41. }
  42. return 0;
  43. }
  44.  
  45. void Initialize(){
  46. #ifndef ASC_LOCAL
  47. freopen("shulie.in","r",stdin);
  48. freopen("shulie.out","w",stdout);
  49. #endif
  50. scanf("%d",&n);
  51. for(int i=1;i<=n;i++)
  52. scanf("%d",a+i);
  53. Build();
  54. }
  55.  
  56. void Build(){
  57. for(int i=1;i<=n;i++)
  58. Add(i,a[i]);
  59. }
  60.  
  61. int Query(int x){
  62. int ans=0;
  63. for(int i=x;i>0;i-=LowBit(i))
  64. ans+=c[i];
  65. return ans;
  66. }
  67.  
  68. void Add(int x,int add){
  69. for(int i=x;i<=n;i+=LowBit(i))
  70. c[i]+=add;
  71. }
  72.  
  73. inline int LowBit(int x){
  74. return x&-x;
  75. }
  76.  
  77. int WORKING=Main();
  78. int main(){;}