rt，题目传送门

思路就是线段树维护区间前缀最值，照着题解看过了也没问题，交上去全屏 TLE。调不出问题来。

#include <bits/stdc++.h>
using namespace std;

#ifdef SPN_LOCAL
#define debug(x) (cerr << "On Line " << __LINE__ << ": " << #x << " = " << x << endl)
#else
#define debug(x) ((void) 0)
#endif

const int N = 1e6 + 5;

int n, q, opt, l, r;
char s[N];

struct node {
	int sum, premn, premx;
	node() : sum(0), premn(0), premx(0) {}
	node(int a, int b, int c) : sum(a), premn(b), premx(c) {}
};
node operator+ (const node& a, const node& b) {
	return node{
		a.sum + b.sum,
		min(a.premn, a.sum + b.premn),
		max(a.premx, a.sum + b.premx)
	};
}

#define ls (rt << 1)
#define rs (rt << 1 | 1)
bool rev[N << 2]; node val[N << 2];
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void reverses(int rt) {  // 取反串
	val[rt].sum = -val[rt].sum, val[rt].premx = -val[rt].premx, val[rt].premn = -val[rt].premn;
	swap(val[rt].premx, val[rt].premn), rev[rt] ^= 1;
}
void pushdown(int rt) {
	if (!rev[rt]) return;
	rev[ls] ^= 1, rev[rs] ^= 1, rev[rt] ^= 1;
	reverses(ls), reverses(rs);
}

void build(int l, int r, int rt) {
	if (l == r) {
		if (s[l] == '(') val[rt].sum = val[rt].premx = val[rt].premn = 1;
		else val[rt].sum = val[rt].premx = val[rt].premn = -1;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}

void reverse(int tl, int tr, int l, int r, int rt) {
	if (tl <= l && r <= tr) return reverses(rt), void();
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (tl <= mid) reverse(tl, tr, l, mid, ls);
	if (tr > mid) reverse(tl, tr, mid + 1, r, rs);
	pushup(rt);
}

int query_sum(int tl, int tr, int l, int r, int rt) {
	if (tl <= l && r <= tr) return val[rt].sum;
	pushdown(rt);
	int mid = (l + r) >> 1, res = 0;
	if (tl <= mid) res += query_sum(tl, tr, l, mid, ls);
	if (tr > mid) res += query_sum(tl, tr, mid + 1, r, rs);
	return res;
}
int query_pre(int tl, int tr, int l, int r, int rt, int tot) {
	if (tl <= l && r <= tr) return val[rt].premn + tot;
	pushdown(rt);
	int mid = (l + r) >> 1, res = INT_MAX;
	if (tl <= mid) res = min(res, query_pre(tl, tr, l, mid, ls, tot)), tot += query_sum(tl, tr, l, mid, ls);
	if (tr > mid) res = min(res, query_pre(tl, tr, mid + 1, r, rs, tot));
	return res;
}

int query(int l, int r) {
	int tl = l, tr = r, res = INT_MAX;
	while (tl <= tr) {
		int mid = (tl + tr) >> 1;
		if (query_pre(l, mid, 1, n, 1, 0) >= 0) tl = mid + 1, res = mid;
		else tr = mid - 1;
	}
	if (res == INT_MAX) return 0;
	int x = res;
	while (x >= l) {
		int h = query_sum(l, x, 1, n, 1);
		if (h == 0) return x;
		x -= h;
	}
	return 0;
}

void _main() {
	cin >> n >> q >> (s + 1);
	build(1, n, 1);
	while (q--) {
		cin >> opt >> l;
		if (opt == 1) cin >> r, reverse(l, r, 1, n, 1);
		else cout << query(l, n) << '\n';
	}
} signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
	
	int t = 1; for (/*cin >> t*/; t--; ) _main();
	return 0;
}