UESTC1546 Bracket Sequence（线段树区间修改）

链接

Bracket Sequence

题解

    只有一种括号，所以很容易用前缀和判断是否合法，方法就是把左括号看作1，右括号看作-1，这样对于一段区间 [ l , r ] [l,r] [l,r]来说，定义前缀和 S [ i ] = ∑ j = 0 i a [ l + i ] S[i] = \sum_{j = 0}^{i}a[l + i] S[i]=∑j=0i​a[l+i]，只要满足

S [ r − l + 1 ] = 0 , S [ i ] ≥ 0 ( i = 0 , 1 , . . . r − l + 1 ) S[r - l + 1] = 0, S[i] \ge 0(i = 0,1,...r - l + 1) S[r−l+1]=0,S[i]≥0(i=0,1,...r−l+1)

即可。

    因此需要维护的信息肯定有区间最小前缀和，但是为了能够将区间之间的信息合并，还需要区间和，为了能处理区间异或操作，还需要最大前缀和。维护三个信息，使用两个 l a z y lazy lazy标记，分别处理区间覆盖和区间异或。两个标记有一个麻烦的事情就是下传标记时候的顺序问题，为了避开这个麻烦，采取这样的措施。如果来了一个覆盖操作，那区间异或的标记肯定直接就没了，这个好处理。如果来了一个异或操作，那么如果这个区间上还有覆盖操作，那就直接把覆盖操作异或，这样不用记录这个异或操作而只有覆盖标记，如果这个区间上没有覆盖操作，那就直接对这个区间进行异或操作，并且打上异或标记，这样这个区间就只有异或标记。通过这样的方式使得一个区间实际上只有一种标记，避免麻烦。

代码

#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i = 1; i <= (n); i++)
#define sqr(x) ((x) * (x))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

const int maxn = 100000 + 100;
// const int maxn = 5;
const int maxm = 20000 + 100;
// const int maxm = 100;
const int maxt = 35 + 2;

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;

const LL unit = 1LL;
const int INF = 0x3f3f3f3f;
const LL Inf = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-8;
const double inf = 1e15;
const double pi = acos(-1.0);
const LL mod = 1000000007;

int n, m, iCase;
int mx[maxn << 2], mi[maxn << 2], sum[maxn << 2];
int cov[maxn << 2], Xor[maxn << 2];
char bra[maxn], opt[10];

inline int idx(char ch)
{
    if(ch == '(')
        return 1;
    return -1;
}

inline void fcover(int l, int r, int rt, int x)
{
    Xor[rt] = 0, cov[rt] = x;
    sum[rt] = (r - l + 1) * x;
    mx[rt] = max(sum[rt], 0);
    mi[rt] = min(sum[rt], 0);
}

inline void fxor(int l, int r, int rt)
{
    sum[rt] = -sum[rt];
    swap(mi[rt], mx[rt]);
    mi[rt] = -mi[rt], mx[rt] = -mx[rt];
    Xor[rt] ^= 1;
}

inline void push_up(int rt)
{
    mx[rt] = max(mx[rt << 1], sum[rt << 1] + mx[rt << 1 | 1]);
    mi[rt] = min(mi[rt << 1], sum[rt << 1] + mi[rt << 1 | 1]);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

inline void push_down(int l, int r, int rt)
{
    int m = (l + r) >> 1;
    if(Xor[rt])
    {
        if(cov[rt])
            cov[rt] *= -1;
        else
            fxor(lson), fxor(rson);
        Xor[rt] = 0;
    }
    if(cov[rt])
    {
        fcover(lson, cov[rt]), fcover(rson, cov[rt]);
        cov[rt] = 0;
    }
}

void build(int l, int r, int rt)
{
    cov[rt] = Xor[rt] = 0;
    if(l == r)
    {
        sum[rt] = idx(bra[l]);
        mx[rt] = max(0, sum[rt]);
        mi[rt] = min(0, sum[rt]);
        return;
    }

    int m = (l + r) >> 1;
    build(lson), build(rson);
    push_up(rt);
}

void cov_change(int L, int R, int x, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        fcover(l, r, rt, x);
        return;
    }

    push_down(l, r, rt);
    int m = (l + r) >> 1;
    if(L <= m)
        cov_change(L, R, x, lson);
    if(R > m)
        cov_change(L, R, x, rson);
    push_up(rt);
}

void xor_change(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        fxor(l, r, rt);
        return;
    }

    push_down(l, r, rt);
    int m = (l + r) >> 1;
    if(L <= m)
        xor_change(L, R, lson);
    if(R > m)
        xor_change(L, R, rson);
    push_up(rt);
}

void query(int L, int R, int l, int r, int rt, int &Sum, int &Min)
{
    if(L <= l && r <= R)
    {
        Sum = sum[rt], Min = mi[rt];
        return;
    }

    push_down(l, r, rt);
    int m = (l + r) >> 1;
    int suml = 0, sumr = 0, minl = 0, minr = 0;
    if(L <= m)
        query(L, R, lson, suml, minl);
    if(R > m)
        query(L, R, rson, sumr, minr);
    Sum = suml + sumr;
    Min = min(minl, minr + suml);
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "r", stdout);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        printf("Case %d:\n", ++iCase);
        scanf("%d", &n);
        scanf("%s", bra + 1);
        scanf("%d", &m);
        build(1, n, 1);
        int l, r;
        char ch[2];
        for(int i = 1; i <= m; i++)
        {
            scanf("%s%d%d", opt, &l, &r);
            l++, r++;
            if(opt[0] == 's')
            {
                scanf("%s", ch);
                cov_change(l, r, idx(ch[0]), 1, n, 1);
            }
            else if(opt[0] == 'r')
            {
                xor_change(l, r, 1, n, 1);
            }
            else
            {
                int Sum = 0, Min = 0;
                query(l, r, 1, n, 1, Sum, Min);
                if(Sum == 0 && Min >= 0)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
        printf("\n");
    }
    return 0;
}