本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-15 16:03:56

将字母看成 $[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 了，反正是打星就图个愉快。

提交记录