ログイン
新規登録
Summer Camp Problems Selection
Permanent Contest
Home
Tasks
Clar
Submissions
Standings
提出 c7d28001-7a3f-4850-af64-422f10718596
コード
#include<iostream> #include<vector> #define rep(i, n) for (int i = 0; i < n; i++) using namespace std; int main() { int n; cin >> n; int twon = 1; while (twon < n) twon *= 2; vector<int> seg(2 * twon, 0); rep(i, n) cin >> seg[twon + i]; for (int i = twon - 1; i > 0; i--) seg[i] = seg[2 * i] + seg[2 * i + 1]; int q; cin >> q; rep(_, q) { int x, l, r; cin >> x >> l >> r; if (x == 1) { seg[twon + l - 1] = r; int now = (twon + l - 1) / 2; while (now > 0) { seg[now] = seg[2 * now] + seg[2 * now + 1]; now /= 2; } } else { int ans = 0; l += twon - 1; r += twon - 2; while (l <= r) { if (l % 2 == 1) { ans += seg[l]; l++; } if (r % 2 == 0) { ans += seg[r]; r--; } l /= 2; r /= 2; } cout << ans << endl; } } return 0; }
結果
問題
点数
言語
結果
実行時間
メモリ
SegTree - segment tree
100
C++
AC
17 ms
3812 KiB