题解：P10513 括号

· · 题解

P10513 括号

题意

你有一个括号序列 S，包含 ( 和 )。还有有两种操作：

  1. 1 l r 表示翻转 l 到 r 之间的括号（注意是括号翻转而非序列翻转）。
  2. 2 l r 表示询问 [l,r] 中最长的合法括号子序列的长度除以 2 的结果。

解法

比较自然的思路，这种题首先考虑用线段树来维护多个状态。

其实和 P2894 思想上比较像。在线段树往上面合并的时候都是左边的最大值和右边的最大值以及左区间的 ( 再加上右区间的 )。

但是发现修改操作有点不是很好搞怎么办呢？可以在存的时候就把括号反着存一遍，也就是说每次更改操作其实都只是一次交换操作而已，这样两个操作都被解决了。

注意的点

其实这道题并没有什么注意的地方，但是可以给我们一点启示：碰上这种类型的问题就可以往线段树方向上想，类似的存储的时候不一定只是答案，也可以是左右区间的某一些信息，更方便我们求解答案。

code

#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define N 500005
using namespace std;
char s[N];
int n,q,a[N];
bool lz[N<<2];
struct NN{
    int l,r,x,y;
    NN operator +(const NN a){
        NN k={l+a.l,r+a.r,0,0};
        k.x=x+a.x+min(r-x,a.l-a.x);
        k.y=y+a.y+min(l-y,a.r-a.y);
        return k;
    }
}tr[N<<2];
void pushup(int x){tr[x]=tr[ls(x)]+tr[rs(x)];}
void Swap(int x){swap(tr[x].l,tr[x].r),swap(tr[x].x,tr[x].y);}
void pushdown(int x){
    if(lz[x]){
        Swap(ls(x)),Swap(rs(x));
        lz[x]=0,lz[ls(x)]^=1,lz[rs(x)]^=1;
    }
}
void build(int x,int l,int r){
    if(l==r){a[l]?tr[x]={0,1,0,0}:tr[x]={1,0,0,0};return;}
    int mid=(l+r)>>1;
    build(ls(x),l,mid),build(rs(x),mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int L,int R){
    if(R<l||L>r) return;
    if(L<=l&&r<=R){Swap(x),lz[x]^=1;return;}
    if(lz[x]) pushdown(x);
    int mid=(l+r)>>1;
    if(L<=mid) update(ls(x),l,mid,L,R);
    if(R>mid) update(rs(x),mid+1,r,L,R);
    pushup(x);
}
NN query(int x,int l,int r,int L,int R){
    if(R<l||L>r) return {0,0,0,0};
    if(L<=l&&r<=R) return tr[x];
    if(lz[x]) pushdown(x);
    int mid=(l+r)>>1;NN k={0,0,0,0};
    if(L<=mid) k=k+query(ls(x),l,mid,L,R);
    if(R>mid) k=k+query(rs(x),mid+1,r,L,R);
    return k;
}
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) a[i]=(s[i]=='(');
    build(1,1,n);
    scanf("%d",&q);
    while(q--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1) update(1,1,n,l,r);
        else printf("%d\n",query(1,1,n,l,r).x);
    }
    return 0;
}