P3372 【模板】线段树 1 (区间查询)

超、凢脫俗 2023-08-17 15:41 130阅读 0赞

P3372 【模板】线段树 1

题目链接:https://www.luogu.org/problem/P3372

题目:

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入 #1

  1. 5 5
  2. 1 5 4 2 3
  3. 2 2 4
  4. 1 2 3 2
  5. 2 3 4
  6. 1 1 5 1
  7. 2 1 4

输出 #1

  1. 11
  2. 8
  3. 20

说明/提示

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

(数据已经过加强^_^,保证在int64/long long数据范围内)

样例说明:

1705372-20190904001921435-676193346.png

  1. //
  2. // Created by hanjinyu on 19-9-2.
  3. //
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn=1e6+10;
  8. int input[maxn];
  9. struct Node{
  10. ll left;
  11. ll right;
  12. ll num;
  13. ll lazy;
  14. }tree[maxn*4];
  15. void PushUp(int root)
  16. {
  17. tree[root].num=tree[root<<1].num+tree[root<<1|1].num;
  18. }
  19. void PushDown(int root)
  20. {
  21. if(tree[root].lazy>0)
  22. {
  23. tree[root<<1].lazy+=tree[root].lazy;
  24. tree[root<<1|1].lazy+=tree[root].lazy;
  25. tree[root<<1].num+=tree[root].lazy*(tree[root<<1].right-tree[root<<1].left+1);
  26. tree[root<<1|1].num+=tree[root].lazy*(tree[root<<1|1].right-tree[root<<1|1].left+1);
  27. tree[root].lazy=0;
  28. }
  29. }
  30. void Build(int root,int l,int r)
  31. {
  32. tree[root].left=l;
  33. tree[root].right=r;
  34. if(l==r)
  35. {
  36. tree[root].num=input[l];
  37. return;
  38. }
  39. int mid=(l+r)>>1;
  40. Build(root<<1,l,mid);
  41. Build(root<<1|1,mid+1,r);
  42. PushUp(root);
  43. }
  44. void change(int root,int l,int r,int k)
  45. {
  46. if(tree[root].left>=l&&tree[root].right<=r)
  47. {
  48. tree[root].num+=k*(tree[root].right-tree[root].left+1);
  49. tree[root].lazy+=k;
  50. return;
  51. }
  52. PushDown(root);
  53. if(l<=tree[root<<1].right)
  54. change(root<<1,l,r,k);
  55. if(r>=tree[root<<1|1].left)
  56. change(root<<1|1,l,r,k);
  57. PushUp(root);
  58. }
  59. ll Q(int root,int l,int r)
  60. {
  61. ll ans=0;
  62. if(tree[root].left>=l&&tree[root].right<=r)
  63. {
  64. return tree[root].num;
  65. }
  66. PushDown(root);
  67. if(l<=tree[root<<1].right)
  68. ans+=Q(root<<1,l,r);
  69. if(r>=tree[root<<1|1].left)
  70. ans+=Q(root<<1|1,l,r);
  71. return ans;
  72. }
  73. int main()
  74. {
  75. int n,m;
  76. scanf("%d%d",&n,&m);
  77. for(int i=1;i<=n;i++)
  78. {
  79. scanf("%d",&input[i]);
  80. }
  81. Build(1,1,n);
  82. int a,x,y,k;
  83. for(int i=0;i<m;i++)
  84. {
  85. scanf("%d",&a);
  86. if(a==1)
  87. {
  88. scanf("%d%d%d",&x,&y,&k);
  89. change(1,x,y,k);
  90. }
  91. else if(a==2)
  92. {
  93. scanf("%d%d",&x,&y);
  94. printf("%lld\n",Q(1,x,y));
  95. }
  96. }
  97. return 0;
  98. }

转载于:https://www.cnblogs.com/Vampire6/p/11456589.html

发表评论

表情:
评论列表 (有 0 条评论,130人围观)

还没有评论,来说两句吧...

相关阅读