Untitled
user_9000366
plain_text
a month ago
3.0 kB
3
Indexable
struct item { ll pre, suf, seg, sum; }; struct segtree { int size; vector<item> values; void init(int n) { size = 1; while (size < n)size *= 2; values.resize(2 * size); } // change item NEUTRAl_ELEMENT = {0, 0, 0, 0}; item single(int v) { if (v > 0) { return {v, v, v, v}; } else { return {0, 0, 0, v}; } } item marge(item a, item b) { return { //pre , suf , seg ,sum; max({a.pre, a.sum + b.pre}), max({b.suf, b.sum + a.suf}), max({a.seg, b.seg, a.suf + b.pre}), a.sum + b.sum }; } void build(vector<int> &a, int x, int lx, int rx) { if (rx - lx == 1) { if (lx < sz(a)) values[x] = single(a[lx]); return; } int m = (lx + rx) / 2; build(a, 2 * x + 1, lx, m); build(a, 2 * x + 2, m, rx); values[x] = marge(values[2 * x + 1], values[2 * x + 2]); } void build(vector<int> &a) { build(a, 0, 0, size); } void set(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { values[x] = single(v); return; } int m = (lx + rx) / 2; if (i < m) { set(i, v, 2 * x + 1, lx, m); } else { set(i, v, 2 * x + 2, m, rx); } values[x] = marge(values[2 * x + 1], values[2 * x + 2]); } void set(int i, int v) { set(i, v, 0, 0, size); } item calc(int l, int r, int x, int lx, int rx) { if (lx >= r || l >= rx)return NEUTRAl_ELEMENT; if (lx >= l && rx <= r)return values[x]; int m = (lx + rx) / 2; item s1 = calc(l, r, 2 * x + 1, lx, m); item s2 = calc(l, r, 2 * x + 2, m, rx); return marge(s1, s2); } item calc(int l, int r) { return calc(l, r, 0, 0, size); } }; void go(int tt) { int n, q; cin >> n >> q; vector<int> a(n); for (auto &i: a) { cin >> i; } segtree st1, st2, st3; st1.init(n), st2.init(n), st3.init(n); for (int i = 0; i < n; ++i) { st1.set(i , -1e9); st2.set(i , -1e9); st3.set(i , -1e9); if (a[i] == 0) st1.set(i, 1); else if (a[i] == 1) st2.set(i, 1); else if (a[i] == 2) st3.set(i, 1); } while (q--) { int i, x; cin >> i >> x; --i; st1.set(i, -1e9); st2.set(i, -1e9); st3.set(i, -1e9); a[i] += x; if (a[i] == 0) st1.set(i, 1); else if (a[i] == 1) st2.set(i, 1); else if (a[i] == 2) st3.set(i, 1); cout << max({st1.calc(0, n).seg, st2.calc(0, n).seg, st3.calc(0, n).seg}) << el; } }
Editor is loading...
Leave a Comment