CF1625E2 Cats on the Upgrade

https://www.luogu.com.cn/problem/CF1625E2

考虑把括号序列对应的树形结构建出来（按照在串中出现的顺序，给一个点所有儿子也定一个顺序）
设 \(u\) 有 \(son_u\) 个儿子，则如果不考虑只取某个儿子中的一部分作为一个合法字串的情况（也就是必须取某几个连续的儿子），那么方案数是 \(f_u=\dfrac{son_u\cdot (son_u+1)}{2}\)
再加上只取某个儿子的一部分的情况，则 \(u\) 对应的答案就是 \(\sum_{x\in \operatorname{subtree}(u)} f_x\)
那么整个询问就是求一段连续的儿子的子树 \(f\) 值和，若共有 \(p\) 个儿子，就在加上 \(\frac{p*(p+1)}{2}\)

修改的时候对 \(f\) 的影响只体现在修改点的父亲上，放在 dfs 序上就变成了单点修改区间查询，树状数组即可
考虑询问时如何确定两个兄弟节点之间有多少节点（就是求上面的 \(p\)）
对每个结点再开一个树状数组，大小为儿子个数，一开始每个儿子处都插入 \(1\)，每删掉一个儿子就把它在父亲的树状数组中的位置标成 \(0\)，区间查询即可

如果把维护 \(f\) 的树状数组换成线段树来支持区间赋值为 \(0\)，这个做法可以做修改时 \(s[l\cdots r]\) 中间不保证全为 . 的情况

#define N 300006
#define M 600006
struct Graph{
	int fir[N],nex[M],to[M],tot;
	inline void add(int u,int v){
		to[++tot]=v;
		nex[tot]=fir[u];fir[u]=tot;
	}
	inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;
int n,m;
char s[N];
int stack[N],top;
int left[N],right[N];
int L[N],R[N],id[N],tot;
void build(int u,int l,int r){
	for(int i=l+1;i