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