Untitled
unknown
c_cpp
a year ago
4.3 kB
2
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second struct segtree { struct node { int ch, nch; }; vt<node> tree; int size; node zero = {0, 0}; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, zero); } void build(vt<int> &a, int x, int lx, int rx) { if (rx == lx + 1) { if (lx < size) { if (lx % 2 == 0) { tree[x].ch = a[lx]; // tree[x].nch = 0; } else { // tree[x].ch = 0; tree[x].nch = a[lx]; } // сout << lx << ' ' << rx << endl; } } else { int m = (lx + rx) / 2; build(a, 2 * x + 1, lx, m); build(a, 2 * x + 2, m, rx); tree[x].ch = tree[2 * x + 1].ch + tree[2 * x + 2].ch; tree[x].nch = tree[2 * x + 1].nch + tree[2 * x + 2].nch; } } void build(vt<int> &a) { init(sz(a)); build(a, 0, 0, size); } void update(int i, int v, int x, int lx, int rx) { if (rx == lx + 1) { if (i % 2 == 0) { tree[x].ch = v; } else { tree[x].nch = v; } return; } int m = (lx + rx) / 2; if (i < m) { update(i, v, 2 * x + 1, lx, m); } else { update(i, v, 2 * x + 2, m, rx); } tree[x].ch = tree[2 * x + 1].ch + tree[2 * x + 2].ch; tree[x].nch = tree[2 * x + 1].nch + tree[2 * x + 2].nch; } void update(int i, int v) { update(i, v, 0, 0, size); } ll sumch(int l, int r, int x, int lx, int rx) { if (r <= lx || l >= rx) { return 0; } if (lx >= l && rx <= r) { return tree[x].ch; } int m = (lx + rx) / 2; int ans = sumch(l, r, 2 * x + 1, lx, m); int ans1 = sumch(l, r, 2 * x + 2, m, rx); return ans + ans1; } ll sumch(int l, int r) { return sumch(l, r, 0, 0, size); } ll sumnch(int l, int r, int x, int lx, int rx) { if (r <= lx || l >= rx) { return 0; } if (lx >= l && rx <= r) { return tree[x].nch; } int m = (lx + rx) / 2; int ans = sumnch(l, r, 2 * x + 1, lx, m); int ans1 = sumnch(l, r, 2 * x + 2, m, rx); return ans + ans1; } ll sumnch(int l, int r) { return sumnch(l, r, 0, 0, size); } }; void solve() { int n; cin >> n; vt<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } segtree st; st.build(a); // for (auto i : st.tree) { // cout << "{" << i.ch << ", " << i.nch << "}" << ' '; // } // cout << endl; int m; cin >> m; while (m--) { int f; cin >> f; if (f == 0) { int i, j; cin >> i >> j; i--; st.update(i, j); // for (auto e : st.tree) { // cout << "{" << e.ch << ", " << e.nch << "}" << ' '; // } // cout << endl; } else { int l, r; cin >> l >> r; l--; int a1 = st.sumch(l, r); int a2 = st.sumnch(l, r); // cout << a1 << ' ' << a2 << endl; if (l % 2 == 0) cout << a1 - a2 << endl; else cout << a2 - a1 << endl; } } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }