[BZOJ4540][HNOI2016]序列 莫队

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

题解:

这道题我刚拿到手被打懵了……但其实这道题有明显的2个特征:

第一,这是区间统计类问题;第二,没要求在线

这样的话我们就考虑一些离线的区间统计算法,首先想到的大概都是莫队。

那么莫队可行吗?我们以从[l,r]转移到[l,r+1]为例,考虑每一次端点移动时带来的影响。如果这样可做,其他三种情况肯定是类似的。

在移动之后,新增了[l,r+1],[l+1,r+1],[l+2,r+1],......,[r+1,r+1]这一些区间。

我们考虑新区间最小的数,设其为a[x],那么,显然有:

从[l,r+1]到[x,r+1]这些区间的最小值都不会是a[r+1],而[x+1,r+1]到[r+1,r+1]这些区间的最小值不确定

因此当转移时,记录变量ans+=(x-l+1)*a[x]+卫龙

那么现在的问题是,卫龙是啥?怎么计算?

不难看出,卫龙指的就是从[x+1,r+1]到[r+1,r+1]这些区间的最小值之和,如果直接对它暴力计算显然不行,因此我们换一种思路。

设f[i]为以i为右端点的区间最小值之和,那么对于上面所说的r和x,由于a[x]是区间最小值,故对于

任何y<=x,区间[y,x],[y,r+1]的最小值肯定不会发生变化,而如果y>x,我们已经在f里加过了

那么显然 f[r+1]-f[x]就是我们要求的卫龙了因此得到转移的式子ans+=(x-l+1)*a[x]+f[r+1]-f[x]

而对f数组的计算可以递推处理,设a[x]为左数第一个小于a[i]的数,那么有f[i]=f[x]+(i-x)*a[i]

正确性很显然,在x以右的区间最小值一定是a[i],而由于x的性质,x及x左边的区间最小值在区间右端点右移后也不会变化

这样我们可以用一个单调栈,在O(n)的时间内计算f数组

这样,这道题就可以做了,只要再把区间左端点移动的情况考虑一下,再计算一个新的f1数组表示以i为左端点的区间最小值之和即可

代码见下:

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=;
struct quest{int id,l,r;}q[N];
int n,m,len;
int minpos[N][],bin[],belong[N],stack[N];
LL a[N],l_f[N],r_f[N],ans[N],minv[N][];
inline bool mt(const quest &a,const quest &b)
{
if(belong[a.l]==belong[b.l])return a.r<b.r;
return belong[a.l]<belong[b.l];
}
inline void intn()
{
scanf("%d%d",&n,&m);len=sqrt(n+0.5);
for(int i=;i<=n;i++)scanf("%lld",&a[i]),belong[i]=(i-)/len+;
for(int i=;i<=m;i++)q[i].id=i,scanf("%d%d",&q[i].l,&q[i].r);
sort(q+,q+m+,mt);
for(int i=;i<=n;i++)minv[i][]=a[i],minpos[i][]=i;
bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]<<;
for(int i=;bin[i]<=n;i++)
for(int j=;j+bin[i]-<=n;j++)
{
minv[j][i]=min(minv[j][i-],minv[j+bin[i-]][i-]);
if(minv[j][i]==minv[j][i-])minpos[j][i]=minpos[j][i-];
else minpos[j][i]=minpos[j+bin[i-]][i-];
}
int i,top;
for(i=,top=;i<=n;i++)
{
while(top&&a[stack[top]]>a[i])top--;
l_f[i]=l_f[stack[top]]+(i-stack[top])*a[i];
stack[++top]=i;
}
for(i=n,top=;i;i--)
{
while(top&&a[stack[top]]>=a[i])top--;
if(top)r_f[i]=r_f[stack[top]]+(stack[top]-i)*a[i];
else r_f[i]=(n-i+)*a[i];
stack[++top]=i;
}
}
inline int query(int l,int r)
{
int k=;while(bin[k]<=r-l+)k++;
k--;if(minv[l][k]<minv[r-bin[k]+][k])return minpos[l][k];
else return minpos[r-bin[k]+][k];
}
int main()
{
intn();int mpos,l=,r=;LL tmp=a[];
for(int i=;i<=m;i++)
{
while(r<q[i].r)
r++,mpos=query(l,r),tmp+=l_f[r]-l_f[mpos]+(LL)(mpos-l+)*a[mpos];
while(r>q[i].r)
mpos=query(l,r),tmp-=l_f[r]-l_f[mpos]+(LL)(mpos-l+)*a[mpos],r--;
while(l<q[i].l)
mpos=query(l,r),tmp-=r_f[l]-r_f[mpos]+(LL)(r-mpos+)*a[mpos],l++;
while(l>q[i].l)
l--,mpos=query(l,r),tmp+=r_f[l]-r_f[mpos]+(LL)(r-mpos+)*a[mpos];
ans[q[i].id]=tmp;
}
for(int i=;i<=m;i++)
printf("%lld\n",ans[i]);
}
上一篇:转-软件测试人员在工作中如何运用Linux


下一篇:总结工作中常见的linux命令