子序列指的是不连续的一些位置组成的序列，而子串指的是连续的一段区间。

括号串的简化

一个括号序列能匹配都匹配完之后剩下一定是一段前缀 ) 和后缀 (。（要不然就还有能匹配的部分）

比如序列 (())))()(() 最后留下的就是 ))(。

而我们能证明，该括号序列的最长合法子序列就是删掉了留下来的字符所得到的结果。（这就是答案的上界，而我们取到了上界）

比如说，上面的序列最长合法子序列就是 (())()()。

我们尝试把这种结构放到线段树上维护。

区间翻转，区间最长合法括号子序列

P10513 括号

给定一个长度为 nn 的括号序列，支持 mm 次操作：

  1. 翻转 [l,r][l,r] 中的括号，即 ( 变 )，) 变 (。
  2. 查询子串 [l,r][l,r] 最长合法括号子序列的长度除 22。

n,m≤5×105n,m\le 5\times 10^5。

对于线段树的每个节点，我们维护当前在左边剩余的右括号（l），右边剩余的左括号（r），节点的合并就是把中间的括号的一边匹配完。

1
2
3
4
5
6
7
struct Node{ // 形如 )))(((
    int l,r; // l个)，r个(
};
Node operator+(const Node& a,const Node& b){
    if(a.r >= b.l)return {a.l, a.r-b.l+b.r}; // 左边的 ( 比较多
    return {a.l+b.l-a.r,b.r};                // 右边的 ) 比较多
}

这样我们就解决了建树和查询的问题。

接下来考虑翻转。我们只需要额外维护一个节点，保存当前节点取反之后的结果，然后翻转操作只需要交换两个节点的内容就好了，打上懒惰标记下面的节点也同样要交换。

建树复杂度 O(n)O(n)，查询复杂度 O(mlog⁡n)O(m\log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5+5;
char s[N];

struct Node{ // 形如 )))(((
    int l,r; // l个)，r个(
};
Node operator+(const Node& a,const Node& b){
    if(a.r >= b.l)return {a.l, a.r-b.l+b.r}; // 左边的 ( 比较多
    return {a.l+b.l-a.r,b.r};                // 右边的 ) 比较多
}

// t[o][0]：原串 t[o][1]：反串
Node t[N*4][2];bool tag[N*4];
void build(int o,int l,int r){
    if(l==r){
        if(s[l]==')')t[o][0]={1,0},t[o][1]={0,1};
        else t[o][0]={0,1},t[o][1]={1,0};
        return;
    }
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    build(lch,l,mid);build(rch,mid+1,r);
    t[o][0]=t[lch][0]+t[rch][0];
    t[o][1]=t[lch][1]+t[rch][1];
}
void swap(int o){
    swap(t[o][0],t[o][1]); // 交换内容
    tag[o] = !tag[o];
}
void pushdown(int o){
    if(tag[o]){
        int lch=o<<1,rch=o<<1|1;
        swap(lch);swap(rch);
        tag[o]=0;
    }
}
void modify(int o,int l,int r,int ql,int qr){
    if(ql <=l && r<=qr){
        swap(o);return;
    }
    pushdown(o);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    if(ql<=mid)modify(lch,l,mid,ql,qr);
    if(qr>mid) modify(rch,mid+1,r,ql,qr);
    t[o][0]=t[lch][0]+t[rch][0];
    t[o][1]=t[lch][1]+t[rch][1];
}

Node query(int o,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr)return t[o][0];
    pushdown(o);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    if(qr<=mid)return query(lch,l,mid,ql,qr);
    if(ql>mid)return query(rch,mid+1,r,ql,qr);
    return query(lch,l,mid,ql,qr)+query(rch,mid+1,r,ql,qr);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    cin>>(s+1);
    int m;cin>>m;
    build(1,1,n);
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1){
            modify(1,1,n,l,r);
        }
        else{
            auto res = query(1,1,n,l,r);
            cout << (r-l+1 - res.l - res.r)/2 << '\n'; // 记得除 2
        }
    }
    return 0;
}

区间翻转，区间最长合法括号子串

P11657 「FAOI-R5」datealive

给定一个长度为 nn 的括号序列，支持 mm 次操作：

  1. 翻转 [l,r][l,r] 中的括号，即 ( 变 )，) 变 (。
  2. 查询子串 [l,r][l,r] 最长合法括号子串的长度。

n≤4×106,m≤1×105n\le 4\times 10^6,m\le 1\times 10^5，保证操作类型随机。

对于翻转来说。我们依然只用额外维护一个节点保存取反之后的结果，然后翻转操作交换两个节点的内容，不是本题的难点，我们考虑如何求出一个区间的最长合法括号子串。

利用线段树的分治结构，我们能求出了只在左右区间内的结果，考虑如何处理横跨区间两边的子串。

不失一般性，假设左区间在右边剩下的 ( 个数更多。
假设匹配了 kk 个，我们只需要找到左区间简化后的第 k+1k+1 个 (（从右边数）和右边的第一个 (（从左边数）。

我们讨论实现找到这些括号位置的细节。
我们发现，对于一个固定起点来说，开头剩余的 ) 个数单调不下降。（因为再也没有字符能和它匹配了）
同样地，对于一个固定终点来说，结尾剩余的 ( 个数也单调不下降。

基于这个单调性，我们可以用线段树二分，花费 O(log⁡n)O(\log n) 的代价找到这些括号的位置。
对于 ) 来说，因为是固定起点单调不降，所以只能左往右找到第 kk 个 )（如果反过来，) 就有可能被前面的 ( 闭合，难以找到实际的位置） ，而对于 ( 就只能从右往左找了。

直接线段树二分也是可行的，这里提供一种更简单的二分。
对于区间 [l,r][l,r] 和一个完全包含它的节点 oo：

先花 O(log⁡n)O(\log n) 把 [l,r][l,r] 拆分成 O(log⁡n)O(\log n) 个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node{
    int o,l,r;  // 包含 [l,r] 的线段树节点编号和该节点维护区间
    int cntL,cntR,ans; // 左边剩下的)，右边剩下的(，答案
};
Node stk[10000];int tp;
void find_nodes(int o,int ql,int qr,int op){
    if(ql<=t[o][op].l&&t[o][op].r<=qr){stk[++tp]=t[o][op];return;}
    int lch=o<<1,rch=o<<1|1;
    int mid=(t[o][op].l+t[o][op].r)>>1;
    pushdown(o);
    if(ql<=mid)find_nodes(lch,ql,qr,op);
    if(qr> mid)find_nodes(rch,ql,qr,op);
}

然后以找到从左边数第 kk 个 ) 为例：
找到 O(log⁡n)O(\log n) 段中第一个达到 kk 个 ) 的，然后在这一段里面进行二分找到真正的分界点，这样二分就保证了时刻处理的都一定是完整的节点，直接用一个 while 循环就足够解决问题。
复杂度仍然是 O(log⁡n)O(\log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Node{
    int o,l,r;  // 包含 [l,r] 的线段树节点编号和该节点维护区间
    int cntL,cntR,ans; // 左边剩下的)，右边剩下的(，答案
};

// 找到 [ql,qr] 中第 k 个剩的右括号所在的位置（最靠左的那个）
int getkth_L(int o,int ql,int qr,int op,int k){
    tp=0; find_nodes(o,ql,qr,op);
    for(int i=1;i<=tp;i++){
        if(stk[i].cntL >= k){ // 在 i 处二分即可。
            int l = stk[i].l, r = stk[i].r;
            o = stk[i].o;
            while(l<r){
                pushdown(o); // 记得 pushdown
                int mid=(l+r)>>1;
                int lch=o<<1,rch=o<<1|1;
                if(t[lch][op].cntL >= k)r=mid,o=lch;
                else k=k-t[lch][op].cntL+t[lch][op].cntR,l=mid+1,o=rch;
            }
            return l;
        }
        k = k - stk[i].cntL + stk[i].cntR;
    }
    assert(0); // 我们保证一定存在这样的位置
    return -1;
}

有了这个，我们就可以开始写 merge 函数，用于合并两个节点了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Node merge(const Node& p,const Node& q,int op){
    int elim = min(p.cntR, q.cntL);
    Node ret{min(p.o,q.o)>>1,p.l,q.r,p.cntL+q.cntL-elim,p.cntR+q.cntR-elim,max(p.ans,q.ans)};
    int newans;
    
    if(p.cntR == q.cntL){
        newans =    (q.cntR ? getkth_R(q.o,q.l,q.r,op,q.cntR)-1 : q.r) 
                  - (p.cntL ? getkth_L(p.o,p.l,p.r,op,p.cntL)+1 : p.l) + 1;
    }
    else if(p.cntR >= q.cntL){ 
        // q 的被消耗完了
        newans =    (q.cntR ? getkth_R(q.o,q.l,q.r,op,q.cntR)-1 : q.r) 
                  - (getkth_R(p.o,p.l,p.r,op,q.cntL+1)+1) + 1;
    }
    else{
        // p 的被消耗完了
        newans =    (getkth_L(q.o,q.l,q.r,op,p.cntR+1)-1) 
                  - (p.cntL ? getkth_L(p.o,p.l,p.r,op,p.cntL)+1 : p.l) + 1;
    }
    ret.ans = max(ret.ans, newans);
    return ret;
}

分类讨论哪边的括号被消耗完，找到对应的位置，算出横跨的长度更新答案就好了。

建树复杂度 T(n)=2T(n/2)+O(log⁡n)=O(n)T(n)=2T(n/2)+O(\log n) = O(n)，查询复杂度 O(log⁡2n)O(\log^2 n)。
总复杂度 O(n+qlog⁡2n)O(n+q\log^2 n)。

这道题空间卡的也比较紧（主要是 nn 太大了）。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;

const int N = 4e6+6;
int a[N];
struct Node{
    int o,l,r;  // 包含 [l,r] 的线段树节点编号和该节点维护区间
    int cntL,cntR,ans; // 左边剩下的)，右边剩下的(，答案
};

Node t[N*4][2];bool tag[N*4];

void inv(int o){
    swap(t[o][0],t[o][1]);
    tag[o] = !tag[o];
}
void pushdown(int o){
    if(tag[o]){
        int lch=o<<1,rch=o<<1|1;
        inv(lch);inv(rch);
        tag[o]=0;
    }
}


Node stk[10000];int tp;
void find_nodes(int o,int ql,int qr,int op){
    if(ql<=t[o][op].l&&t[o][op].r<=qr){stk[++tp]=t[o][op];return;}
    int lch=o<<1,rch=o<<1|1;
    int mid=(t[o][op].l+t[o][op].r)>>1;
    pushdown(o);
    if(ql<=mid)find_nodes(lch,ql,qr,op);
    if(qr> mid)find_nodes(rch,ql,qr,op);
}

// 找到 [ql,qr] 中第 k 个剩的右括号所在的位置（最靠左的那个）
int getkth_L(int o,int ql,int qr,int op,int k){
    tp=0; find_nodes(o,ql,qr,op);
    for(int i=1;i<=tp;i++){
        if(stk[i].cntL >= k){ // 在 i 处二分即可。
            int l = stk[i].l, r = stk[i].r;
            o = stk[i].o;
            while(l<r){
                pushdown(o);
                int mid=(l+r)>>1;
                int lch=o<<1,rch=o<<1|1;
                if(t[lch][op].cntL >= k)r=mid,o=lch;
                else k=k-t[lch][op].cntL+t[lch][op].cntR,l=mid+1,o=rch;
            }
            return l;
        }
        k = k - stk[i].cntL + stk[i].cntR;
    }
    assert(0);
    return -1;
}

// 找到 [ql,qr] 中从右边看，第k个右边剩下的左括号所在的位置（最靠右的那个）
int getkth_R(int o,int ql,int qr,int op,int k){
    tp=0; find_nodes(o,ql,qr,op);
    for(int i=tp;i>=1;i--){
        if(stk[i].cntR >= k){ // 在 i 处二分即可。
            int l = stk[i].l, r = stk[i].r;
            o = stk[i].o;
            while(l<r){
                pushdown(o);
                int mid=(l+r)>>1;
                int lch=o<<1,rch=o<<1|1;
                if(t[rch][op].cntR >= k)l=mid+1,o=rch;
                else k=k-t[rch][op].cntR+t[rch][op].cntL,r=mid,o=lch;
            }
            return l;
        }
        k = k - stk[i].cntR + stk[i].cntL;
    }
    assert(0);
    return -1;
}


Node merge(const Node& p,const Node& q,int op){
    int elim = min(p.cntR, q.cntL);
    Node ret{min(p.o,q.o)>>1,p.l,q.r,p.cntL+q.cntL-elim,p.cntR+q.cntR-elim,max(p.ans,q.ans)};
    int newans;
    
    if(p.cntR == q.cntL){
        newans =    (q.cntR ? getkth_R(q.o,q.l,q.r,op,q.cntR)-1 : q.r) 
                  - (p.cntL ? getkth_L(p.o,p.l,p.r,op,p.cntL)+1 : p.l) + 1;
    }
    else if(p.cntR >= q.cntL){ 
        // q 的被消耗完了
        newans =    (q.cntR ? getkth_R(q.o,q.l,q.r,op,q.cntR)-1 : q.r) 
                  - (getkth_R(p.o,p.l,p.r,op,q.cntL+1)+1) + 1;
    }
    else{
        // p 的被消耗完了
        newans =    (getkth_L(q.o,q.l,q.r,op,p.cntR+1)-1) 
                  - (p.cntL ? getkth_L(p.o,p.l,p.r,op,p.cntL)+1 : p.l) + 1;
    }
    ret.ans = max(ret.ans, newans);
    return ret;
}

void build(int o,int l,int r){
    if(l==r){
        t[o][0] = {o,l,r, a[l]==1,a[l]==0,0};
        t[o][1] = {o,l,r, a[l]==0,a[l]==1,0};
        return;
    }
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    build(lch,l,mid);build(rch,mid+1,r);
    t[o][0] = merge(t[lch][0],t[rch][0],0);
    t[o][1] = merge(t[lch][1],t[rch][1],1);
}
void modify(int o,int l,int r,int ql,int qr){
    if(ql <=l && r<=qr){
        inv(o);return;
    }
    pushdown(o);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    if(ql<=mid)modify(lch,l,mid,ql,qr);
    if(qr>mid) modify(rch,mid+1,r,ql,qr);
    t[o][0] = merge(t[lch][0],t[rch][0],0);
    t[o][1] = merge(t[lch][1],t[rch][1],1);
}

Node query(int o,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr)return t[o][0];
    pushdown(o);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    if(qr<=mid)return query(lch,l,mid,ql,qr);
    if(ql>mid)return query(rch,mid+1,r,ql,qr);
    return merge(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr),0);
}
    

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];

    build(1,1,n);
    int lastans = 0;
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        l=(l+lastans)%n+1,r=(r+lastans)%n+1;
        if(l>r)swap(l,r);
        if(op==1){
            lastans = query(1,1,n,l,r).ans;
            cout << lastans << '\n';
        }
        else modify(1,1,n,l,r);
    }
    return 0;
}

区间翻转，某一位置开始最长合法括号子串

P8765 [蓝桥杯 2021 国 AB] 翻转括号序列

给定一个长度为 nn 的括号序列，支持 mm 次操作：

  1. 翻转 [l,r][l,r] 中的括号，即 ( 变 )，) 变 (。
  2. 查询以 ll 为起点，最长合法括号子串的右端点（不存在输出 00）。

n≤1×106,m≤2×105n\le 1\times 10^6,m\le 2\times 10^5。

考虑延续之前的思路。

合法括号子串尽可能匹配后左边一定剩下 00 个 )，因此我们可以先二分找到最长的一段没有 ) 的位置。
即找到最大的 rr，使得 [l,r][l,r] 化简后不存在 )。
假设 [l,r][l,r] 中有 k (k≥0)k\ (k\ge 0) 个左括号。
如果 k=0k=0，那么 rr 就是答案，否则需要往回找，从右往左找到 [l,r][l,r] 中第 kk 个 (，该做法已经在上文讲过了，那么前一个位置就是我们要求出的右端点。（特判都是左括号的情况）

由此，我们就成功 O(n+mlog⁡n)O(n+m\log n) 解决了该题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;


const int N = 1e6+5;
string s;
struct Node{
    int o,l,r;  // 包含 [l,r] 的线段树节点编号和该节点维护区间
    int cntL,cntR,ans; // 左边剩下的)，右边剩下的(，答案
};
Node t[N*4][2];bool tag[N*4];

void inv(int o){
    swap(t[o][0],t[o][1]);
    tag[o] = !tag[o];
}
void pushdown(int o){
    if(tag[o]){
        int lch=o<<1,rch=o<<1|1;
        inv(lch);inv(rch);
        tag[o]=0;
    }
}

Node stk[10000];int tp;
void find_nodes(int o,int ql,int qr){
    if(ql<=t[o][0].l&&t[o][0].r<=qr){stk[++tp]=t[o][0];return;}
    int lch=o<<1,rch=o<<1|1;
    int mid=(t[o][0].l+t[o][0].r)>>1;
    pushdown(o);
    if(ql<=mid)find_nodes(lch,ql,qr);
    if(qr> mid)find_nodes(rch,ql,qr);
}

// 找到最长的没有)的段
pair<int,int> maxR(int o,int ql,int qr){
    tp=0; find_nodes(o,ql,qr);
    int k = 0;
    for(int i=1;i<=tp;i++){
        if(stk[i].cntL > k){ 
            int l = stk[i].l, r = stk[i].r;
            o = stk[i].o;
            while(l<r){
                pushdown(o);
                int mid=(l+r)>>1;
                int lch=o<<1,rch=o<<1|1;
                if(t[lch][0].cntL > k)r=mid,o=lch;
                else k=k-t[lch][0].cntL+t[lch][0].cntR,l=mid+1,o=rch;
            }
            return {l-1,k};
        }
        k = k - stk[i].cntL + stk[i].cntR;
    }
    return {qr,k};
}

// 找到 [ql,qr] 中从右边看，第k个右边剩下的左括号所在的位置（最靠右的那个）
int getkth_R(int o,int ql,int qr,int k){
    tp=0; find_nodes(o,ql,qr);
    for(int i=tp;i>=1;i--){
        if(stk[i].cntR >= k){ // 在 i 处二分即可。
            int l = stk[i].l, r = stk[i].r;
            o = stk[i].o;
            while(l<r){
                pushdown(o);
                int mid=(l+r)>>1;
                int lch=o<<1,rch=o<<1|1;
                if(t[rch][0].cntR >= k)l=mid+1,o=rch;
                else k=k-t[rch][0].cntR+t[rch][0].cntL,r=mid,o=lch;
            }
            return l;
        }
        k = k - stk[i].cntR + stk[i].cntL;
    }
    assert(0);
    return -1;
}


Node merge(const Node& p,const Node& q){
    int elim = min(p.cntR, q.cntL);
    Node ret{min(p.o,q.o)>>1,p.l,q.r,p.cntL+q.cntL-elim,p.cntR+q.cntR-elim};
    return ret;
}

void build(int o,int l,int r){
    if(l==r){
        t[o][0] = {o,l,r, s[l-1]==')',s[l-1]=='('};
        t[o][1] = {o,l,r, s[l-1]=='(',s[l-1]==')'};
        return;
    }
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    build(lch,l,mid);build(rch,mid+1,r);
    t[o][0] = merge(t[lch][0],t[rch][0]);
    t[o][1] = merge(t[lch][1],t[rch][1]);
}
void modify(int o,int l,int r,int ql,int qr){
    if(ql <=l && r<=qr){
        inv(o);return;
    }
    pushdown(o);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    if(ql<=mid)modify(lch,l,mid,ql,qr);
    if(qr>mid) modify(rch,mid+1,r,ql,qr);
    t[o][0] = merge(t[lch][0],t[rch][0]);
    t[o][1] = merge(t[lch][1],t[rch][1]);
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cout<<fixed;

    int n,m;cin>>n>>m;
    cin>>s;

    build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            modify(1,1,n,l,r);
        }
        else{
            int x;cin>>x;
            auto [maxr,cnt] = maxR(1,x,n);
            if(maxr == x-1){
                cout << 0 << '\n';
            }
            else if(!cnt){
                cout << maxr << '\n';
            }
            else{
                int pos = getkth_R(1,x,maxr,cnt)-1 ;
                cout << (pos==x-1?0:pos) << '\n';
            }
        }
    }
    return 0;
}