尝试学习 Min_25 筛，看了半天最终弃疗……
来写点 DS 题散心。
题面中二程度爆表。
以下 \(a_i = k_i\)。
翻译一下，题目的意思是：
对于每个有序数对 \((x,y),x < y\)，如果 \(a_x,a_y > \max\limits_{i = x + 1}^{y - 1} a_i\)，对答案产生 \(p_1\) 的贡献；如果 \(a_x > \max\limits_{i = x + 1}^{y - 1} a_i > a_y\) 或 \(a_y > \max\limits_{i = x + 1}^{y - 1} a_i > a_x\)，对答案产生 \(p_2\) 的贡献。
询问给定 \(l,r\)，求两个数都在 \([l,r]\) 内的数对的答案。
两种贡献都跟 \(\max\) 有关，所以我们可以考虑对于这个 \(\max\) 统计答案的贡献。
先不考虑多组询问，假设只求整个序列的答案。
设 \(left_i\) 表示 \([1,i)\) 中最后一个 \(> a_i\) 的数的位置，\(right_i\) 表示 \((i,n]\) 中第一个 \(> a_i\) 的数的位置。
这个东西随便用单调栈/双向链表/set 预处理就好了。
对于每个 \(i\)，显然 \(a_i = \max\limits_{i = left_i + 1}^{right_i - 1}\)。
所以 \((left_i,right_i)\) 产生 \(p_1\) 的贡献。
\((left_i,j),(k,right_i),i < j < right_i,left_i < k < i\) 产生 \(p_2\) 的贡献。
现在来考虑多组询问。
这个时候发现我们没辙了。
考虑离线。
对于第一种贡献，我们把询问按 \(r\) 排序，从 \(1 \to n\) 扫描，如果遇到一个位置 \(i\)，并有另外一个/多个位置 \(j\) 满足 \(i = right_j\)，就让数据结构上第 \(left_j\) 个数加上 \(p_1\)。
然后对于所有 \(r = i\) 的询问，查询数据结构上 \([l,r]\) 的和，即为第一种贡献。
注意这样子没法统计到形如 \((x,x + 1)\) 的数对的贡献，另外加上即可。
对于第二种贡献，我们先考虑 \((left_i,j),i < j < right_i\) 的情况，另一种倒过来即可。 把询问按 \(l\) 排序，从 \(n \to 1\) 扫描，遇到一个位置 \(i\)，并有 \(j\) 满足 \(i = left_j\)，就让数据结构上 \([j + 1,right_j)\) 加上 \(p_2\)。
对于 \(l = i\) 的询问，直接查询 \([l,r]\) 区间和。
数据结构用线段树就好了。
因为个人习惯，我顺便写了动态开点和标记永久化。
代码：
1 |
|