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）是指序列：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。

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为左端点的区间最小值之和即可

代码见下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7 const int N=100100; 8 struct quest{
    int id,l,r;}q[N]; 9 int n,m,len;10 int minpos[N][18],bin[20],belong[N],stack[N];11 LL a[N],l_f[N],r_f[N],ans[N],minv[N][18];12 inline bool mt(const quest &a,const quest &b)13 {14     if(belong[a.l]==belong[b.l])return a.r
          
           a[i])top--;36         l_f[i]=l_f[stack[top]]+(i-stack[top])*a[i];37         stack[++top]=i;38     }39     for(i=n,top=0;i;i--)40     {41         while(top&&a[stack[top]]>=a[i])top--;42         if(top)r_f[i]=r_f[stack[top]]+(stack[top]-i)*a[i];43         else r_f[i]=(n-i+1)*a[i];44         stack[++top]=i;45     }46 }47 inline int query(int l,int r)48 {49     int k=0;while(bin[k]<=r-l+1)k++;50     k--;if(minv[l][k]
           
            q[i].r)61 mpos=query(l,r),tmp-=l_f[r]-l_f[mpos]+(LL)(mpos-l+1)*a[mpos],r--;62 while(l
            
             q[i].l)65 l--,mpos=query(l,r),tmp+=r_f[l]-r_f[mpos]+(LL)(r-mpos+1)*a[mpos];66 ans[q[i].id]=tmp;67 }68 for(int i=1;i<=m;i++)69 printf("%lld\n",ans[i]);70 }