CF1881G 题解

· · 题解

将字母看成 [0,25] 的数字。

每次修改都视为模 26 意义下的区间加法。

对于询问，注意题目要求没有任何回文子串，这等价于 {\forall i} \in [1,n], s_i \neq s_{i+1}, s_i \neq s_{i+2}，对此维护数据结构标记它们的相等关系。

想一想如何维护区间加法，以及 s_i 是否等于 s_{i+1} 或 s_{i+2}。

一次区间加法操作结束后，被修改区间内部相等关系不会有变化，主要考虑边界变化。设加法操作区间为 [l,r]，那么我们需要更新 l-1,l-2,r,r-1 位置的相等关系记录。

而查询操作，设区间为 [l,r] 则意味着 l \le {\forall i} \le {r-1}, s_i \neq s_{i+1}, l \le {\forall i} \le {r-2}, s_i \neq s_{i+2}。

第一种操作包含区间加法，单点查询（和区间加法共用数据结构，用于修改相等关系），单点修改（相等关系的标记，和区间加法独立）。

第二种操作包含区间查询（和第一种操作的单点修改共用数据结构，查询相等关系）。

显然可以树状数组，但我赛时脑子抽了，写了 250 整行分块，不过也 50min 写完一发 AC 了，反正是打星就图个愉快。

提交记录