Problem
Description
给定长度为 \(n\) 的序列：\(a_1, a_2, \cdots , a_n\)，记为 \(a[1 \colon n]\)。类似地，\(a[l \colon r]\)（\(1 \leq l \leq r \leq N\)）是指序列：\(a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r\)。若 \(1\leq l \leq s \leq t \leq r \leq n\)，则称 \(a[s \colon t]\)是 \(a[l \colon r]\) 的子序列。
现在有 \(q\) 个询问，每个询问给定两个数 \(l\) 和 \(r\)，\(1 \leq l \leq r \leq n\)，求 \(a[l \colon r]\) 的不同子序列的最小值之和。例如，给定序列
\(5, 2, 4, 1, 3\)，询问给定的两个数为 \(1\) 和 \(3\)，那么 \(a[1 \colon 3]\) 有 \(6\) 个子序列 \(a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3]\)，这 \(6\) 个子序列的最小值之和为 \(5+2+4+2+2+2=17\)。Input Format
输入文件的第一行包含两个整数 \(n\) 和 \(q\)，分别代表序列长度和询问数。
接下来一行，包含 \(n\) 个整数，以空格隔开，第 \(i\) 个整数为 \(a_i\)，即序列第 \(i\) 个元素的值。 接下来 \(q\) 行，每行包含两个整数 \(l\) 和 \(r\)，代表一次询问。Output Format
对于每次询问，输出一行，代表询问的答案。
Sample
Input
5 55 2 4 1 31 51 32 43 52 5
Output
2817111117
Range
对于 \(100\%\) 的数据，\(1 \leq n,q \leq 100000 ,|a_i| \leq 10^9\)
Algorithm
莫队
Mentality
第一眼觉得做法和 \(HNOI2017\) 的影魔应该是一样的，然后发现由于这一题的区间最小值可能存在多个，那么影魔里的就完全不适用了 \(QwQ\) 。
那看着这个数据范围，我们能想到三种复杂度：\(nlog\) 、\(nlog^2\)、\(n\sqrt{n}\) 。
然后发现可以离线，询问是区间形式的，我们便不由得想到莫队了。
接下来考虑莫队里的计算步骤：从 \([l,r]\) -> \([l,r+1]\) 的增量，由于其他三个计算本质相同，不多做讨论。
首先，我们设 \(p\) 为区间 \([l,r+1]\) 的最小值所在位置，那么对于区间左端点在 \(l\sim p\) ，右端点在 \(r+1\) 的区间，它们的最小值肯定都是 \(a[p]\) 。则这一坨区间对答案的贡献为 \(a[p]*(p-l+1)\) 。
那剩下的左端点在 \(p+1\sim r\) 的区间的贡献呢？
其实我们可以稍加思考，就会发现我们应该考虑先处理出两个 \(ll[i],rr[i]\) 数组，分别是 \(i\) 左边第一个比 \(i\) 小的位置，\(i\) 右边第一个比 \(i\) 小的位置。
那么我们设 \(f_l[r+1]\) 右端点在 \(r+1\) ，而左端点在 \([1,r+1]\) 范围的区间的最小值之和：
\[ f_l[r+1]=(r+1-ll[r+1])*a[r]+(ll[r+1]-ll[ll[r+1]])*a[ll[r+1]]+\dots + 0 \]
也即按照区间最小值分段，只要右端点固定，那么区间的最小值肯定是连续相同的，我们一个个区间去计算就好了。
然后我们观察到反正这个式子是从 \(ll[r+1]\) 把值转移上来的，那我们自然可以写出如下 \(DP\) 式：
\[ f_l[r+1]=(r+1-ll[r+1])*a[r]+f_l[ll[r+1]] \]
不难发现，对于原式子中，我们沿着一段段连续的区间最小值计算答案，而对于其中任意一个 "\(ll[i]\)" ，我们只需要把后面那截砍掉，也即 \(f_l[r+1]-f_l[ll[i]]\) ，这显然就是右端点在 \(r+1\) ，左端点在 \([ll[i]+1,r+1]\) 这段范围内的区间最小值之和。
由于 \(p\) 已经是区间内最小的位置了，所以对于 \(p+1\sim r\) 这些点，它们的 \(ll[i]\) 的值要么就是 \(a[p]\) ，要么就不小于 \(a[p]\)。所以 \(p\) 一定是计算 \(r+1\) 的答案中的某个 "\(ll[i]\)" ，那我们只需要用 \(f_l[r+1]\) 减去 \(f_l[p]\) 即可得到左端点在 \(p+1\sim r\) 的区间的答案。
总结一下，\([l,r]\) -> \([l,r+1]\) 的增量为：
\[ a[p]*(p-l+1)+f_l[r+1]-f_l[p] \]
对于 \([l,r]\) -> \([l-1,r]\) 也同理，我们只需要处理出一个类似的 \(f_r\) 数组即可。
Code
#include#include #include #include using namespace std;int n, size, Q, a[100001];int minn[100001][18], pos[100001][18], Log[100001];int top, ll[100001], rr[100001], stack[100001];int L, R;long long ans, Ans[100001], fr[100001], fl[100001];struct node { int l, r, d;} k[100001];bool cmp(node a, node b) { return (a.l / size) == (b.l / size) ? a.r < b.r : (a.l / size) < (b.l / size);}int find(int l, int r) { if (l > r) return 0; if (l == r) return pos[l][0]; int x = Log[r - l], p; return minn[l][x] > minn[r - (1 << x) + 1][x] ? pos[r - (1 << x) + 1][x] : pos[l][x];} //寻找最小值位置void init() { cin >> n >> Q; size = sqrt(n); int now = 2; for (int i = 2; i <= (int)1e5; i++) { Log[i] = Log[i - 1]; if (i == now) Log[i]++, now <<= 1; } //预处理对数 for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); minn[i][0] = a[i], pos[i][0] = i; } for (int i = 1; i <= Q; i++) scanf("%d%d", &k[i].l, &k[i].r), k[i].d = i; sort(k + 1, k + Q + 1, cmp); //离线询问 for (int j = 1; j <= 17; j++) for (int i = 1; i <= n - (1 << j) + 1; i++) { pos[i][j] = pos[i][j - 1], minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]); if (minn[i][j] != minn[i][j - 1]) pos[i][j] = pos[i + (1 << (j - 1))][j - 1]; } //预处理 rmq stack[top = 0] = 0; for (int i = 1; i <= n; i++) { while (top && a[stack[top]] >= a[i]) top--; ll[i] = stack[top], stack[++top] = i; } for (int i = 1; i <= n; i++) fl[i] = fl[ll[i]] + 1ll * (i - ll[i]) * a[i]; stack[top = 0] = n + 1; for (int i = n; i >= 1; i--) { while (top && a[stack[top]] >= a[i]) top--; rr[i] = stack[top], stack[++top] = i; } //单调栈处理 ll，rr 数组 for (int i = n; i >= 1; i--) fr[i] = fr[rr[i]] + 1ll * (rr[i] - i) * a[i]; //计算 fl，fr 数组}long long workr(int x) { int p = find(L, x); return 1ll * a[p] * (p - L + 1) + fl[x] - fl[p];}long long workl(int x) { int p = find(x, R); return 1ll * a[p] * (R - p + 1) + fr[x] - fr[p];}void solve() { L = k[1].l, R = k[1].l - 1; for (int i = 1; i <= Q; i++) { while (R < k[i].r) ans += workr(++R); while (L > k[i].l) ans += workl(--L); while (R > k[i].r) ans -= workr(R--); while (L < k[i].l) ans -= workl(L++); Ans[k[i].d] = ans; }}int main() { init(); //预处理和读入 solve(); for (int i = 1; i <= Q; i++) printf("%lld\n", Ans[i]);}