【题解】Codeforces Round #765 (Div. 2)

vp→rk156，罚时有些爆炸，题好像都挺经典的？
小清新的分治题（不过题解方法不一样），和经典的括号树的实现

D

小清新题，在二进制下从高位往低位考虑：
若 K 该位为 0，自然想到分治：将待选集合按该位为 0 或 1 分为两组，显然组间的配对是满足的，组内继续考虑下一位；
若 K 该位为 1，注意到这时我们只能在待选集合里选择最多两个数，且这两个数在该位一个为 0，一个为 1，那么我们同样对这个区间按该位的数字划分成两部分，递归下去找那两个数就行了（另一个递归函数 find）
感觉写的挺好看的，在下标数组上操作，用 [l, r] 来表示集合

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int T;
const int MAXN = 300005;
int N, K;
int A[MAXN], B[MAXN], C[MAXN];
int S[MAXN];
void di(int l, int r, int &pl, int &pr, int b) // l, pl, pr, r
{
	pl = l-1, pr = r+1;
	for (int i=l; i<=r; i++)
		if (A[B[i]]&(1< r1 || l2> r2) return 0;
	if (b< 0) { C[B[l1]] = C[B[l2]] = 1; return 1; }
	int pl1, pr1, pl2, pr2;
	di(l1, r1, pl1, pr1, b);
	di(l2, r2, pl2, pr2, b);
	if (K&(1<=l1 && r2>=pr2) { C[B[l1]] = C[B[r2]] = 1; return 1; }
		if (r1>=pr1 && pl2>=l2) { C[B[r1]] = C[B[l2]] = 1; return 1; }
		if (find(l1, r1, l2, r2, b-1)) return 1;
	}
	return 0;
}
void cal(int l, int r, int b)
{
	if (l==r || b< 0) {
		for (int i=l; i<=r; i++) C[B[i]] = 1;
		return;
	}
	int pl, pr; di(l, r, pl, pr, b);
	if (K&(1< 1) {
			printf("%d\n", ans);
			for (int i=1; i<=N; i++) if (C[i]) printf("%d ", i);
		} else puts("-1");
	}
}

题解做法：利用结论：

Suppose we have a set of numbers and we need to find minimal possible xor over all the pairs. It is true that, if we sort the numbers in non-descending order, the answer will be equal to minimal xor over neighboring numbers.

然后以集合最大值 i 为状态进行 dp[i]

E1, E2

括号匹配建树，发现自己从没写过（
好像也查不到什么有关的东西，可能太经典了没人打算写吧，那自己乱搞一个
经典的合法括号串的定义是：()是合法的；若A合法，则(A)合法；若A,B合法，则AB合法
对于一个括号序列，其每个括号对应的匹配是唯一的，整个序列包含了若干连续的极大合法子串，每个子串内形成一棵树，总体是一个森林
我的定义表示如图，每个括号用其左括号的下标表示，右括号不在树里（图里只是示意了一下），大于 N 的编号是虚点，每个虚点的儿子们为一个极大合法子串

这个树有一些显然而好用的性质：

1. 树的dfs序即 1 到 N
2. 同属于某个括号的儿子的若干连续的括号，它们的子树的编号是连续的

代码：

int L[MAXN<<1], R[MAXN<<1], tot; // 因为多开了虚点，所以空间开两倍
vector son[MAXN<<1];
stack stk;
void build(int p, int fa) // 对一个合法子串的内部建树，fa 不能为虚点
{
	if (p==R[fa]) return;
	son[fa].push_back(p);
	build(R[p]+1, fa), build(p+1, p);
}
void init()
{
	for (int i=1; i<=N; i++) {
		char c = S[i-1];
		if (c==')' && !stk.empty())
			R[stk.top()] = i, L[i] = stk.top(), stk.pop();
		if (c=='(') stk.push(i);
	}
	tot = N+1;
	int p = 1; while (!R[p]) p++;
	while (p<=N) {
		son[tot].push_back(p), build(p+1, p);
		p = R[p]+1; if (p> N) break;
		if (!R[p]) {
			while (p<=N && !R[p]) p++;
			if (p<=N) tot++;
		}
	}
}

其他一些有意思的trick见题目
由题目，我们很容易知道答案的计算方式：设 f[i] 表示括号 i 的串的合法子串的种类，则 \(f[i] = \sum{f[son]} + C^{2}_{sz} + 1\)，其中 sz 为 i 的儿子个数。我们可以根据这个做掉 E1
对于 E2，我们可以这么转化：每个节点的权值为 \(C^{2}_{sz} + 1\)，此时某个节点的 f 即其子树权值之和；对于操作删除某个叶子，等价于对其父节点的权值做修改，同时要能支持查询子树权值和——dfs序上用树状数组，而且刚好这里1到N就是dfs序
此外回答询问中（易知询问保证l和r所属的括号是同一个节点的儿子），我们还需要知道这两个同父的儿子之间一共有多少儿子（这是个有序树），怎么维护呢？
我的做法是，再开一个树状数组，对每个节点，其左括号处+1，右括号处（不是刚好右括号在dfs序上也有一个位置嘛！）-sz，sz 是其儿子个数，你会发现对于同父的儿子们来说，做前缀和之差时，即直接 sum[r]-sum[l-1]，各自底下节点都不会造成贡献，图示如下：

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MAXN = 300005;
int N, Q;
char S[MAXN];
int L[MAXN<<1], R[MAXN<<1], tot;
vector son[MAXN<<1];
stack stk;
void build(int p, int fa)
{
	if (p==R[fa]) return;
	son[fa].push_back(p);
	build(R[p]+1, fa), build(p+1, p);
}
void init()
{
	for (int i=1; i<=N; i++) {
		char c = S[i-1];
		if (c==')' && !stk.empty())
			R[stk.top()] = i, L[i] = stk.top(), stk.pop();
		if (c=='(') stk.push(i);
	}
	tot = N+1;
	int p = 1; while (!R[p]) p++;
	while (p<=N) {
		son[tot].push_back(p), build(p+1, p);
		p = R[p]+1; if (p> N) break;
		if (!R[p]) {
			while (p<=N && !R[p]) p++;
			if (p<=N) tot++;
		}
	}
}
// ll f[MAXN<<1], g[MAXN<<1];
int fa[MAXN<<1], sz[MAXN<<1];
ll C2(ll x) { return x*(x-1)/2; }
struct arrayTree {
	ll a[MAXN];
	arrayTree() { memset(a, 0, sizeof(a)); }
	int lb(int p) { return (p&(-p)); }
	void add(int p, ll x) { if (p) for (; p< MAXN; p+=lb(p)) a[p] += x; }
	ll sum(int p) { ll r=0; for (; p; p-=lb(p)) r+=a[p]; return r; }
} AT, ATg;
void dp(int x)
{
	sz[x] = son[x].size();
	for (int o=0; o< sz[x]; o++)
		dp(son[x][o]), fa[son[x][o]] = x, ATg.add(son[x][o], 1);
	if (x<=N) AT.add(x, C2(sz[x])+1), ATg.add(R[x], -sz[x]);
}
int main()
{
	scanf("%d%d%s", &N, &Q, S);
	init();
	for (int i=N+1; i<=tot; i++) dp(i);
	for (; Q; Q--) {
		int o, l, r; scanf("%d%d%d", &o, &l, &r);
		if (o==1) {
			int f = fa[l];
			AT.add(l, -1), ATg.add(l, -1);
			if (f> N) continue;
			AT.add(f, -(sz[f]-1)), sz[f]--;
			ATg.add(R[f], 1);
		} else {
			ll t = ATg.sum(r) - ATg.sum(l-1);
			printf("%lld\n", AT.sum(r)-AT.sum(l-1)+C2(t));
		}
	}
}