「BZOJ4540」[HNOI2016]序列

Description

给定长度为nn的序列:a1,a2,,ana_1, a_2, \cdots , a_n,记为a[1 ⁣:n]a[1 \colon n]。类似地,a[l ⁣:r]a[l \colon r]1lrN1 \leq l \leq r \leq N)是指序列:al,al+1,,ar1,ara_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r。若1lstrn1\leq l \leq s \leq t \leq r \leq n,则称a[s ⁣:t]a[s \colon t]a[l ⁣:r]a[l \colon r]的子序列。

现在有qq个询问,每个询问给定两个数llrr1lrn1 \leq l \leq r \leq n,求a[l ⁣:r]a[l \colon r]的不同子序列的最小值之和。例如,给定序列
5,2,4,1,35, 2, 4, 1, 3,询问给定的两个数为1133,那么a[1 ⁣:3]a[1 \colon 3]66个子序列a[1 ⁣:1],a[2 ⁣:2],a[3 ⁣:3],a[1 ⁣:2],a[2 ⁣:3],a[1 ⁣:3]a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3],这66个子序列的最小值之和为5+2+4+2+2+2=175+2+4+2+2+2=17

Input

输入文件的第一行包含两个整数nnqq,分别代表序列长度和询问数。
接下来一行,包含nn个整数,以空格隔开,第ii个整数为aia_i,即序列第ii个元素的值。
接下来qq行,每行包含两个整数llrr,代表一次询问。

Output

对于每次询问,输出一行,代表询问的答案。

Sample Input

1
2
3
4
5
6
7
5 5 
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

Sample Output

1
2
3
4
5
28 
17
11
11
17

HINT

对于 100%100\% 的数据,$ 1 \leq n,q \leq 100000 ,|a_i| \leq 10^9$

Solution

莫队

考虑如何从[l,r][l,r]转移到[l,r+1][l,r+1]
fjf_{j}表示表示右端点在jj,左端点在[1,j][1,j]的区间答案。
prejpre_{j}定义为[1,j][1,j]第一个小于aia_i的位置,不存在等于自身。
显然fj=fprej+(jprej)×aprejf_{j}=f_{pre_{j}}+(j-pre_j)\times a_{pre_j}
假设pp[l,r+1][l,r+1]中最小的数的位置编号;
那么[l,r+1][l,r+1]的贡献就是fr+1fp+(r+1p+1)×apf_{r+1}-f_p+(r+1-p+1)\times a_p

不能直接用fr+1fl1f_{r+1}-f_{l-1}算答案。
fr+1=ar+1×(r+1prer+1)++ap×(pprep)f_{r+1}=a_{r+1}\times (r+1-pre_{r+1})+\cdots+ a_{p}\times (p - pre_p)
fl1=al1×(l1prep1)++ap×(pprep)f_{l-1}=a_{l-1}\times(l-1 - pre_{p-1})+\cdots+a_p\times (p-pre_p)
如果r+1r+1里有个prepre等于l1l-1可以满足
如果r+1r+1里没有prepre等于l1l-1,那么显然是错的。

如果pp是最小值,保证了[l,p][l,p]的答案是(pl+1)×ap(p-l+1)\times a_p 剩下的就变成了右端点在j+1j+1,左端点在[p+1,j+1][p+1,j+1]的问题了。这里fj+1fpf_{j+1}-f_p,保证了fj+1f_{j+1}的答案是经过pp算过来的,所以满足前缀的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120000;

int n, m;
ll a[N];
int lg[N], g[N][21];
ll fl[N], fr[N];
int top, st[N];
int get(int x, int y) {
int t = lg[y - x + 1];
if(a[g[x][t]] < a[g[y - (1 << t) + 1][t]]) return g[x][t];
return g[y - (1 << t) + 1][t];
}
void init() {
for(int i = 1; i <= n; ++i) g[i][0] = i;
for(int j = 1; j <= 17; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
if(a[g[i][j - 1]] < a[g[i + (1 << (j - 1))][j - 1]])
g[i][j] = g[i][j - 1];
else
g[i][j] = g[i + (1 << (j - 1))][j - 1];
for(int i = 2; i <= n; ++i) lg[i] = lg[i>>1]+1;
for(int i = 1; i <= n; ++i) {
while(top && a[st[top]] >= a[i]) --top;
if(top) {
fl[i] = fl[st[top]] + (i - st[top]) * a[i];
}
else fl[i] = i * a[i];
st[++top] = i;
}
top = 0;
for(int i = n; i; --i) {
while(top && a[st[top]] >= a[i]) --top;
if(top) {
fr[i] = fr[st[top]] + (st[top] - i) * a[i];
}
else
fr[i] = (n - i + 1) * a[i];
st[++top] = i;
}
}
struct T {
int l, r, i;
}q[N];
int block;
bool cmp(T x, T y) {
if(x.l / block != y.l / block) return x.l < y.l;
return x.r < y.r;
}
ll ans[N];
ll getl(int x, int y) {
int p = get(x, y);
return fr[x] - fr[p] + (y - p + 1) * a[p];
}
ll getr(int x, int y) {
int p = get(x, y);
return fl[y] - fl[p] + (p - x + 1) * a[p];
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
init();
for(int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].i= i;
block = sqrt(n) + 1;
sort(q +1, q + 1 + m, cmp);
int l = 1, r = 1;
ll res = fl[1];
for(int i = 1; i <= m; ++i) {
while(r < q[i].r) res += getr(l, r + 1), ++r;
while(l > q[i].l) res += getl(l - 1, r), --l;
while(l < q[i].l) res -= getl(l, r),++l;
while(r > q[i].r) res -= getr(l, r), --r;
ans[q[i].i] = res;
}
for(int i = 1; i <= m; ++i)
writeln(ans[i]);
return 0;
}

树状数组

对于一个位置xx,处理处左边第一个比他小和右边第一个比他小的数的位置,分别记做Lx,RxL_x,R_x
相当于[l,r](LxlrRx)[l,r] (L_x\leq l\leq r\leq R_x)矩形里的数,他的值都等于axa_x
对于询问区间[l,r][l,r],就是查询矩形左下角为(l,l)(l,l)右上角为(r,r)(r,r)的矩形里的数字之和。