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
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
vector<i64> A(N + 1);
rep(i,0,N) {
cin >> A[i];
}
vector<std::tuple<int, int, int>> B(Q);
rep(i,0,B.size()) {
int a, b, c;
cin >> a >> b >> c;
B[i] = { a, b, c };
}
const int Qsq = 2048;
const int Qsh = 11;
int Qsz = (Q + Qsq - 1) / Qsq;
std::bitset<505050> s;
std::bitset<505050> t;
vector<i64> idx(N + 1, 0);
vector<i64> Comp(Qsq * 2, 0);
for(int qi = 0; qi < Qsz; qi++) {
int start = qi << Qsh;
int end = std::min(Q, (qi + 1) << Qsh);
s = 0;
t = 0;
for(int i = start; i < end; i++) {
int a, b, c;
std::tie(a, b, c) = B[i];
if(a == 0) {
s.set(b);
t.set(b);
}
else {
s.set(b);
s.set(c);
}
}
Comp.assign(Qsq * 2, 0);
Comp[0] += A[0];
for(int i = 1;i < N + 1;i++) {
idx[i] = idx[i - 1];
if(t[i - 1] || s[i]) {
idx[i]++;
}
Comp[idx[i]] += A[i];
}
for(int i = start; i < end; i++) {
int a, b, c;
std::tie(a, b, c) = B[i];
if(a == 0) {
A[b] += c;
Comp[idx[b]] += c;
}
else {
i64 sum = 0;
for(int j = idx[b]; j < idx[c]; j++) {
sum += Comp[j];
}
cout << sum << "\n";
}
}
}
}
|
