P10513 括号

一、题目简析

本题采用 线段树 求解。

节点的定义

struct node
{
	int l, r;
	int lcnt, rcnt;     // lcnt -- (的个数; rcnt -- )的个数 
	int ans, anti;      // ans -- ()的个数; anti -- )(的个数 
	bool tag;           // true -- 需要翻转左右孩子 
} tree[N << 2];

对于 \([l,r]\) 的括号序列，合法的括号对数，有三个贡献：

• 仅在左半部分 \([l,m]\) 形成的合法括号对数 ()
• 仅在右半部分 \([m+1,r]\) 形成的合法括号对数 ()
• 由左右两部分一起提供括号形成的括号对数 ()，即 \([l,m]\) 提供 (，为 lcnt - ans；\([m+1,r]\) 提供 )，为 rcnt - ans

因此，节点不仅要有 ans (记录 ())，而且要有 lcnt (记录 ()和 rcnt (记录 ))。

除此以外，还需要 anti，记录 )(。翻转一次括号序列 \([l.r]\)，翻转后的结果，只需要分别交换 lcnt 和 rcnt，ans 和 anti。有了 anti，就能快速得到 ans。

对于 \([l,r]\) 的括号序列，anti 也有三个贡献：

• 仅在左半部分 \([l,m]\) 形成的 )(
• 仅在右半部分 \([m+1,r]\) 形成的 )(
• 由左右两部分一起提供括号形成的 )(，即 \([l,m]\) 提供 )，为 rcnt - anti；\([m+1,r]\) 提供 (，为 lcnt - anti

合并信息

void add(node &p, node &a, node &b)
{
	p.lcnt = a.lcnt + b.lcnt;
	p.rcnt = a.rcnt + b.rcnt;
	p.ans = a.ans + b.ans + min(a.lcnt - a.ans, b.rcnt - b.ans);
	p.anti = a.anti + b.anti + min(a.rcnt - a.anti, b.lcnt - b.anti);
}

void pushup(int p)
{
	add(tree[p], tree[lc(p)], tree[rc(p)]);
}

翻转操作

void amend(node &p)
{
	swap(p.lcnt, p.rcnt);
	swap(p.ans, p.anti);
}

Code

#include <iostream>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

#define lc(p)    p << 1
#define rc(p)    p << 1 | 1
const int N = 5e5 + 5;
int n, m;
char s[N];
struct node
{
	int l, r;
	int lcnt, rcnt;     // lcnt -- (的个数; rcnt -- )的个数 
	int ans, anti;      // ans -- ()的个数; anti -- )(的个数 
	bool tag;           // true -- 需要翻转左右孩子 
} tree[N << 2];

void add(node &p, node &a, node &b)
{
	p.lcnt = a.lcnt + b.lcnt;
	p.rcnt = a.rcnt + b.rcnt;
	p.ans = a.ans + b.ans + min(a.lcnt - a.ans, b.rcnt - b.ans);
	p.anti = a.anti + b.anti + min(a.rcnt - a.anti, b.lcnt - b.anti);
}

void amend(node &p)
{
	swap(p.lcnt, p.rcnt);
	swap(p.ans, p.anti);
}

void pushup(int p)
{
	add(tree[p], tree[lc(p)], tree[rc(p)]);
}

void pushdown(int p)
{
	if (tree[p].tag)
	{
		amend(tree[lc(p)]);
		tree[lc(p)].tag ^= 1;
		
		amend(tree[rc(p)]);
		tree[rc(p)].tag ^= 1;
		
		tree[p].tag = false;
	}
}

void build(int p, int l, int r)
{
	tree[p].l = l, tree[p].r = r;
	if (l == r)
	{
		tree[p].lcnt = s[l] == '(';
		tree[p].rcnt = s[l] == ')';
		return;
	}
	
	int m = l + r >> 1;
	build(lc(p), l, m);
	build(rc(p), m + 1, r);
	
	pushup(p);
}

void update(int p, int x, int y)
{
	if (x <= tree[p].l && tree[p].r <= y)
	{
		amend(tree[p]);
		tree[p].tag ^= 1;
		return;
	}
	
	pushdown(p);
	
	int m = tree[p].l + tree[p].r >> 1;
	if (x <= m)    update(lc(p), x, y);
	if (y > m)    update(rc(p), x, y);
	
	pushup(p);
}

node query(int p, int x, int y)
{
	if (x <= tree[p].l && tree[p].r <= y)
		return tree[p];
		
	pushdown(p);
	
	int m = tree[p].l + tree[p].r >> 1;
	node a = {0}, b = {0}, res = {0};        // 不能简单地将两个区间的ans相加， 
	if (x <= m)    a = query(lc(p), x, y);   // 还有两个区间共同形成的() 
	if (y > m)    b = query(rc(p), x, y);    // 所以必须将两个区间的信息合并 
	
	add(res, a, b);
	return res;
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	scanf("%s", s + 1);
	
	build(1, 1, n);
	
	m = quickin();
	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		a = quickin(), b = quickin(), c = quickin();
		
		if (a == 1)
			update(1, b, c);
		else if (a == 2)
			printf("%d\n", query(1, b, c).ans);
	}
	
	return 0;
}

完