Untitled

 
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;
    }
}