给定一个长度为n的括号序列，要求支持两种操作:
- 将
[
L
i
,
R
i
]
[L_i,R_i]
[Li,Ri]区间内(序列中的第
L
i
L_i
Li个字符到第
R
i
R_i
Ri个字符)的括号全部翻转（左括号变成右括号，右括号变成左括号)。求出以L为左端点时，最长的合法括号序列对应的R(即找出最大的R使[Li,R]是一个合法括号序列)。
输入的第一行包含两个整数n, m，分别表示括号序列长度和操作次数。
第二行包含给定的括号序列，括号序列中只包含左括号和右括号。
接下来m行，每行描述—个操作。如果该行为“1 L R”，表示第一种操作，区间为[L,R];如果该行为“2 L”表示第二种操作，左端点为L。
对于每个第二种操作，输出一行，表示对应的R。如果不存在这样的R，输出0。
输入输出样例 输入样例 #17 5
((())()
2 3
2 2
1 3 5
2 3
2 1
4
7
0
0
对于 20% 的评测用例，n, m ≤ 5000；
对于 40% 的评测用例，n, m ≤ 30000；
对于 60% 的评测用例，n, m ≤ 100000；
对于所有评测用例， 1 ≤ n ≤ 1 0 6 , 1 ≤ m ≤ 2 × 1 0 5 1 ≤ n ≤ 10^6 , 1 ≤ m ≤ 2 × 10^5 1≤n≤106,1≤m≤2×105。
思路对于一个括号序列 [ L , R ] [L,R] [L,R]要合法，需要满足以下要求：
-
p
r
e
s
u
m
[
R
]
=
p
r
e
s
u
m
[
L
−
1
]
presum[R] = presum[L-1]
presum[R]=presum[L−1]
p
r
e
s
u
m
[
i
]
≥
p
r
e
s
u
m
[
L
−
1
]
∀
i
∈
[
L
,
R
]
presum[i] geq presum[L-1] ~forall iin[L,R]
presum[i]≥presum[L−1] ∀i∈[L,R]
要维护这么一个要求，我们只需要满足在 [ L , R ] [L,R] [L,R]之间的前缀和最小值不小于 L − 1 L-1 L−1即可，所以可以用线段树维护一个区间前缀最小值。
同时由于我们有一个翻转操作，由于我们维护的是前缀值，所以一个区间的翻转，我们可以分为 [ 1 , L − 1 ] , [ 1 , R ] [1,L-1],[1,R] [1,L−1],[1,R]的两次翻转。稍作分析我们可以得到一次翻转前后的关系，即原最大值的相反数变为最小值，最小值的相反数变为最大值，所以我们还需要的是维护一个最大值，同时 [ R , N ] [R,N] [R,N]需要加上前缀的改变值。
代码#include#include using namespace std; const int N = 1e6+5; #define lson (p << 1) #define rson (p << 1 | 1) int a[N],n,m; char s[N]; struct node { int mx,mn; int rv,ad; }tr[N<<2]; void push_up(int p) { tr[p].mx = max(tr[lson].mx,tr[rson].mx); tr[p].mn = min(tr[lson].mn,tr[rson].mn); } void change_mn_mx(int p) { int mx = tr[p].mx , mn = tr[p].mn; tr[p].mx = -mn; tr[p].mn = -mx; tr[p].rv ^= 1; tr[p].ad *= -1; } void push_down(int p) { if(tr[p].rv) { change_mn_mx(lson); change_mn_mx(rson); tr[p].rv = 0; } if(tr[p].ad) { tr[lson].ad += tr[p].ad , tr[lson].mn += tr[p].ad , tr[lson].mx += tr[p].ad; tr[rson].ad += tr[p].ad , tr[rson].mn += tr[p].ad , tr[rson].mx += tr[p].ad; tr[p].ad = 0; } } void build(int p,int l,int r) { if(l == r) { tr[p].mn = tr[p].mx = a[l]; return; } int mid = l + r >> 1; build(lson,l,mid); build(rson,mid+1,r); push_up(p); } int ask1(int p,int l,int r,int pos) { if(l == r) return tr[p].mn; push_down(p); int mid = l + r >> 1; int ans = 0; if(pos <= mid) ans = ask1(lson,l,mid,pos); else ans = ask1(rson,mid+1,r,pos); push_up(p); return ans; } int ask2(int p,int l,int r,int pos,int val) { if(l == r) return l; push_down(p); int ans = -1; int mid = l + r >> 1; if(mid >= pos && tr[lson].mn < val) ans = ask2(lson,l,mid,pos,val); if(ans != -1) return ans; if(tr[rson].mn < val) ans = ask2(rson,mid+1,r,pos,val); push_up(p); return ans; } int ask3(int p,int l,int r,int pos,int val) { if(l == r) return l; push_down(p); int ans = -1; int mid = l + r >> 1; if(mid < pos && tr[rson].mn < val) ans = ask3(rson,mid+1,r,pos,val); if(ans != -1) return ans; if(tr[lson].mn < val) ans = ask3(lson,l,mid,pos,val); push_up(p); return ans; } void update(int p,int l,int r,int L,int R) { if(L <= l && r <= R) { change_mn_mx(p); return; } push_down(p); int mid = l + r >> 1; if(L <= mid) update(lson,l,mid,L,R); if(R > mid) update(rson,mid+1,r,L,R); push_up(p); } void modify(int p,int l,int r,int L,int R,int val) { if(L <= l && r <= R) { tr[p].ad += val; tr[p].mn += val; tr[p].mx += val; return; } push_down(p); int mid = l + r >> 1; if(L <= mid) modify(lson,l,mid,L,R,val); if(R > mid) modify(rson,mid+1,r,L,R,val); push_up(p); } void flip(int pos) { if(pos == 0) return; int v = ask1(1,1,n,pos); update(1,1,n,1,pos); if(pos != n) modify(1,1,n,pos+1,n,-2*v); } int main() { #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif scanf("%d%d",&n,&m); scanf("%s",s+1); for(int i = 1 ; i <= n ; i ++) { if(s[i] == '(') a[i] = a[i-1] + 1; else a[i] = a[i-1] - 1; } build(1,1,n); while(m--) { int op; scanf("%d",&op); if(op == 1) { int l,r; scanf("%d%d",&l,&r); flip(l-1); flip(r); } else { int x,target; scanf("%d",&x); if(x == 1) target = 0; else target = ask1(1,1,n,x-1); int y = ask2(1,1,n,x,target); //找到[x,n]中第一个 < target的值，即[x,y-1]均>=target,保证序列无不合法 if(y == -1) y = n + 1; int z = ask3(1,1,n,y-1,target+1);//找到[1,y-1]中第一个< target + 1的值，即[1,z]均<=target,且保证序列最长 printf("%dn",z <= x ? 0 : z); } } return 0; }
