题解：[CF2129C1] 追忆

· · 题解

Tip：本题正解不需要使用 bitset。

我常常追忆过去。

上场 Div.2 瞬间定格在我脑海。我将那场的 E 题分成 E1、E2、E3（不会做），整理成一道交互题。

询问之间亦有分别：合法括号串有贡献，而非法括号串没有。s 前 i 个字符中含有子串 () 的字符串询问了评测机便一定返回非零值，而更为普通平常的 )))...((( 字符串便会返回 0。追忆解法宛然如梦，二分查找第一个使得 1\sim i 的询问值非零的点则可以确定 s_{i-1}=\texttt (,s_i=\texttt )，过分模糊的字符串 )))...)))(((...(((（询问值始终为 0）却又会使得 s_1=\texttt ),s_n=\texttt (。只有二分出的位置，那恰到好处的左括号右括号位置，才能满足我对 AC 的苛求。

解法总在不经意间将我裹进题解的文字里。连续而非连续的 ()，确定和不确定的左右括号，种种线索协助着我从一个具体的字符串 s_i\texttt )s_{i+1}\texttt {)()} 开始询问（当 s_1=\texttt ( 时只会创造额外的 1 的贡献，s_2=\texttt ( 时会创造额外 2 的贡献，同时为 \texttt ( 时共有 6 个合法括号串。以此方式，一次询问可以处理 2 个字符）。

曾经的比赛无法重来，我也没有场切。但我仍然渴望在每一次比赛之后留有闲暇的时间，在一道题目前驻足，在补题的过程中瞭望赛时的自己，感受尽可能多的糖错。OI 的时光曾流过我的身体，我便心满意足。

AC 代码已经凝固，我带着回忆向前，只是时常疏于保管，bug 也在改变着各自的形态。这给我的 OI 带来些许挑战。

我该在何时退役？我问我自己。