P10513 括号 Solution

Description

给定一个长度为 $n$ 且只包含 ( 和 ) 的字符串 $s$，有 $m$ 个操作分两种：

• $\mathrm{negate}(l,r)$：将 $s_l\sim s_r$ 的括号翻转.
• $\mathrm{query}(l,r)$：求 $s_{l\cdots r}$ 的最长合法括号子序列长度除以 $2$.

Limitations

$1\le n,m\le 5\times 10^5$
$1\le l\le r\le n$
保证数据随机.
$1\text{s},512\text{MB}$

Solution

显然用线段树，考虑如何合并答案.
每个节点维护 $(cn{t}_L,cn{t}_R,res)$ 表示剩余左括号个数、剩余右括号个数和答案.
合并时先加上子节点的答案，然后消掉跨过 $\text{mid}$ 的 $\min (cn{t}_L(\text{lson}),cn{t}_R(\text{rson}))$ 对括号.
区间取反就多维护一个反串的信息，修改的时候可以直接交换.
时间复杂度 $O(m\log n)$.

Code

$2.81\text{KB},7.24\text{s},35.33\text{MB}\text{(in total, C++20 with O2)}$

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

struct Data {
	int cntL = 0, cntR = 0, res = 0;
	inline Data() {}
	inline Data(int _cntL, int _cntR, int _res) : cntL(_cntL), cntR(_cntR), res(_res) {}
};
inline Data operator+(const Data& lhs, const Data& rhs) {
	const int tmp = min(lhs.cntL, rhs.cntR);
	return Data(lhs.cntL + rhs.cntL - tmp, 
	            lhs.cntR + rhs.cntR - tmp, 
	            lhs.res + rhs.res + tmp);
}

namespace seg_tree {
	struct Node {
		int l, r;
		array<Data, 2> dat;
		bool rev = false;
	};
	
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct SegTree {
		vector<Node> tr;
		inline SegTree() {}
		inline SegTree(const string& s) {
			const int n = s.size();
			tr.resize(n << 1);
			build(0, 0, n - 1, s);
		}
		
		inline void pushup(int u, int mid) {
			tr[u].dat[0] = tr[ls(mid)].dat[0] + tr[rs(mid)].dat[0];
			tr[u].dat[1] = tr[ls(mid)].dat[1] + tr[rs(mid)].dat[1];
		}
		
		inline void apply(int u) {
			tr[u].rev ^= 1;
			swap(tr[u].dat[0], tr[u].dat[1]);
		}
		
		inline void pushdown(int u, int mid) {
			if (!tr[u].rev) return;
			apply(ls(mid)), apply(rs(mid));
			tr[u].rev = 0;
		}
		
		void build(int u, int l, int r, const string& s) {
			tr[u].l = l, tr[u].r = r;
			if (l == r) {
				tr[u].dat[0] = Data(s[l] == '(', s[l] == ')', 0);
				tr[u].dat[1] = Data(s[l] == ')', s[l] == '(', 0);
				return;
			}
			const int mid = (l + r) >> 1;
			build(ls(mid), l, mid, s);
			build(rs(mid), mid + 1, r, s);
			pushup(u, mid);
		}
		
		void negate(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return apply(u);
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (l <= mid) negate(ls(mid), l, r);
			if (r > mid) negate(rs(mid), l, r);
			pushup(u, mid);
		}
		
		Data query(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return tr[u].dat[0];
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (r <= mid) return query(ls(mid), l, r);
			else if (l > mid) return query(rs(mid), l, r);
			else return query(ls(mid), l, r) + query(rs(mid), l, r);
		}
	};
}
using seg_tree::SegTree;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n; scanf("%d", &n);
	string s; s.resize(n);
	scanf("%s", &s[0]);
	SegTree seg(s);
	
	int m; scanf("%d", &m);
	for (int i = 0, op, l, r; i < m; i++) {
		scanf("%d %d %d", &op, &l, &r), l--, r--;
		if (op == 1) seg.negate(0, l, r);
		else printf("%d\n", seg.query(0, l, r).res);
	}
	
	return 0;
}