HNOI 2016 序列(RMQ+单调栈)

[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
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
#include<stdio.h>
#define N 100005
#define ll long long
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
char t=GC;bool f=0;
while((t<48||t>57)&&t!='-')t=GC;
if(t=='-')f=1,t=GC;
for(x=0;t>47&&t<58;t=GC)x=(x<<1)+(x<<3)+t-48;
x=f?-x:x;
}
int n,q,A[N],F[N][20],S[N],T=17;
ll suf[N],Suf[N],pre[N],Pre[N],Log[N];
int RMQ(int l,int r)
{
int k=Log[r-l+1],t=r-(1<<k)+1;
return A[F[l][k]]<A[F[t][k]]?F[l][k]:F[t][k];
}
int main()
{
register int i,j,k,x,y,Min,top;
_R(n);_R(q);Log[1]=0;
for(i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
for(i=1;i<=n;i++)_R(A[i]);
for(i=1;i<=n;i++)F[i][0]=i;
for(i=n;i>=1;i--)
for(j=1;j<=Log[n-i+1];j++)F[i][j]=A[F[i][j-1]]<A[F[i+(1<<j-1)][j-1]]?F[i][j-1]:F[i+(1<<j-1)][j-1];
for(i=n;i>=1;i--)
{
while(top&&A[i]<A[S[top]])top--;
suf[i]=top?suf[S[top]]+1ll*(S[top]-i)*A[i]:suf[i]=1ll*(n-i+1)*A[i];
Suf[i]=Suf[i+1]+suf[i];
S[++top]=i;
}
for(i=1,top=0;i<=n;i++)
{
while(top&&A[i]<A[S[top]])top--;
pre[i]=top?pre[S[top]]+1ll*(i-S[top])*A[i]:pre[i]=1ll*i*A[i];
Pre[i]=Pre[i-1]+pre[i];
S[++top]=i;
}
for(i=1;i<=q;i++)
{
_R(x);_R(y);
Min=RMQ(x,y);
printf("%lld\n",1ll*(Min-x+1)*(y-Min+1)*A[Min]+Suf[x]-Suf[Min]-1ll*(Min-x)*suf[Min]+Pre[y]-Pre[Min]-1ll*(y-Min)*pre[Min]);
}
}