POJ 3468 A Simple Problem with Integers //线段树的成段更新

迷南。 2022-09-20 15:27 253阅读 0赞

A Simple Problem with Integers

















Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 59046   Accepted: 17974
Case Time Limit: 2000MS

Description

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c“ means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b“ means querying the sum of Aa, Aa+1, … , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

  1. 10 5
  2. 1 2 3 4 5 6 7 8 9 10
  3. Q 4 4
  4. Q 1 10
  5. Q 2 4
  6. C 3 6 3
  7. Q 2 4

Sample Output

  1. 4
  2. 55
  3. 9
  4. 15

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly—2007.11.25, Yang Yi

  1. /*
  2.     区间更新的lazy操作。
  3. */
  4. #include <stdio.h>
  6. struct node
  7. {
  8.     int l, r;
  9.     __int64 sum;
  10.     __int64 lazy;    //当成段更新时，往往不用更新到单个的点。lazy操作大大节省了时间。
  11. }tree[300005];
  12. int h[100005];
  13. __int64 sum;        //int超限
  15. void build(int l, int r, int n)
  16. {
  17.     int mid;
  18.     tree[n].l = l;
  19.     tree[n].r = r;
  20.     tree[n].lazy = 0;    //赋初值
  21.     if(l==r)
  22.     {
  23.         tree[n].sum = h[l];
  24.         return ;
  25.     }
  26.     mid = (l+r)/2;
  27.     build(l, mid, 2*n);
  28.     build(mid+1, r, 2*n+1);
  30.     tree[n].sum = tree[2*n].sum+tree[2*n+1].sum;
  31. }
  32. void add(int l, int r, __int64 k, int n)
  33. {
  34.     int mid;
  35.     if(tree[n].l==l && tree[n].r==r)    //当需要更新的段 与 结点对应的段吻合时，直接把此结点的lazy值更新即可，不需要再向下更新。
  36.     {
  37.         tree[n].lazy += k;
  38.         return;
  39.     }
  41.     tree[n].sum += k*(r-l+1);        //当此区间包含需要更新的区间，但不吻合时，需要向下继续查找，此时需要更新这个父节点的sum值。
  43.     mid = (tree[n].l + tree[n].r)/2;
  44.     if(r <= mid)
  45.         add(l, r, k, 2*n);
  46.     else if(l >=mid+1)
  47.         add(l, r, k, 2*n+1);
  48.     else
  49.     {
  50.         add(l, mid, k, 2*n);
  51.         add(mid+1, r, k, 2*n+1);
  52.     }
  53. }
  54. void qu(int l, int r, int n)
  55. {
  56.     int mid;
  57.     if(tree[n].l==l && tree[n].r==r)
  58.     {
  59.         sum += tree[n].sum + (r-l+1)*tree[n].lazy;    //当查找的段与 此结点的段吻合时，sum 值等于这个结点的sum加上lazy乘区间长度的值。
  60.         return ;
  61.     }
  63.     if(tree[n].lazy!=0 && tree[n].l!=tree[n].r)    //当查找区间为此结点对应区间的子集时，需要将此结点对应的lazy值下放到其子节点，并把此结点的lazy值置为0。
  64.     {
  65.         add(tree[2*n].l, tree[2*n].r, tree[n].lazy, n);
  66.         add(tree[2*n+1].l, tree[2*n+1].r, tree[n].lazy, n);
  67.         tree[n].lazy = 0;
  68.     }
  69.     mid = (tree[n].l + tree[n].r)/2;
  71.     if(l >= mid+1)
  72.         qu(l, r, 2*n+1);
  73.     else if(r <= mid)
  74.         qu(l, r, 2*n);
  75.     else
  76.     {
  77.         qu(l, mid, 2*n);
  78.         qu(mid+1, r, 2*n+1);
  79.     }
  80. }
  82. int main()
  83. {
  84.     int n, q;
  85.     int i;
  86.     int a, b, c;
  87.     char ch[10];
  89.     scanf("%d%d", &n, &q);
  90.     for(i=1; i<=n; i++)
  91.         scanf("%d", &h[i]);
  93.     build(1, n, 1);
  94.     while(q--)
  95.     {
  96.         scanf("%s", ch);
  97.         if(ch[0]=='Q')
  98.         {
  99.             scanf("%d%d", &a, &b);
  100.             sum = 0;
  101.             qu(a, b, 1);
  102.             printf("%I64d\n", sum);
  103.         }
  104.         else
  105.         {
  106.             scanf("%d%d%d", &a, &b, &c);
  107.             add(a, b, c, 1);
  108.         }
  109.     }
  110.     return 0;
  111. }

发表评论

表情：
评论列表 （有 0 条评论，253人围观）

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

相关阅读