Editorial for Bedao Mini Contest 05 - BUILDING
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; const string filename = "BUILDING"; #define int long long int n, q; int a[100001], b[100001]; int BIT[100001]; void upd(int x, int val) { for(;x <= 100000; x += x & (-x)) BIT[x] += val; } int query(int x) { int ans = 0; for(;x > 0; x -= x & (-x)) ans += BIT[x]; return ans; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen( (filename + ".inp").c_str(), "r", stdin); freopen( (filename + ".out").c_str(), "w", stdout); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n - 1; i++) { b[i] = abs(a[i + 1] - a[i]); upd(i, b[i]); } cin >> q; while (q--) { int t; cin >> t; if (t == 1) { int p, x; cin >> p >> x; a[p] = x; if (p > 1) { upd(p - 1, -b[p - 1]); b[p - 1] = abs(a[p] - a[p - 1]); upd(p - 1, b[p - 1]); } if (p < n) { upd(p, -b[p]); b[p] = abs(a[p + 1] - a[p]); upd(p, b[p]); } } else { int l, r; cin >> l >> r; cout << query(r - 1) - query(l - 1) << ' '; } } }
Comments