CodeForces 315B(线段树+区间更新)

桃扇骨 2022-06-06 04:50 316阅读 0赞

问题描述:

Sereja has got an array, consisting of n integers, a1, a2, …, an. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:

  1. Make vi-th array element equal to xi. In other words, perform the assignment avi = xi.
  2. Increase each array element by yi. In other words, perform n assignments ai = ai + yi (1 ≤ i ≤ n).
  3. Take a piece of paper and write out the qi-th array element. That is, the element aqi.

Help Sereja, complete all his operations.

Input

The first line contains integers n, m (1 ≤ n, m ≤ 105). The second line contains nspace-separated integers a1, a2, …, an (1 ≤ ai ≤ 109) — the original array.

Next m lines describe operations, the i-th line describes the i-th operation. The first number in the i-th line is integer ti (1 ≤ ti ≤ 3) that represents the operation type. If ti = 1, then it is followed by two integers vi and xi, (1 ≤ vi ≤ n, 1 ≤ xi ≤ 109). If ti = 2, then it is followed by integer yi (1 ≤ yi ≤ 104). And if ti = 3, then it is followed by integer qi (1 ≤ qi ≤ n).

Output

For each third type operation print value aqi. Print the values in the order, in which the corresponding queries follow in the input.

Example

Input

  1. 10 11
  2. 1 2 3 4 5 6 7 8 9 10
  3. 3 2
  4. 3 9
  5. 2 10
  6. 3 1
  7. 3 10
  8. 1 1 10
  9. 2 10
  10. 2 10
  11. 3 1
  12. 3 10
  13. 3 9

Output

  1. 2
  2. 9
  3. 11
  4. 20
  5. 30
  6. 40
  7. 39

问题分析:线段树的区间更新!

代码如下:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. using namespace std;
  7. const int maxn=1e5+100;
  8. struct note
  9. {
  10.     int l,r,val;
  11. }tree[maxn*4];
  12. int a[maxn];
  14. void build(int root,int ll,int rr)
  15. {
  16.     tree[root].l=ll;
  17.     tree[root].r=rr;
  18.     tree[root].val=0;
  19.     if (ll==rr) {
  20.         tree[root].val=a[ll];
  21.         return ;
  22.     }
  23.     int mid=(tree[root].l+tree[root].r)>>1;
  24.     build(root<<1,ll,mid);
  25.     build(root<<1|1,mid+1,rr);
  26. }
  27. void pushdown(int root)
  28. {
  29.     if (tree[root].val) {
  30.         tree[root<<1].val+=tree[root].val;
  31.         tree[root<<1|1].val+=tree[root].val;
  32.         tree[root].val=0;
  33.     }
  34. }
  35. void update(int root,int l,int r,int cur,int p)
  36. {
  37.     int ll=tree[root].l;
  38.     int rr=tree[root].r;
  39.     if (l<=ll&&r>=rr) {
  40.         if (p==2) tree[root].val+=cur;
  41.         else tree[root].val=cur;
  42.         return ;
  43.     }
  44.     pushdown(root);
  45.     int mid=(ll+rr)>>1;
  46.     if (l<=mid) update(root<<1,l,r,cur,p);
  47.     if (r>mid) update(root<<1|1,l,r,cur,p);
  48. }
  49. int query(int root,int pos)
  50. {
  51.     int l=tree[root].l;
  52.     int r=tree[root].r;
  53.     if (l==r) {
  54.         return tree[root].val;
  55.     }
  56.     pushdown(root);
  57.     int mid=(l+r)>>1;
  58.     if (pos<=mid)
  59.         return query(root<<1,pos);
  60.     else
  61.         return query(root<<1|1,pos);
  62. }
  63. int main()
  64. {
  65.     int n,m;
  66.     while (scanf("%d%d",&n,&m)!=EOF) {
  67.         for (int i=1;i<=n;i++)
  68.             scanf("%d",&a[i]);
  69.         build(1,1,n);
  70.         for (int i=1;i<=m;i++) {
  71.             int t;
  72.             scanf("%d",&t);
  73.             if (t==1) {
  74.                 int pos,x;
  75.                 scanf("%d%d",&pos,&x);
  76.                 update(1,pos,pos,x,1);
  77.             }
  78.             else if (t==2) {
  79.                 int v;
  80.                 scanf("%d",&v);
  81.                 update(1,1,n,v,2);
  82.             }
  83.             else if (t==3) {
  84.                 int pos;
  85.                 scanf("%d",&pos);
  86.                 printf("%d\n",query(1,pos));
  87.             }
  88.         }
  89.     }
  90.     return 0;
  91. }

发表评论

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

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

相关阅读