本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 22:42:04

记录

赛时在车上还很困，A 都没做出来直接跑了。CD 老师讲了，写一下记录。

题解

A - ABA and BAB

发现对于每个长度为奇数且相邻两个字母不相同的子串，都可以删除其中任意多个 AB（或者说是 BA），也就是长为 $k$ 的子串可以有 $\frac{k+1}2$ 种结果。所以对于每个这样的极长子串记录方案数，乘法原理乘起来即可。

这样不会算重是因为两段之间一定是互不影响的，而且相邻两个极长段之间要么字符相同，要么是极长段长为偶数多出来的，都会有字符分隔，所以乘法原理正确。

C - Subsequence and Prefix Sum

发现会影响接下来操作的只有目前的前缀和，而不关心这个前缀和是怎么来的。又因为值域小，总和的绝对值不超过 $1000$，可以设入状态，设 $f_{i,j}$ 表示前 $i$ 位中目前前缀和为 $j$ 的方案数。

所以不选 $i$ 时有 $f_{i,j}=f_{i,j}+f_{i-1,j}$，否则有 $f_{i,j+a_i}=f_{i,j+a_i}+f_{i-1,j}(j\ne0)$。这里 $j$ 不等于 $0$ 是因为如果用 $0$ 来转移，那么 $a_i$ 不会有变化，会导致计重。

所以设 $g_i$ 表示上一次为 $0$ 又加上了 $i$ 的方案数，每次令 $g_{a_i}=g_0,g_0=f_{i,0}$ 即可。前面的转移也会变成 $f_{i,j+a_i}=f_{i,j+a_i}+f_{i-1,j}+g_j(j\ne0)$，这样就没问题了。

D - Division into 3

先考虑朴素做法，发现区间内的最大值一定会贡献到答案里。那么分这个最大值 $p$ 在哪一段讨论。若在第二段，那么左右各取最边上的一个一定最优。若在两边，那么中间的第二段只取一个一定不劣，这里假设取左边的第一段，那么就要求 $i\in[p+1,r-1]$ 使得 $a_i+\max_{k=i+1}^r a_k$ 最小。

考虑把所有这样的询问 $[p,r]$ 离线下来，然后对整个长度为 $n$ 的区间操作。发现 $a_i$ 只会影响到 $[k,i-1]$ 这段区间，其中 $a_k$ 是 $i$ 前面最近的大于 $i$ 的数。那么所有最终有影响的 $a_i$ 一定单调递减，可以用个单调栈维护。

所以设 $f_i$ 表示处理到目前的 $r$ 时的 $a_i+\max_{k=i+1}^r a_k$，如果能在依次处理每一个元素的同时维护这个数组，那只要在处理完了询问的 $r$ 后求 $[p+1,r-1]$ 区间的 $f_i$ 最小值即可。那么每处理到 $i$ 就给 $f_{i-1}$ 赋值 $a_{i-1}+a_i$，然后维护单调栈，弹出元素 $x$ 时意味着 $x$ 的上一个元素直到 $x-1$ 这一段区间 $f_i$ 中的最大值不能取 $a_x$ 而是要取 $a_i$ 了，所以这段要加上 $a_i-a_x$。

综上，要支持的操作有：

• 单点修改
• 区间加
• 区间求最小值

所以线段树就行了。