Description:
奈文摩尔有 \(n\) 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 \(1\) 到 \(n\)。第 \(i\) 个灵魂的战斗力为 \(k_i\)，灵魂们以点对的形式为影魔提供攻击力。对于灵魂对 \(i, j\) 来说，若不存在 \(k_s\\) 大于 \(k_i\) 或者 \(k_j\)，则会为影魔提供 \(p_1\) 的攻击力。另一种情况，令 \(c\) 为 \(k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}\) 的最大值，若 \(c\) 满足：\(k_i ; c > k_j\)，或者 \(k_j lt; c lt; k_i\)，则会为影魔提供 \(p_2\) 的攻击力，当这样的 \(c\) 不存在时，自然不会提供这 \(p_2\) 的攻击力；其他情况的点对，均不会为影魔提供攻击力。
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间
\([a, b]\)，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足
\(a\le ilt;j\le b\) 的灵魂对
\(i, j\) 提供的攻击力之和。
顺带一提，灵魂的战斗力组成一个
\(1\) 到
\(n\) 的排列：
\(k_1, k_1, \cdots, k_n\)。
Hint:
对于 \(30\%\) 的数据，\(1\le n, m\le 500\)。
另有
\(30\%\) 的数据，
\(p_1 = 2p_2\)。
对于
\(100\%\) 的数据，
\(1\le n,m\le 200000, 1\le p_1, p_2\le 1000\)。
Solution:
这题直接统计不好统计
我们反过来考虑每个位置对区间的贡献
首先预处理出每个位置左右第一个大于它的位置
1.\(i\)对于区间(\(l[i] ,r[i]\)),有\(p_1\)的贡献,我们在扫到\(r[i]\)更新\(l[i]\)即可
2.\(i\)对于所有区间\((l[i],i+1 \text{~} r[i]-1)\) 有\(p_2\)的贡献,我们在扫到\(l[i]\)时更新\(i+1 \text{~} r[i]-1\)
3.\(i\)对于所有区间\((l[i]+1\text{~}i-1,r[i])\) 有\(p_2\)的贡献,我们在扫到\(r[i]\)时更新\(l[i]+1\text{~}i-1\)
然后把询问离线拆成\(l,r\)后按端点排序,每次询问区间\(l~r\)的和,答案就是两次询问相减
注意要特判相邻位置的贡献
update:
今天体育课ysbs给我讲了一个更优秀的方法,实际上没必要处理出每个点的左右边界
对于贡献2,我们只要枚举所有以该点为右端点的区间,单调栈维护最近的大于该点的位置
分为左大于右和左小于右两种情况分别做一次就行,这样稍微方便一些
#include