样例输出随机值求条

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define dwn(i, j, k) for (int i = (j); i >= (k); --i)
#define endl '\n'
#define ls son[u][0]
#define rs son[u][1]

using namespace std;

constexpr int N = 1e6 + 7;

mt19937 rnd(chrono :: system_clock :: now().time_since_epoch().count());

struct FHQ_Treap {
	int a[N], sum[N], pri[N], son[N][2], pre_max[N], pre_min[N], suf_max[N], suf_min[N], cover[N], size[N], rev[N], inv[N];
	int rt, cnt;
	
	int new_node(int value) {
		const int u = ++cnt;
		pre_max[u] = pre_min[u] = suf_min[u] = suf_max[u] = 0;
		sum[u] = a[u] = value;
		pri[u] = rnd();
		size[u] = 1;
		if (value == 1) pre_max[u] = suf_max[u] = value;
		else pre_min[u] = suf_min[u] = value;
		return u;
	}
	
	void push_up(int u) {
		sum[u] = sum[ls] + sum[rs] + a[u];
		size[u] = size[ls] + size[rs] + 1;
		pre_max[u] = max(pre_max[ls], sum[ls] + a[u] + pre_max[rs]);
		pre_min[u] = min(pre_min[ls], sum[ls] + a[u] + pre_min[rs]);
		suf_max[u] = max(suf_max[rs], sum[rs] + a[u] + suf_max[ls]);
		suf_min[u] = min(suf_min[rs], sum[rs] + a[u] + suf_min[ls]);
	}
	
	void _rev(int u) {
		swap(ls, rs);
		swap(pre_max[u], suf_max[u]);
		swap(pre_min[u], suf_min[u]);
		rev[u] ^= 1;
	}
	
	void _inv(int u) {
		a[u] = -a[u], sum[u] = -sum[u];
		int x = pre_max[u], y = pre_min[u];
		pre_min[u] = -x, pre_max[u] = -y;
		x = suf_max[u], y = suf_min[u];
		suf_min[u] = -x, suf_max[u] = -y;
	}
	
	void _cover(int u, int value) {
		a[u] = cover[u] = value;
		sum[u] = size[u] * value;
		if (value == 1) {
			pre_min[u] = suf_min[u] = 0;
			pre_max[u] = suf_max[u] = size[u];
		} else {
			pre_min[u] = suf_min[u] = -size[u];
			pre_max[u] = suf_max[u] = 0;
		}
		inv[u] = rev[u] = 0;
	}
	
	void push_down(int u) {
		if (inv[u]) {
			if (ls) _inv(ls);
			if (rs) _inv(rs);
			inv[u] = 0;
		}		
		if (cover[u]) {
			if (ls) _cover(ls, cover[u]);
			if (rs) _cover(rs, cover[u]);
			cover[u] = 0;
		}
		if (rev[u]) {
			if (ls) _rev(ls);
			if (rs) _rev(rs);
			rev[u] = 0;
		}
	}
	
	int merge(int first, int second) {
		push_down(first), push_down(second);
		if (!first || !second) return first + second;
		if (pri[first] < pri[second]) {
			son[first][1] = merge(son[first][1], second);
			push_up(first);
			return first;
		} else {
			son[second][0] = merge(first, son[second][0]);
			push_up(second);
			return second;
		}
	}
	
	void split(int u, int value, int &L, int &R) {
		if (!u) return L = R = 0, void();
		push_down(u);
		if (size[ls] < value) {
			L = u;
			split(rs, value - size[ls] - 1, rs, R);
		} else {
			R = u;
			split(ls, value, L, ls);
		}
	}
	
	void insert(int value) {rt = merge(rt, new_node(value));}
	
	int query(int l, int r) {
		int x, y, z, res = 0;
		split(rt, l - 1, x, y), split(y, r - l + 1, z, y);
		res = (pre_max[z] + 1) / 2 - (suf_min[z] - 1) / 2;
		rt = merge(merge(x, z), y);
		return res;
	}
	
	void reverse(int l, int r) {
		int x, y, z;
		split(rt, l - 1, x, y), split(y, r - l + 1, z, y);
		_rev(z);
		rt = merge(merge(x, z), y);
	}
	
	void replace(int l, int r, int value) {
		int x, y, z;
		split(rt, l - 1, x, y), split(y, r - l + 1, z, y);
		_cover(z, value);
		rt = merge(merge(x, z), y);
	}
	
	void invert(int l, int r) {
		int x, y, z;
		split(rt, l - 1, x, y), split(y, r - l + 1, z, y);
		_inv(z);
		rt = merge(merge(x, z), y);
	}
} T;
	
int n, Q;
	
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> Q;
	string s;
	cin >> s;
	for (auto c : s) T.insert(c == ')' ? 1 : -1);
	while (Q--) {
		int l, r;
		string op;
		cin >> op;
		if (op == "Replace") {
			cin >> l >> r;
			char c;
			cin >> c;
			T.replace(l, r, c == ')' ? 1 : -1);
		} else if (op == "Query") {
			cin >> l >> r;
			cout << T.query(l, r) << endl;
		} else if (op == "Swap") {
			cin >> l >> r;
			T.reverse(l, r);
		} else if (op == "Invert") {
			cin >> l >> r;
			T.invert(l, r);
		}
	}
	return 0;
}