首先我们亲爱的 zyr 同学在 2 道几乎一样的括号序列题上面用了 2 种不同的方式来维护 pushup,而这和每道题题解的趋势几乎一致。
但是我直接交的他的代码。
所以写一下 zyr 队爷的思路。
以下直接设 (
为 \(1\),)
为 \(-1\)。
一、结论法
答案为右最大前缀和 - 左最小后缀和。(跨越区间)
根据这个,类似 https://www.becoder.com.cn/article/15845 那样维护即可。(真是碰巧,完全一样维护)
二、暴力法
每次 pushup 合并左右括号,并统计答案。
发现有些东西是需要保留原始的状态的(先不消除合法括号)。
由于你合并的时候是这样子的:
\(L_{lnxt} + |L_{rnxt}-R_{lpre}|+R_{rpre}\)
\(lnxt\) 表示后缀中的 )
个数。
所以暴力拆绝对值,维护 \(lnxt+rnxt,lnxt-rnxt,lpre+rpre,rpre-lpre\) 即可。代码:
void pushup(int p) {
if(T[p << 1].lsum > T[p << 1 | 1].rsum) T[p].rsum = T[p << 1].rsum, T[p].lsum = T[p << 1].lsum + T[p << 1 | 1].lsum - T[p << 1 | 1].rsum;
else T[p].lsum = T[p << 1 | 1].lsum, T[p].rsum = T[p << 1].rsum + T[p << 1 | 1].rsum - T[p << 1].lsum;
T[p].pre1 = max({T[p << 1].pre1, T[p << 1].rsum + T[p << 1].lsum + T[p << 1 | 1].pre2, // 多一点 ((
T[p << 1 | 1].pre1 + T[p << 1].rsum - T[p << 1].lsum}); // 多一点 ))))
// 表示的是 ))(((
T[p].pre2 = max({T[p << 1].pre2, T[p << 1 | 1].pre2 + T[p << 1].lsum - T[p << 1].rsum});
// 表示 (((((( 且前面 )) 被减去
T[p].nxt1 = max({T[p << 1 | 1].nxt1, T[p << 1].nxt1 + T[p << 1 | 1].lsum - T[p << 1 | 1].rsum,
T[p << 1].nxt2 + T[p << 1 | 1].lsum + T[p << 1 | 1].rsum});
T[p].nxt2 = max({T[p << 1 | 1].nxt2, T[p << 1].nxt2 + T[p << 1 | 1].rsum - T[p << 1 | 1].lsum});
T[p].maxn = max({T[p << 1].maxn, T[p << 1 | 1].maxn, T[p << 1 | 1].pre1 + T[p << 1].nxt2,
T[p << 1 | 1].pre2 + T[p << 1].nxt1});
}
// 维护 pre(R + L) pre(L - R)
// nxt(R + L) nxt(R - L)
// 参考:)( 是 RL 的
好像式子的 \(l,r\) 写反了。
标签:rnxt,lnxt,匹配段,浅谈,lpre,括号,pushup,维护,最长 From: https://www.cnblogs.com/LCat90/p/18284512