1 条题解
-
0
#include <bits/stdc++.h> using namespace std; using ll = long long; int n, q; ll t[500020]; ll l[500020]; ll r[500020]; ll m[500020]; void build(int idx, int lt, int rt) { l[idx] = lt; r[idx] = rt; m[idx] = (lt + rt) / 2; if (lt < rt) { build(idx << 1, lt, m[idx]); build(idx << 1 | 1, m[idx] + 1, rt); } return; } void add(int idx, int u, ll v) { if (l[idx] == r[idx]) { t[idx] += v; return; } if (m[idx] >= u) { add(idx << 1, u, v); } else { add(idx << 1 | 1, u, v); } t[idx] = t[idx << 1] + t[idx << 1 | 1]; return; } ll query(int idx, int ql, int qr) { if (ql <= l[idx] && qr >= r[idx]) { return t[idx]; } ll sum = 0; if (m[idx] >= ql) { sum += query(idx << 1, ql, qr); } if (m[idx] < qr) { sum += query(idx << 1 | 1, ql, qr); } return sum; } int main() { cin >> n >> q; build(1, 1, n); for (int i = 0; i < q; i++) { int flag = 0; cin >> flag; if (flag == 0) { int a; ll b; cin >> a >> b; add(1, a, b); } else { int a, b; cin >> a >> b; cout << query(1, a, b) << endl; } } return 0; }
- 1
信息
- ID
- 1266
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 上传者