BZOJ 4540 Hnoi2016 序列 ST表+单调栈

本文主要是介绍BZOJ 4540 Hnoi2016 序列 ST表+单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4540: [Hnoi2016]序列

Time Limit: 20 Sec Memory Limit: 512 MB

Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。若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。

Input

　　输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。

Output

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

Sample Input

5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

Sample Output

28
17
11
11
17

HINT

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

首先膜一波pwj大神，本题做法由他提供。小常数 $O(nlogn)$ 碾压标算线段树和莫队算法，代码还很短。

首先容易处理以 $a_1$ 为起点的所有区间的答案：考虑增量法。

左端点固定在1，右端点从 $r-1$ 变成 $r$ 时，增加的贡献就是以 $r$ 为右端点的区间的最小值之和。设以 $r$ 为右端点的所有区间的最小值之和为 $pre[r]$ ， $r$ 左边第一个比 $r$ 大的位置为 $pos$ ，那么有：

p r e [r] = p r e [p o s] + (r - p o s) a r

$pre[r]=pre[pos]+(r-pos)a_r$
求以1为左端点，某个点为右端点的区间的答案只需要对

pre p r e $pre$ 做一次前缀和即可。

对称一下也可以求以 $n$ 为右端点的所有区间的答案，以及以 $l$ 为左端点的所有区间最小值之和 $suc$ 。这些都可以通过单调栈 $O(n)$ 处理。

现在考虑如何利用刚才得到的几个数组处理区间 $[l,r]$ 的答案。
这里写图片描述
首先需要找到区间中最小值的位置 $Min$ 。考虑把这段区间的答案拆成三个部分：右端点在 $Min$ 左边的所有区间的答案、左端点在 $Min$ 右边的所有区间的答案、跨过 $Min$ 的区间的答案。容易看出，这三部分加起来就是最终答案，而且前两部分答案本质相同，所以接下来讨论解决两个问题即可：

1.右端点在 $Min$ 左边的所有区间的答案
2.跨过 $Min$ 的区间的答案

问题2的答案显然是 $(r-Min+1)(Min-l+1)a_{Min}$ 。

对于问题1，先凭感觉写出 $sum\_suc[l]-sum\_suc[Min]$ ，这包含了哪些区间的最小值之和呢？思考一番发现算多了：不仅有我们想要的答案，还包含了左端点在 $[l , Min-1]$ ，右端点在 $[Min+1,n]$ 的所有区间的最小值之和。由于这样的区间跨过了 $Min$ ，而 $a_{Min}$ 是区间中最小的数，因此，对于每一个左端点 $\in[l,Min-1]$ 的所有区间的最小值之和，其答案就是 $suc[Min]$ 。这样就得出了问题1的答案。

可以看到，只要得到了 $Min$ 的位置，就能够 $O(1)$ 得到答案。而对于无修改的区间极值的询问可以采用ST表做到 $O(nlogn)$ 预处理， $O(1)$ 询问。所以总时间复杂度为 $O(nlogn)$ 。

注意预处理 $log$ 代替cmath里函数的使用以减小常数。

#include<stdio.h>
#include<algorithm>
#define MAXN 400005
#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 int _R(){char s=GC;int sign=0,v=0;while((s!='-')&&(s>57||s<48))s=GC;if(s=='-')s=GC,sign=1;for(;s>47&&s<58;s=GC)v=v*10+s-48;return sign?-v:v;
}int N,Q,A[MAXN];
int S[MAXN],Top;
ll pre[MAXN],suc[MAXN],sp[MAXN],ss[MAXN],Ans;int Log[MAXN],ST[MAXN][20];int GetMin(int l,int r){int len=r-l+1,k;k=Log[len];return A[ST[l][k]]<A[ST[r-(1<<k)+1][k]]?ST[l][k]:ST[r-(1<<k)+1][k];
}int main(){int i,j,l,r,Min;N=_R();Q=_R();for(i=1;i<=N;i++)A[i]=_R();for(i=1;i<=N;i++){while(Top&&A[S[Top]]>A[i])Top--;pre[i]=(ll)A[i]*(i-S[Top])+pre[S[Top]];S[++Top]=i;sp[i]=sp[i-1]+pre[i];}Top=0;S[0]=N+1;for(i=N;i;i--){while(Top&&A[S[Top]]>A[i])Top--;suc[i]=(ll)A[i]*(S[Top]-i)+suc[S[Top]];S[++Top]=i;ss[i]=ss[i+1]+suc[i];}Log[1]=0;Log[2]=1;for(i=3;i<=N;i++)Log[i]=Log[i>>1]+1;for(i=1;i<=N;i++)ST[i][0]=i;for(j=1;j<18;j++)for(i=1;i<=N;i++){ST[i][j]=A[ST[i][j-1]]<A[ST[i+(1<<j-1)][j-1]]?ST[i][j-1]:ST[i+(1<<j-1)][j-1];}for(i=1;i<=Q;i++){l=_R();r=_R();Min=GetMin(l,r);Ans=ss[l]-ss[Min]-suc[Min]*(Min-l);Ans+=sp[r]-sp[Min]-pre[Min]*(r-Min);Ans+=(ll)A[Min]*(ll)(r-Min+1)*(ll)(Min-l+1);printf("%lld\n",Ans);}
}