[Hnoi2016 day2]序列
问题描述
给定长度为n的序列：$a_1,a_2,…,a_n$记为a[1:n]。
类似地，a[l:r]（$1≤l≤r≤N$）是指序列：$a_l,a_{l+1},…,a_{r-1},a_r$。
若$1≤l≤s≤t≤r≤n$，则称a[s:t]是a[l:r]的子序列。
现在有q个询问，每个询问给定两个数l和r，$1≤l≤r≤n$，求a[l:r]的不同子序列的最小值之和。
例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。
输入格式
第一行包含两个整数n和q，分别代表序列长度和询问数。
接下来一行，包含n个整数，以空格隔开,第i个整数为$a_i$，即序列第i个元素的值。
接下来q行，每行包含两个整数l和r，代表一次询问。
输出格式
对于每次询问，输出一行，代表询问的答案。
样例输入
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
样例输出
28
17
11
11
17
提示
$1 ≤N,Q ≤ 100000,|A_i| ≤ 10^9$
这个做法非常的妙啊。
令$pre[i]$表示以$i$为区间右端点的所有区间的最小值之和。
令$Pre[i]$表示$pre[i]$的前缀和，即$[1,i]$的所有子区间的最小值之和。
令$suf[i]$表示以$i$为区间左端点的所有区间的最小值之和。
令$Suf[i]$表示$suf[i]$的后缀和，即$[i,n]$的所有子区间的最小值之和。
上述四个数组可以通过维护单调栈来$O(n)$求出。例如求$pre[i]$，只需要找到$i$左边第一个比$i$小的位置$j$，求可以求出$pre[i]$
考虑如何求解答案，对于一个询问$[L,R]$，那么先找到$[L,R]$的最小值$Min$和最小值的位置$pos$
对于左端点在$[L,pos]$，右端点在$[pos,R]$的区间，那么它的最小值一定是$Min$，可以$O(1)$统计。
对于左端点在$[L,pos-1]$，右端点在$[L,pos-1]$的区间，我们考虑$Suf[L]-Suf[pos]$，其中不仅有我们想要的，还有一部分是左端点在$[L,pos-1]$，右端点在$[pos,n]$的区间，考虑把它减掉，由于这些区间跨过了$pos$位置，那么他们的答案等价于$suf[pos]\times (pos-L)$，另一部分可以同理处理。
因此本题就只需要$RMQ$解决了。复杂度$O(n\log n)$，而且常数非常小
代码：
1 |
|