区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。 例如二维前缀和求法： $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题：NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…

题目链接。 解析 考虑最终序列。由于序列较长，先考虑序列短小的情况，即长度为 $3$ 时。 对于一个长度为 $3$ 的序列 $S_{1,2,3}$，要使其不存在回文串，需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$，你发现这三个字母必须是互不相同的，由于字符串仅由三种字母组成，最终序列的前三个字母一定是以下六种…

题意 题目链接。 数轴上有若干传送门，初始是关闭或开启。对于关闭的传送门，经过后就会开启；对于开启的传送门，到达后会被传送到一个位置，然后会关闭。求从 $0$ 点走到 $x_n+1$，即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门，则记 $f_…