感觉很深刻啊！感觉那么不可做的问题，分个类突然就十分容易了啊！
CF1801G
给定一个字符串 \(t\) 和 \(n\) 个字符串 \(s_1, s_2, s_3, \dots, s_n\)
\(m\) 次询问 \(t[l_i, r_i]\) 中出现了多少次 \(s_1, s_2, \dots, s_n\) 中的字符串
Solution
考虑寻找最后一个点 \(q \in [l, r]\) 使得存在 \(p < l\) 使得 \(t[p, q] = s_i\)
从而对于任意 \(y \in (q, r]\)，直接预处理以 \(y\) 为右端点的 \(s_i\) 个数即可，而 \([l, q]\) 内的 \(s_i\) 个数相当于 \([p, q]\) 的一个后缀，\(\sum |s_i|\) 预处理即可
nfls 2024-1-13 模拟赛 螺旋
给定长度为 \(n\) 的序列 \(a\)，\(q\) 次询问 \([l, r]\) 内最长的子段 \([p, q]\) 使得 \(\max(a_{p \sim q}) = a_p = a_q\)
Solution
考虑寻找区间 \([l, r]\) 的第一个最大值 \(p\) 和最后一个最大值 \(q\)
则最大值的贡献为 \(q - p + 1\)，并且在 \([p, q]\) 之间的数字是无用的，并预处理 \([l, p)\) 作为左端点与 \((q, r]\) 作为右端点的答案即可
[HNOI2016] 序列
给定长度为 \(n\) 的序列 \(a\)，\(q\) 次询问，区间 \([l, r]\) 的不同子区间的最小值之和
Solution
考虑寻找区间 \([l, r]\) 的最小值 \(a_x = p\)，则其有 \((x - l + 1)(r - x + 1)p\) 的贡献
对于最小值左边的 \(u \in [l, x)\)，则对于 \(v \ge x\)，\(\min(a_{u \sim v}) = \min(a_{x \sim v})\)，考虑预处理 \(u\) 作为左端点的答案之和 \(f\)，则 \(u\) 的贡献即为 \(f_u - f_x\)，右侧同理即可