题解 CF1149C 【Tree Generator™】

· · 题解

码长文不易，点个赞吧。QwQ
UPD：修复部分错误

题目概述

中文翻译很清楚了。不过有一点是没有讲清楚的：关于如何使用树构建括号序列。

Dfs，每经过一条边，往下走就加入“(”，往上走就加入“)”。

题目分析

™好评

首先我们来证明一个引理。

引理1.1 若从序列中任取一段连续子序列，从中去掉所有匹配括号后，剩下的括号组成的路径一定为一条链，链长为剩下的子序列长。

以下是一个例子。
对于括号序列（（）（（））），其构成的树如下：
其中，若我们取：后六个括号（中文括号没法标红好烦啊）
其对应的即为从节点3到节点1的链。
我们可以发现，2-4-5-4-2的链在括号序列上因为匹配而被消掉了。
因此，括号匹配即表示这条链下去过，但又上来了，因此对答案没有贡献。
这是一个似曾相识的思想，可是我记不起是什么了\笑

这样，第二个引理就出现了。

引理1.2 树上直径长度即为任意区间去掉匹配括号后的长度的最大值。

考虑直径的构成情况。它只会有两种。

图有点龊，将就看吧。

第二种没有问题，但是第一种。注意到它也是可以被括号序列表示出来的。比如（）（（）（））选第5、6个括号。其实这点在刚刚的例子中已经体现出来了。

这时候我们给出第三个引理。

若我们给”(”赋值 +1，给”)”赋值 -1，则：

引理1.3 最长去匹配区间 = 最大的（将区间分成两段）后面的权值和 - 前面的权值和

这是为什么呢？我想你可能会有以下疑问：

Q：如果我把一个括号在分配时分成两半了怎么办啊？
A：依赖于负数权值，不会有任何影响。因为此时的值为 -1-(+1)=-2，对比之前的 -1+1=0，你只会选择之前的办法，根本不会考虑这种毫无用处的办法。

Q：对于）（）（））这种序列岂不是无法划分？
A：可以的，只需要全部划分到前半部分即可。

Q：（略加思考后）那你证明一下吧。
A：因为匹配的括号在灵魂拷问三连第一问中已经证明了是无用的（即贡献为0），所以整个序列可以被简化为以下三种：

1> ……（（（（（（……
2> ……））））））……
3> ……）））（（（……

对于第一种和第二种我们只需将中间位置移到左边和右边即可。而对于第三种，放到中间，所以后减前的好处就体现出来了——两边相减恰为答案。

那么，思考：如何维护相邻区间差最大值呢？

用线段树（废话）。

不妨设这个最长去匹配区间为Δ。

我们选择维护九个变量：区间和，左/右连续选值最大/小值，从左/右连续选值Δ最大值，选择整个区间Δ最大值，无限制连续选值Δ最大值（最终答案）。

接下来考虑如何向上更新。

区间和：直接加。
左/右连续选值最大值，无限制连续选值最大值：Can you answer these queries III
从左/右连续选值Δ最大值：以左为例，先给转移式：

lv[k]=max(max(lv[k<<1],lv[k<<1|1]-s[k<<1]),mv[k<<1]+lmx[k<<1|1])

这个真的画个图看一下就明白了。用到的思想就是，枚举中间点分别在左区间和右区间的情况，取max。

选择整个区间Δ最大值：同上一个的思想：

mv[k]=max(mv[k<<1]+s[k<<1|1],mv[k<<1|1]-s[k<<1])

无限制连续选值Δ最大值：同上一个的思想：

mm[k]=max(max(max(mm[k<<1],mm[k<<1|1]),lv[k<<1|1]-rmn[k<<1]),rv[k<<1]+lmx[k<<1|1])

这题就做完了。掐头去尾后40行都没有。

void Pushup(int k)
{
    s[k]=s[k<<1]+s[k<<1|1];
    lmx[k]=max(lmx[k<<1],s[k<<1]+lmx[k<<1|1]);
    rmx[k]=max(rmx[k<<1|1],s[k<<1|1]+rmx[k<<1]);
    lmn[k]=min(lmn[k<<1],s[k<<1]+lmn[k<<1|1]);
    rmn[k]=min(rmn[k<<1|1],s[k<<1|1]+rmn[k<<1]);
    lv[k]=max(max(lv[k<<1],lv[k<<1|1]-s[k<<1]),mv[k<<1]+lmx[k<<1|1]);
    rv[k]=max(max(rv[k<<1|1],s[k<<1|1]+rv[k<<1]),mv[k<<1|1]-rmn[k<<1]);
    mv[k]=max(mv[k<<1]+s[k<<1|1],mv[k<<1|1]-s[k<<1]);
    mm[k]=max(max(max(mm[k<<1],mm[k<<1|1]),lv[k<<1|1]-rmn[k<<1]),rv[k<<1]+lmx[k<<1|1]);
}
char S[maxn];
void Build(int k,int l,int r)
{
    if(l==r) return s[k]=(S[l]=='('?1:-1),lmx[k]=rmx[k]=max(s[k],0),lmn[k]=rmn[k]=min(s[k],0),lv[k]=rv[k]=mv[k]=mm[k]=1,void(0);
    int mid=l+r>>1;
    Build(k<<1,l,mid),Build(k<<1|1,mid+1,r);
    Pushup(k);
}
void Update(int k,int l,int r,int p,char d)
{
    if(l==r) return s[k]=(d=='('?1:-1),lmx[k]=rmx[k]=max(s[k],0),lmn[k]=rmn[k]=min(s[k],0),lv[k]=rv[k]=mv[k]=mm[k]=1,void(0);
    int mid=l+r>>1;
    if(p>mid) Update(k<<1|1,mid+1,r,p,d);
    else Update(k<<1,l,mid,p,d);
    Pushup(k);
}
char SWAP(char&x,char&y) {char z=y;y=x,x=z;}
signed main()
{
    int x,y;
    n=read()-1<<1,m=read(),rein(S+1);
    Build(1,1,n),printf("%d\n",mm[1]);
    while(m--) x=read(),y=read(),S[x]^S[y]?(SWAP(S[x],S[y]),Update(1,1,n,x,S[x]),Update(1,1,n,y,S[y])):void(0),printf("%d\n",mm[1]);
    return 0;
}