题解：P13274 [NOI2025] 三目运算符

· · 题解

前言

不是，什么年头连我都会做两道国赛题了，这题有点水。

思路

这题一眼线段树。

首先想到先考虑长度最小时的状况，即长度为 3 的串怎么变。

我们发现除了 101 和 110 以外的串都不会变化，所以那些形式的串我们暂且不管。

先说说 110，容易发现 110X 在一次变化后会变成 X110，这里的 X 表示未知数字。然后你会发现这个变化似乎很像一个操作，即把 110 整体往后移一格。因此，若线段树树维护区间存在 110，那么要找到最左边的 110 的开头位置，计为第 x 位，则答案为 len-x+1，len 为区间长度，区间合并时答案做加法，如果你合并有疑问下面会说。

再说说 101，101 只能变成 XX0，其中有作用的只有 110，似乎问题棘手起来，但容易发现的是，这个 110 必须是前面的 110 右移过来，所以这个情况应该扔给上面所讲的那个部分处理。

好，怎么合并呢？我们只需要几个判断语句在合并时判断中间夹不夹着 101 和 110 即可。

话说不会合并的也不会来做这题吧。

现在带上区间修改，由于 01 反转，再维护一下 010 和 001 即可，毕竟人家摇身一变，就反转成 101 和 110 了。

好了，讲完了。