本以为只是不会线段树，写完之后发现二分也不会
问题出在几个地方：
一、
这个是正确复杂度的查询
int query(int x, int y, int p)
{
int l = t[p].l, r = t[p].r;
if (!x)return 0;
if (x <= l && r <= y)return t[p].vue;
pushdown(p);
int mid = l + r >> 1;
if (y <= mid)return query(x, y, p << 1);
else if (x > mid)return query(x, y, p << 1 | 1);
else
return min(query(x, y, p << 1), query(x, y, p << 1 | 1));
}
这个是会T的查询
int query(int x, int y, int p)
{
if(!x)return 0;
int l = t[p].l, r = t[p].r;
if (x <= l && r <= y)return t[p].vue;
pushdown(p);
int mid = l + r >> 1;
if (x <= mid && y > mid)return min(query(x, y, p << 1), query(x, y, p << 1 | 1));
else if (x <= mid)return query(x, y, p << 1);
else return query(x, y, p << 1 | 1);
}
就是在区间划分的时候
if (y <= mid)return query(x, y, p << 1);
else if (x > mid)return query(x, y, p << 1 | 1);
else
return min(query(x, y, p << 1), query(x, y, p << 1 | 1));
这样写比之前的写法时间上更优
二、
二分答案出现问题,之前写的二分个人理解可能是由于mid下取整导致在处理这种问题
上不够稳定
二分最后一个满足条件的点（可能不存在）
while (l <= r)
{
int mid = l + r >> 1;
if (query(mid, r, 1) == limx)//如果有合法状态在区间内的话最小值必然等于limx
ans = mid, l = mid + 1;
else
r = mid - 1;//没有就换个区间
}
二分第一个满足条件的点（可能不存在）
while (l <= r)
{
int mid = l + r >> 1;
if (query(l, mid, 1) < limx)
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
我们记录左括号为+1，右括号为-1，求一个前缀和，然后用线段树维护区间最小值
题目要求找从某个点(x)出发的最长匹配，就是前缀和等于(pre[x-1])的点(i)，并且满足(x<=j<=i)同时(pre[j]>=pre[x-1])，那么只有2种情况：
①、对于区间([x,n]),其中(x<=j<=n)且都满足(pre[j]>=pre[x-1])
形如：()()()(()()() ) ((
找到最后一个(pre[j]==pre[x-1])即为答案
(但可能出现"((((((((((((("即(pre[j]>pre[x-1])这种特殊情况，需要将ans初始化为x-1，在二分更新l的时候更新答案，若不更新即为该种情况)
②、对于区间([x,n]),其中(x<=j<=n)存在(pre[j]<pre[x-1])
就去寻找第一个(pre[j]<pre[x-1])的(j)，答案即为(j-x)
剩下的都写在注释里了
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#include<unordered_map>
using namespace std;
#define ll long long
#define Ls t[p << 1]
#define Rs t[p << 1 | 1]
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int maxn = 5e5 + 10;
const int inf = 1e9;
ll mod = 1e9 + 7;
char s[maxn];
int n;
struct tree {
int l, r;
int vue, lazy;
}t[maxn << 2];
int a[maxn];
void build(int l, int r, int p)
{
t[p].lazy = 0;
t[p].l = l, t[p].r = r;
if (l == r)
{
t[p].vue = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1 | 1);
t[p].vue = min(Ls.vue, Rs.vue);
}
void pushdown(int p)
{
if (t[p].lazy)
{
int lazy = t[p].lazy;
Ls.vue += lazy;
Rs.vue += lazy;
Ls.lazy += lazy;
Rs.lazy += lazy;
t[p].lazy = 0;
}
}
void change(int x, int y, int k, int p)
{
int l = t[p].l, r = t[p].r;
if (x <= l && r <= y) {
t[p].vue += k;
t[p].lazy += k;
return;
}
pushdown(p);
int mid = l + r >> 1;
if (x <= mid)change(x, y, k, p << 1);
if (y > mid)change(x, y, k, p << 1 | 1);
t[p].vue = min(Ls.vue, Rs.vue);
}
int query(int x, int y, int p)
{
int l = t[p].l, r = t[p].r;
if (!x)return 0;
if (x <= l && r <= y)return t[p].vue;
pushdown(p);
int mid = l + r >> 1;
if (y <= mid)return query(x, y, p << 1);
else if (x > mid)return query(x, y, p << 1 | 1);
else
return min(query(x, y, p << 1), query(x, y, p << 1 | 1));
}
int main()
{
//freopen("C:\1.in", "r", stdin);
//fastio;
int t;
scanf("%d", &t);
while (t--)
{
int q;
scanf("%d%d", &n, &q);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++)
a[i] = a[i - 1] + (s[i] == '(' ? 1 : -1);
build(0, n, 1);
while (q--)
{
int o, x;
scanf("%d%d", &o, &x);
if (o == 1)
{
if (s[x] == '(')
{
s[x] = ')';
change(x, n, -2, 1);
}
else
{
s[x] = '(';
change(x, n, 2, 1);
}
}
else
{
int limx = query(x - 1, x - 1, 1), MIN = query(x, n, 1), l = x, r = n;
//cout << limx << " " << MIN << endl;
if (MIN >= limx)//在匹配段后没有出现")..."这种情况，即')'全被匹配,'('多了
{
//寻找最后一个等于limx的位置
int ans = x - 1;
while (l < r)
{
int mid = l + r >> 1;
if (query(mid, r, 1) == limx)//如果有合法状态在区间内的话最小值必然等于limx
ans = mid, l = mid + 1;
else
r = mid - 1;//没有就换个区间
}
//cout << l << " " << x << endl;
printf("%d
", ans - x + 1);
}
else//在合法状态之后会出现')'的直接导致不能继续延展
{
//寻找第一个不合法位置
int ans;
while (l <= r)
{
int mid = l + r >> 1;
//cout << query(x, mid, 1) << " " << limx << endl;
if (query(l, mid, 1) < limx)
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d
", ans - x);
//cout << endl;
}
}
}
}
return 0;
}