【LG3246】[HNOI2016]序列
题面
题解
60pts
对于每个位置(i)，单调栈维护它往左第一个小于等于它的位置(lp_i)以及往右第一个小于它的位置(rp_i)。
那么在左端点在((lp_i,i])，右端点在([i,rp_i))的所有区间中，
区间的贡献均为(a_i)(之所以取等情况不一样是防止算重或算漏)。
那么对于一个询问(L,R)，有
[Ans=sum_{i=L}^R (i-max(lp_i+1,L)+1)cdot (min(rp_i-1,R)-i+1)
]
100pts
考虑莫队，那么我们的难点主要就是怎么从区间([L,R])转移到区间([L,R+1])。
用ST表查一下([L,R+1])的最小值的位置(p)，则左端点在([L,p])的区间贡献均为(a[p])。
现在考虑左端点在([p+1,R+1])的贡献，记一个类似于前缀和的东西(f_i=f_{lp_i}+(i-lp_i)*a[i])，
则可以算出区间([p+1,R+1])的贡献为(f_{R+1}-f_p)，因为(f_i)相当于求(i)的(lp)，它(lp)的(lp)...
到(i)的贡献，而(p)必为某一个转移端点，所以成立。
向([L-1,R])转移同样维护一个(g_i=g_{rp_i}+(rp_i-i)*a[i])。
减法直接减去一个位置对区间的贡献即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
typedef long long ll;
const int MAX_N = 1e5 + 5;
const int LEN = 320;
int N, Q, a[MAX_N], bel[MAX_N];
struct Query { int l, r, id; } q[MAX_N], tmp[MAX_N];
bool operator < (const Query &lhs, const Query &rhs) {
if (bel[lhs.l] == bel[rhs.l]) return (bel[lhs.l] & 1) ? lhs.r < rhs.r : lhs.r > rhs.r;
else return bel[lhs.l] < bel[rhs.l];
}
int stk[MAX_N], top, lp[MAX_N], rp[MAX_N];
int st[18][MAX_N], bin[18], lg[MAX_N];
int query(int l, int r) {
int k = lg[r - l + 1];
if (a[st[k][l]] < a[st[k][r - bin[k] + 1]]) return st[k][l];
else return st[k][r - bin[k] + 1];
}
ll L[MAX_N], R[MAX_N], ans[MAX_N], Ans;
ll Ladd(int l, int r) {
int p = query(l - 1, r);
return 1ll * a[p] * (r - p + 1) + R[l - 1] - R[p];
}
ll Radd(int l, int r) {
int p = query(l, r + 1);
return 1ll * a[p] * (p - l + 1) + L[r + 1] - L[p];
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
freopen("cpp.out", "w", stdout);
#endif
N = gi(), Q = gi();
for (int i = 1; i <= N; i++) a[i] = gi();
for (int i = 1; i <= N; i++) bel[i] = (i - 1) / LEN + 1;
bin[0] = 1; for (int i = 1; i <= 17; i++) bin[i] = bin[i - 1] << 1;
for (int i = 2; i <= N; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= N; i++) st[0][i] = i;
for (int i = 1; bin[i] <= N; i++)
for (int j = 1; j + bin[i] - 1 <= N; j++)
if (a[st[i - 1][j]] < a[st[i - 1][j + bin[i - 1]]]) st[i][j] = st[i - 1][j];
else st[i][j] = st[i - 1][j + bin[i - 1]];
for (int i = 1; i <= Q; i++) {
int l = gi(), r = gi();
q[i] = (Query){l, r, i};
}
sort(&q[1], &q[Q + 1]);
stk[0] = 0;
for (int i = 1; i <= N; i++) {
while (a[stk[top]] >= a[i] && top) --top;
lp[i] = stk[top], stk[++top] = i;
}
top = 0, stk[0] = N + 1;
for (int i = N; i >= 1; i--) {
while (a[stk[top]] > a[i] && top) --top;
rp[i] = stk[top], stk[++top] = i;
}
for (int i = 1; i <= N; i++) L[i] = L[lp[i]] + 1ll * (i - lp[i]) * a[i];
for (int i = N; i >= 1; i--) R[i] = R[rp[i]] + 1ll * (rp[i] - i) * a[i];
int ql = 1, qr = 0;
for (int i = 1; i <= Q; i++) {
while (qr < q[i].r) ++qr, Ans += Radd(ql, qr - 1);
while (ql < q[i].l) Ans -= Ladd(ql + 1, qr), ++ql;
while (ql > q[i].l) --ql, Ans += Ladd(ql + 1, qr);
while (qr > q[i].r) Ans -= Radd(ql, qr - 1), --qr;
ans[q[i].id] = Ans;
}
for (int i = 1; i <= Q; i++) printf("%lld
", ans[i]);
return 0;
}