给定长度为n的序列a1,…，an。现在有q个询问，每个询问给定两个数l和r,求序列[l,r]内的不同子序列的最小值之和。

链接

LOJ2051

BZOJ4540

题解

首先考虑使用莫队算法更新答案。当询问区间从[l,r]变为[l,r+1]时，多出了r-l+2个子序列，这些子序列的贡献需要分别计算。首先假设[l,r]中最小值的位置是w，则以[l,w]开头的子序列的贡献是

(w-l+1)a_w

剩下的[w+1,r+1]的贡献需要另外计算。

首先定义left数组，left[i]表示第i个元素左边第一个小于等于它的元素的位置。这一数组可以在线性时间内计算：维护一个单调栈，先将-1入栈，然后以此将序列的元素添加进去。每当添加一个元素的时候，把前面大于该元素的所有元素全部弹出，然后再把新元素入栈。该元素前面的元素在原序列的位置就是left[i]。正确性显然。类似的，可以定义并计算right数组。

接着计算剩余部分的贡献。再定义

f_{[l,r]}

表示[l,r]这段区间对答案的贡献。那么，剩下部分的贡献可以表示为

(r+1-left[r+1])*a_{r+1}+f_{[w+1,left[r+1]]}

而后一项可以递归算下去，直到区间左右两端相等。同时，可以使用前缀和提前算好这一部分。定义

F_i = \begin{cases}
(i-left[i])*a_i+f_{left[i]}&i != left[i] \
0&i==left[i]\ \end{cases}

所以，以上转移过程的增量可以写成

(w-l+1)a_w+F_{r+1}-F_{w}

对于左端区间延伸的情况同理。故可以利用RMQ求区间最小值从而在O(1)时间内完成转移。总的时间复杂度为

O(n\sqrt{n})

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,q,i,block,L,R;
LL ans;
int pos[N],l[N],r[N],lg[N],f[N][20];
LL a[N],z[N],ls[N],rs[N],Ans[N];

struct Data{
    LL l,r;
    int id;
}b[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1; c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline bool cmp(const Data x,const Data y){return (pos[x.l]==pos[y.l])?x.r<y.r:x.l<y.l;}

inline void Ready(){
    int i=0,j=0;
    z[++z[0]]=-1;
    for (i=1;i<=n;i++){
        while (z[z[0]]>0)
            if (a[i]<a[z[z[0]]])    z[0]--;
            else break;
        l[i]=(z[z[0]]==-1)?i:z[z[0]];   z[++z[0]]=i;
    }
    memset(z,0,sizeof(z));
    z[++z[0]]=-1;
    for (i=n;i;i--){
        while (z[z[0]]>0)
            if (a[i]<a[z[z[0]]])    z[0]--;
            else break;
        r[i]=(z[z[0]]==-1)?i:z[z[0]];   z[++z[0]]=i;
    }
    for (i=1;i<=n;i++){
        ls[i]=(LL)(i-l[i])*a[i];
        if (l[i]<i) ls[i]+=ls[l[i]];
    }
    for (i=n;i;i--){
        rs[i]=(LL)(r[i]-i)*a[i];
        if (r[i]>i) rs[i]+=rs[r[i]];
    }
    for (i=1;i<=N-10;i++)   lg[i]=(int)(log(i)/log(2));
    for (i=1;i<=n;i++)  f[i][0]=i;
    for (j=1;(1<<j)<=n;j++)
        for (i=1;i<=n-(1<<j)+1;i++)
            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];
}

inline int Get(int p,int q){
    if (p==q)   return p;
    int s=lg[q-p];
    return (a[f[p][s]]<a[f[q-(1<<s)+1][s]])?f[p][s]:f[q-(1<<s)+1][s];
}

inline void Update(int x,int flag,int p){
    int w=0;
    LL cnt=0;
    if (flag){
        w=Get(L,x);
        if (w==x){
            ans+=p*(LL)(x-L+1)*a[x];
            return;
        }
        cnt=(LL)(w-L+1)*a[w];
        cnt+=ls[x]-ls[w];
        ans+=cnt*p;
    }   else {
        w=Get(x,R);
        if (w==x){
            ans+=p*(LL)(R-x+1)*a[x];
            return;
        }
        cnt=(LL)(R-w+1)*a[w];
        cnt+=rs[x]-rs[w];
        ans+=cnt*p;
    }
}

inline void Solve(){
    ans=0;
    for (i=1;i<=q;i++){
        while (R<b[i].r)    Update(R+1,1,1),R++;
        while (R>b[i].r)    Update(R,1,-1),R--;
        while (L<b[i].l)    Update(L,0,-1),L++;
        while (L>b[i].l)    Update(L-1,0,1),L--;
        Ans[b[i].id]=ans;
    }
}

int main(){
    n=read();   q=read();
    for (i=1;i<=n;i++)  a[i]=read();
    block=int(sqrt(n)); L=1;    R=0;
    for (i=1;i<=n;i++)  pos[i]=(i-1)/block+1;
    for (i=1;i<=q;i++){
        b[i].l=read();  b[i].r=read();  b[i].id=i;
    }
    sort(b+1,b+1+q,cmp);
    Ready();    Solve();
    for (i=1;i<=q;i++)  printf("%lld\n",Ans[i]);
    return 0;
}