C - Paired Parentheses

https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_c

解法

対応の取れた括弧列で、二点の括弧を入れ替えることを考える。

すると、端以外の括弧を入れ替えた場合、操作後も対応が取れている事が言える。

よって、端を除く2n-2個でa,bを偶数個選び合計を最大にする問題となった。

ここで、最初にすべてbを選び、その内のいくつかをaへ変えることを考える。

a-bの差分が正のものをすべて選べたら、それは間違いなく答えとなる。

差分が正となる物が奇数個ある場合は、最小の+を一つ諦めるか、最大の-を一つ選ぶ必要がある。

最大の負の数と、最小の正の数の判定はセグ木を二つ用意すればできる

後は常に正の差分の合計を持つようにすればよい。

https://atcoder.jp/contests/cf17-tournament-round1-open/submissions/4742394

struct Monoid {
    ll i, v;
    Monoid(ll i, ll v) : i(i), v(v) {}
};
#define segMinl [](Monoid a,Monoid b){return a.v <= b.v ? a : b;} , Monoid(-1,MAX(ll))
#define segMinr [](Monoid a,Monoid b){return a.v < b.v ? a : b;} , Monoid(-1,MAX(ll))
#define segMaxl [](Monoid a,Monoid b){return a.v >= b.v ? a : b;} , Monoid(-1,MIN(ll))
#define segMaxr [](Monoid a,Monoid b){return a.v > b.v ? a : b;} , Monoid(-1,MIN(ll))
#define segSum  [](Monoid a,Monoid b){return Monoid(a.i+b.i,a.v+b.v);} , Monoid(0,0)

struct SegmentTree {
    using func=function<Monoid(Monoid, Monoid)>;
    int n;
    vector<Monoid> seg;
    const func f;
    const Monoid e;
    SegmentTree(int len, func f, const Monoid e) : f(f), e(e) {
        n = 1;
        while (n < len)n *= 2;
        seg.assign(2 * n - 1, e);
    }
    SegmentTree(vi dat, const func f, const Monoid e) : f(f), e(e) {
        n = 1;
        int asz = dat.size();
        while (n < asz)n *= 2;
        seg.assign(2 * n - 1, e);
        rep(i, asz) seg[i + n - 1] = Monoid(i, dat[i]);
        rer(i, n - 2)seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]);
    }
    void update(int k, int v) {
        seg[k + n - 1] = Monoid(k, v);
        k += n - 1;
        while (k) {
            k = (k - 1) / 2;
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }
    void del(int k) {
        update(k, e.v);
    }
    void add(int k, int v) {
        update(k, v + seg[k + n - 1].v);
    }
    Monoid query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)return e;
        else if (a <= l && r <= b)return seg[k];
        else {
            Monoid sl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            Monoid sr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return f(sl, sr);
        }
    }
    Monoid get(int a = 0, int b = -1) {
        if (b == -1)b = n;
        return query(a, b, 0, 0, n);
    }
    int geti(int a = 0, int b = -1) {
        return get(a, b).i;
    }
    ll getv(int a = 0, int b = -1) {
        return get(a, b).v;
    }
    int operator()(int a = 0, int b = -1) {
        return get(a, b).v;
    }
    Monoid operator[](int k) const {
        return seg[k + n - 1];
    }
};

void solve() {
    cin >> n >> q;
    n *= 2;
    na(a, n);
    na(b, n);
    //基本b
    rep(i, n)c += a[i] - b[i];
    SegmentTree minu(k5*2, segMaxl);
    SegmentTree plu(k5*2, segMinl);
    int pc = 0;
    int base = 0;
    int pad = 0;
    int add = 0;
    add = a[0] + a[n - 1];
    rep(i, 1, n - 1) {
        base += b[i];
        if (c[i] < 0)minu.update(i, c[i]);
        else {
            plu.update(i, c[i]);
            pc++;
            pad += c[i];
        }
    }
    while (q--) {
        din(p, x, y);
        p--;
        if (p == 0 || p == n - 1) {
            add -= a[p];
            a[p] = x;
            b[p] = y;
            add += a[p];
        } else {
            base -= b[p];
            a[p] = x;
            b[p] = y;
            base += b[p];
            int nc = a[p] - b[p];
            //-に入ってる
            if (c[p] < 0) {
                //-から消す
                if (nc >= 0) {
                    pad += nc;
                    plu.update(p, nc);
                    minu.del(p);
                    pc++;
                } else {
                    minu.update(p, nc);
                }
            } else {
                pad -= c[p];
                if (nc < 0) {
                    minu.update(p, nc);
                    plu.del(p);
                    pc--;
                } else {
                    plu.update(p, nc);
                    pad += nc;
                }
            }
            c[p] = a[p] - b[p];
        }
        if (pc % 2 == 0) {
            cout << add + pad + base << endl;
        } else {
            int res = -linf;
            //+を一つ消す
            chma(res, add + pad - plu() + base);
            //-を一つ取る
            chma(res, add + pad + minu() + base);
            cout << res << endl;
        }
    }

}