「鲜花」2023.9.28 旧事重提

https://www.luogu.com.cn/paste/zuy6eopx

https://www.luogu.com.cn/paste/1rj3m6z7

***神话**一则*

在 A 星球上有一个名为 B 的谷，在谷的底部生活着无数青蛙：

每月在谷中只能看见月亮掠过谷几个小时，却很难以看到太阳。

谷很深很深，青蛙们世世代代尝试爬到谷外。

谷内的燃料能量非常大，以至于科学家们研发的火箭可以在每月的月亮耀谷时期送青蛙到月球上探索再返回，却不能送青蛙到谷外。于是每月青蛙们都会去往月亮寻找燃烧时恰好能够逃离谷的燃料，这是他们唯一的出路。

火箭技术只掌握在科学家手中，所以科学家掌控了所有的实权。

在 107 号登月探索中，一名在 Balkan 旅游过的沙东青蛙 C，发现他所到的月球上竟然是 Balkan 中的一块儿地伪装起来的，其实他们还在谷中的 Balkan 地区！

C 有些愤怒，但碍于科学家的颜面并没有明说，只是从包中拿出 Balkan 的特产问大家见没见过。

这个特产是给定一个括号串 $S$，多次询问区间 $[L,R]$ 中至少删去多少个括号使得正反都是一个括号串。这个问题怎么做呢？

先转化成 $1,-1$，使得前缀和都 $\geq 0$，后缀和都 $\geq 0$．暴力怎么做？前搞出前缀和，然后把如果前缀 $\min$ 更新为负数了就贪心改掉，然后再倒过来改。需要把这个过程写成式子的形式：先花费 $-\min\{pre_k\}$，然后考虑 $i$ 后缀删的个数就 $(-\min\{pre_k\})-(-\min_{j<i}\{pre_j\})$ 即 $suf'_i=suf_i+(-\min\{pre_k\})-(-\min_{j<i}\{pre_j\})$，然后再花费 $-\min\{suf'_i\}$．

那么总的花费就是：$-\min\{pre_k\}-\min\{suf'_i\}=-\min\{pre_k\}-\min\{suf_i+(-\min\{pre_k\})-(-\min_{j<i}\{pre_j\})\}$．

$=-\min_{j<i}\{suf_i+pre_j\}$，所以只需要线段树维护分治信息就行可以了！

科学家得知了这件事，立马堵住了 C 的嘴，告知他不要妄想动了“月亮”的威严。

这一切都被 C 的朋友看到，他们也恐惧于科学家的统治，便在民间传起了月亮具有神奇力量的都市传说。大家愈发相信月亮具有神力，就愈发向往月亮，当传说与青蛙们的唯一追求所契合时，便产生了宗教。

拜月教就此诞生。尽管人们忘记了或许从未了解过一切的伊始，所有含义在不断的解构中重组，成为了人们想要的。

后来 C 背井盖离乡，骑着酒精柚子炮弹走了。

当然这只是一个神话故事，无非是一些人臆想出来的歇斯底里的狂欢而已。

9.29 upd：中秋节快乐。

9.30 upd：解释一下吗？

谷就是指的洛谷，来自 Balkan 的特产可以通过[搜索](https://cn.bing.com/search?q=Balkan+%E5%A4%9A%E6%AC%A1%E8%AF%A2%E9%97%AE%E5%8C%BA%E9%97%B4%5BL%2CR%5D%E4%B8%AD%E8%87%B3%E5%B0%91%E5%88%A0%E5%8E%BB%E5%A4%9A%E5%B0%91%E4%B8%AA%E6%8B%AC%E5%8F%B7%E4%BD%BF%E5%BE%97%E6%AD%A3%E5%8F%8D%E9%83%BD%E6%98%AF%E4%B8%80%E4%B8%AA%E6%8B%AC%E5%8F%B7%E4%B8%B2&PC=U316&FORM=CHROMN)得知是 P4786 这个题，打开[讨论区](https://www.luogu.com.cn/discuss/432606)是 2022-4-23 月赛题，找到 2022-4-23 的[月赛](https://www.luogu.com.cn/contest/67366)，其 D 题和这个题完全一样。

C 是指的一名沙东选手，他在 Balkan 那个题讨论区发了个询问猫树做法的帖子被管理员删除并警告发现原题不要传播。后面拜月教确实就是拜月教。权当一个小故事，如果解读为当下在国内网络环境下【数据删除】似乎也可以。

正在渲染内容...