codeforces 315 B.Sereja and Array(线段树区间更新+单点更新+单点询问)

Bertha 。 2022-06-06 03:57 212阅读 0赞

Sereja has got an array, consisting of *n* integers, *a*1, *a*2, ..., *a**n*. 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 *v**i*\-th array element equal to *x**i*. In other words, perform the assignment *a**v**i* = *x**i*.
2.  Increase each array element by *y**i*. In other words, perform *n* assignments *a**i* = *a**i* + *y**i* (1 ≤ *i* ≤ *n*).
3.  Take a piece of paper and write out the *q**i*\-th array element. That is, the element *a**q**i*.

Help Sereja, complete all his operations.

Input

The first line contains integers *n*, *m* (1 ≤ *n*, *m* ≤ 105). The second line contains *n*space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 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 *t**i* (1 ≤ *t**i* ≤ 3) that represents the operation type. If *t**i* = 1, then it is followed by two integers *v**i* and *x**i*, (1 ≤ *v**i* ≤ *n*, 1 ≤ *x**i* ≤ 109). If *t**i* = 2, then it is followed by integer *y**i* (1 ≤ *y**i* ≤ 104). And if *t**i* = 3, then it is followed by integer *q**i* (1 ≤ *q**i* ≤ *n*).

Output

For each third type operation print value *a**q**i*. Print the values in the order, in which the corresponding queries follow in the input.

Example

Input

10 11
    1 2 3 4 5 6 7 8 9 10
    3 2
    3 9
    2 10
    3 1
    3 10
    1 1 10
    2 10
    2 10
    3 1
    3 10
    3 9

Output

2
    9
    11
    20
    30
    40
    39

题解：

题意：

操作1 x y表示将a\[x\]=y

操作2 x 表示全体数列值加上x

操作3 x 表示询问a\[x\]处的值

思路：

比较裸的一道线段树的题，然后这里的区间更新因为是全体更新所以可以偷懒

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    struct node
    {
        int v;
        int tag;
        int l,r;
    }t[100005*4];
    void pushdown(int k)
    {
        if(t[k].tag)
        {
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            if(t[lson].l==t[lson].r)
                t[lson].v+=t[k].tag;
            if(t[rson].l==t[rson].r)
                t[rson].v+=t[k].tag;
            t[k].tag=0;
        }
    }
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag=0;
        if(l==r)
        {
            scanf("%d",&t[k].v);
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void update(int k,int v)
    {
        t[k].v+=v;
        t[k].tag+=v;
    }
    void change(int x,int v,int k)
    {
        if(t[k].l==x&&t[k].r==x)
        {
            t[k].v=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(x<=mid)
            change(x,v,lson);
        else
            change(x,v,rson);
    }
    int query(int x,int k)
    {
        if(t[k].l==x&&t[k].r==x)
        {
            return t[k].v;
        }
        pushdown(k);
        int mid=M;
        if(x<=mid)
            return query(x,lson);
        else
            return query(x,rson);
    }
    int main()
    {
        int i,j,n,m,d,x,y;
        scanf("%d%d",&n,&m);
        Build(1,n,1);
        while(m--)
        {
            scanf("%d",&d);
            if(d==1)
            {
                scanf("%d%d",&x,&y);
                change(x,y,1);
            }
            else if(d==2)
            {
                scanf("%d",&x);
                update(1,x);
            }
            else
            {
                scanf("%d",&x);
                printf("%d\n",query(x,1));
            }
        }
        return 0;
    }