2018年3月3日

[HNOI2011]括号修复 题解

[HNOI2011]括号修复 题解

题目地址：洛谷：【P3215】[HNOI2011]括号修复 – 洛谷、BZOJ：Problem 2329. — [HNOI2011]括号修复

题目描述

一个合法的括号序列是这样定义的：

  1. 空串是合法的。
  2. 如果字符串 S 是合法的，则(S)也是合法的。
  3. 如果字符串 A 和 B 是合法的，则 AB 也是合法的。

现在给你一个长度为 N 的由‘(‘和‘)’组成的字符串，位置标号从 1 到 N。对这个字符串有下列四种操作：

  1. Replace a b c：将[a,b]之间的所有括号改成 c。例如：假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。
  2. Swap a b：将[a,b]之间的字符串翻转。例如：假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。
  3. Invert a b：将[a,b]之间的‘(’变成‘)’,‘)’变成‘(’。例如：假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。
  4. Query a b：询问[a,b]之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的‘(’变成‘)’或‘)’变成‘(’。注意执行操作 Query 并不改变当前的括号序列。例如：假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 2，因为要将位置 5 的‘)’变成‘(’并将位置 6 的‘(’变成‘)’。

输入输出格式

输入格式：
从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示字符串的长度和将执行的操作个数。第二行是长度为N的初始字符串S。接下来的M行是将依次执行的M个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。

输出格式：
输出文件 output.txt 包含 T 行，其中 T 是输入的将执行的 M 个操作中 Query 操作出现的次数。Query 操作的每次出现依次对应输出文件中的一行，该行只有一个非负整数，表示执行对应 Query 操作的结果，即：所指字符串至少要改变多少位才能变成合法的括号序列。输入数据保证问题有解。

输入输出样例

输入样例#1：

4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4

输出样例#1：

1
2

说明

样例解释：
输入中有2个Query操作，所以输出有2行。执行第一个Query操作时的括号序列为))((，因改变第1位可使[1,2]之间的字符串变成合法的括号序列，故输出的第一行为1。执行第二个Query操作时的括号序列为)((),因要改变第1位和第2位才能使[1,4]之间的字符串变成合法的括号序列，故输出的第二行为2。

数据范围：
30%的数据满足N,M≤3000。100%的数据满足N,M≤100000。

题解

从操作4入手，问题转化

首先我们考虑一个问题，给一个串，怎么知道它最少改变多少位才能合法。我们发现，去除配对成功的括号后，剩余不能配对的串一定长这样：))))(((。假如这里面有a个)，b个(，答案应该是\lceil \frac{a}{2} \rceil + \lceil \frac{b}{2} \rceil。对于括号序列，我们可以用1代替(，用-1代替)，这样求个和就会自动消除那些已经匹配的括号。而a就是最小前缀和，b就是最大后缀和。
我们可以用splay维护区间和，区间最大前缀和，区间最大后缀和。有了这些信息，最小前缀和可以通过和-最大后缀和求得。

标记和标记的apply

翻转标记和替换标记很常规，可以参考[NOI2005]维护数列 题解 | KSkun’s Blog。
至于invert标记，这个会比较麻烦。它会使总和变为相反数，最大前缀和变为最小前缀和，最大后缀和变为最小后缀和。但是我们可以用总和-最小前缀求得最大后缀，以此类推，这个标记就也不是问题了。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'R' || c == 'S' || c == 'I' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

inline bool isbracket(char c) {
    return c == '(' || c == ')';
}

inline char readbracket() {
    char c;
    while(!isbracket(c = fgc()));
    return c;
}

// variables

const int MAXN = 100005, INF = 1e9;

int n, m, at, bt, ct, a[MAXN];
char op;

// splay

struct Node {
    int val, sum, mxl, mxr, siz;
    bool rev, rep, inv;
    int ch[2], fa;
} tr[MAXN]; 
int tot = 0, sta[MAXN], stop = 0, rt = 0;

inline void update(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    tr[p].siz = tr[lch].siz + tr[rch].siz + 1;
    tr[p].sum = tr[lch].sum + tr[rch].sum + tr[p].val;
    tr[p].mxl = std::max(tr[lch].mxl, tr[lch].sum + tr[p].val + tr[rch].mxl);
    tr[p].mxr = std::max(tr[rch].mxr, tr[rch].sum + tr[p].val + tr[lch].mxr);
}

inline void pushdown(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[p].rep) {
        tr[p].rep = tr[p].rev = tr[p].inv = false;
        if(lch) {
            tr[lch].rep = true;
            tr[lch].rev = tr[lch].inv = false;
            tr[lch].val = tr[p].val;
            tr[lch].sum = tr[p].val * tr[lch].siz;
            tr[lch].mxl = tr[lch].mxr = std::max(0, tr[lch].sum);
        }
        if(rch) {
            tr[rch].rep = true;
            tr[rch].rev = tr[rch].inv = false;
            tr[rch].val = tr[p].val;
            tr[rch].sum = tr[p].val * tr[rch].siz;
            tr[rch].mxl = tr[rch].mxr = std::max(0, tr[rch].sum);
        }
    }
    if(tr[p].rev) {
        tr[p].rev = false;
        if(lch) {
            std::swap(tr[lch].mxl, tr[lch].mxr);
            std::swap(tr[lch].ch[0], tr[lch].ch[1]);
            tr[lch].rev = !tr[lch].rev;
        }
        if(rch) {
            std::swap(tr[rch].mxl, tr[rch].mxr);
            std::swap(tr[rch].ch[0], tr[rch].ch[1]);
            tr[rch].rev = !tr[rch].rev;
        }
    }
    if(tr[p].inv) {
        tr[p].inv = false;
        if(lch) {
            int omxl = tr[lch].mxl;
            tr[lch].inv = !tr[lch].inv;
            tr[lch].mxl = std::max(0, -(tr[lch].sum - tr[lch].mxr));
            tr[lch].mxr = std::max(0, -(tr[lch].sum - omxl));
            tr[lch].sum = -tr[lch].sum;
            tr[lch].val = -tr[lch].val;
        }
        if(rch) {
            int omxl = tr[rch].mxl;
            tr[rch].inv = !tr[rch].inv;
            tr[rch].mxl = std::max(0, -(tr[rch].sum - tr[rch].mxr));
            tr[rch].mxr = std::max(0, -(tr[rch].sum - omxl));
            tr[rch].sum = -tr[rch].sum;
            tr[rch].val = -tr[rch].val;
        }
    }
}

inline int newnode() {
    int p;
    if(stop > 0) {
        p = sta[--stop];
    } else {
        p = ++tot;
    } 
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int a) {
    sta[stop++] = a;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void rotate(int p) { // p is child
    bool type = !isleft(p);
    int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[fa].ch[type] = tr[p].ch[!type];
    tr[p].ch[!type] = fa;
    tr[tr[fa].ch[type]].fa = fa;
    if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[p].fa = tr[fa].fa;
    tr[fa].fa = p;
    update(fa);
    update(p);
}

inline void splay(int p, int tar) {
    for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
        if(tr[tr[p].fa].fa != tar) {
            rotate(isleft(fa) == isleft(p) ? fa : p);
        }
    }
    if(!tar) rt = p;
}

inline int find(int p, int rk) {
    pushdown(p);
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[lch].siz + 1 == rk) return p;
    else if(tr[lch].siz >= rk) return find(lch, rk);
    else return find(rch, rk - tr[lch].siz - 1);
}

inline int build(int fa, int l, int r) {
    if(l > r) return 0;
    int p = newnode();
    if(l == r) {
        tr[p].siz = 1;
        tr[p].val = tr[p].sum = a[l];
        tr[p].mxl = tr[p].mxr = std::max(0, a[l]);
        tr[p].fa = fa;
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].ch[0] = build(p, l, mid - 1);
    tr[p].ch[1] = build(p, mid + 1, r);
    tr[p].fa = fa;
    tr[p].val = a[mid];
    update(p);
    return p;
}

inline void replace(int x, int len, int val) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    tr[p].val = val;
    tr[p].rep = true;
    tr[p].sum = val * tr[p].siz;
    tr[p].mxl = tr[p].mxr = std::max(0, tr[p].sum);
    update(b);
    update(a);
}

inline void reverse(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    if(!tr[p].rep) {
        tr[p].rev = !tr[p].rev;
        std::swap(tr[p].mxl, tr[p].mxr);
        std::swap(tr[p].ch[0], tr[p].ch[1]);
        update(b);
        update(a);
    }
}

inline void invert(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    int omxl = tr[p].mxl;
    tr[p].inv = !tr[p].inv;
    tr[p].mxl = std::max(0, -(tr[p].sum - tr[p].mxr));
    tr[p].mxr = std::max(0, -(tr[p].sum - omxl));
    tr[p].sum = -tr[p].sum;
    tr[p].val = -tr[p].val;
}

inline int query(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    return (tr[p].mxr - tr[p].sum + 1) / 2 + (tr[p].mxr + 1) / 2;
}

int main() {
    n = readint();
    m = readint();
    for(int i = 1; i <= n; i++) {
        a[i + 1] = readbracket() == '(' ? 1 : -1;
    }
    rt = build(0, 1, n + 2);
    n += 2;
    while(m--) {
        op = readop();
        at = readint();
        bt = readint();
        if(op == 'R') {
            ct = readbracket() == '(' ? 1 : -1;
            replace(at, bt - at + 1, ct);
        }
        if(op == 'S') {
            reverse(at, bt - at + 1);
        }
        if(op == 'I') {
            invert(at, bt - at + 1);
        }
        if(op == 'Q') {
            printf("%d\n", query(at, bt - at + 1));
        }
    }
    return 0;
}
Author:
Filed Under: 题解, 省选, 算法
Tags: , ,

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。