CompetitiveProgrammingAlgos/RangeUpdateQueries.cpp at main · tientnc/CompetitiveProgrammingAlgos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define int ll

int n;
const int Sz = 2e5;
int x[Sz + 1];

struct Dat
{
    int val;
    int lazy;
}st[Sz * 4 + 1];

void down(int id)
{
    int t = st[id].lazy;
    st[id * 2].val += t;
    st[id * 2].lazy += t;
    st[id * 2 + 1].val += t;
    st[id * 2 + 1].lazy += t;
    st[id].lazy = 0;
}

void update(int id, int l, int r, int u, int v, int k)
{
    if(r < u || v < l) return;
    if(u <= l && r <= v)
    {
        st[id].val += k;
        st[id].lazy += k;
        return;
    }
    int mid = (l + r) / 2;
    down(id);
    update(id * 2, l, mid, u, v, k);
    update(id * 2 + 1, mid + 1, r, u, v, k);
    st[id].val = max(st[id * 2].val, st[id * 2 + 1].val);
}

int get(int id, int l, int r, int u, int v)
{
    if(r < u || v < l) return -1e18;
    if(u <= l && r <= v) return st[id].val;
    int mid = (l + r) / 2;
    down(id);
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    int q;
    cin >> q;
    for(int i = 1; i <= n; i++) cin >> x[i];

    int type, a, b, u, k;
    int res;
    while(q--)
    {
        cin >> type;
        if(type == 1)
        {
            cin >> a >> b >> u;
            update(1, 1, n, a, b, u);
        }
        else
        {
            cin >> k;
            res = get(1, 1, n, k, k);
            res += x[k];
            cout << res << "\n";
        }
    }
}