题解 P3246 【[HNOI2016]序列】

Kelin · 2018-04-01 00:55:16 · 题解

题意

给你一个序列,每次询问一个区间,求其所有子区间的最小值之和

题解

这里有两种方法,一种是离线的莫队,一种是在线算法

一.莫队

这题难就难在怎么由[l,r]推向[l,r+1]

考虑他们之间的增量就是新增的[l,r+1],[l+1,r+1],\ldots,[r+1,r+1]这r-l+2个区间的最小值之和

考虑求出[l,r+1]的最小值位置是p,那么所有左端点在[l,p]之间的区间答案都是a[p]

贡献就是a[p]\times(p-l+1),这一部分可以用rmq求最小值处理

考虑剩下的左端点在[p+1,r+1]的区间

设f[l][r]表示以r为右端点,左端点在[l,r]的区间的答案(要求的就是f[p+1][r+1])

记录一下pre_i表示从i向前第一个比i小的数的位置(这个可以用单调栈O(n)求出)

那么左端点在[pre_r,r]的区间最小值都是a[r]

那么就有f[l][r]=f[l][pre_r]+a_r\times(r-pre_r)

可以发现dp增量只和r自身有关,所以可以去掉l那一维

因为最终一定会存在一个点x,满足pre_x=p

那么f_{r+1}=a_{r+1}\times(r+1-pre_{r+1})+\ldots+a_x\times(x-p)+f_p

我们可以发现f_{r+1}-f_p就是原来要求的f[p+1][r+1]

这样我们就可以预处理出f,然后就可以O(1)完成转移了

删除的话我们就减去[l,r-1]\to[l,r]的增量就好了

至于在左边加,就对称处理就好了

复杂度O(n\log n+n\sqrt n)

(rmq的qry里R-(1<<t)+1的"+1”,忘记打了调了一个小时/一脸悲伤)

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,inf=2e9;
typedef int arr[N];
typedef long long ll;
struct Q{
    int l,r,x,id;
    inline bool operator<(const Q b)const{return x==b.x?x&1?r<b.r:r>b.r:x<b.x;}
}q[N];
int n,m,Sz,Top,Mi[17],f[N][17];arr a,pre,suf,S,Log;ll Now,fl[N],fr[N],ans[N];
inline int cmp(const int x,const int y){return a[x]<a[y]?x:y;}
inline int qry(int L,int R){int t=Log[R-L+1];return cmp(f[L][t],f[R-Mi[t]+1][t]);}
inline ll left(int L,int R){int p=qry(L-1,R);return (ll)a[p]*(R-p+1)+fl[L-1]-fl[p];}
inline ll right(int L,int R){int p=qry(L,R+1);return (ll)a[p]*(p-L+1)+fr[R+1]-fr[p];}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);sd(m);Sz=sqrt(n);a[n+1]=a[0]=inf;
    Mi[0]=1;fp(i,1,16)Mi[i]=Mi[i-1]<<1;
    fp(i,2,n)Log[i]=Log[i>>1]+1;
    fp(i,1,n)sd(a[i]),f[i][0]=i;
    fp(j,1,Log[n])fp(i,1,n-Mi[j-1]+1)
        f[i][j]=cmp(f[i][j-1],f[i+Mi[j-1]][j-1]);
    fp(i,1,n){
        while(Top&&a[S[Top]]>a[i])suf[S[Top--]]=i;
        pre[i]=S[Top];S[++Top]=i;
    }while(Top)pre[S[Top]]=S[Top-1],suf[S[Top--]]=n+1;
    fp(i,1,n)fr[i]=(ll)a[i]*(i-pre[i])+fr[pre[i]];
    fd(i,n,1)fl[i]=(ll)a[i]*(suf[i]-i)+fl[suf[i]];
    int x,y,L,R;
    fp(i,1,m)sd(x),sd(y),q[i]={x,y,x/Sz,i};
    sort(q+1,q+m+1);L=q[1].l,R=L-1;
    fp(i,1,m){
        x=q[i].l,y=q[i].r;
        while(L>x)Now+=left(L,R),L--;
        while(R<y)Now+=right(L,R),R++;
        while(L<x)Now-=left(L+1,R),++L;
        while(R>y)Now-=right(L,R-1),--R;
        ans[q[i].id]=Now;
    }
    fp(i,1,m)we(ans[i]);
return Ot(),0;
}

二.在线算法

我们假设区间[l,r]的最小值的位置是p

那么对于左端点在[l,p],右端点在[p,r]的区间最小值都是a[p]

这一部分的贡献是a[p]\times(p-l+1)\times(r-p+1)

我们还没有统计[l,p-1]和[p+1,r]的答案

在莫队算法中我们已经知道

因为最终一定会存在一个点x,满足pre_x=p

那么f_{r+1}=a_{r+1}\times(r+1-pre_{r+1})+\ldots+a_x\times(x-p)+f_p

我们可以发现f_{r+1}-f_p就是原来要求的f[p+1][r+1]

然而这个是以r+1为右端点,左端点在(p,r+1]的答案

在这里我们就要考虑左端点在(p,x],右端点在[x,r]的全部答案

对于点r,所有以r为右端点,左端点在(p,r]的区间答案是f_r-f_p

对于点r-1,所有以r-1为右端点,左端点在(p,r-1]的区间答案是f_{r-1}-f_p

\ldots

对于点p+1,所有以p+1为右端点,左端点在(p,p+1]的区间答案是f_{p+1}-f_p

设g_i=\sum_{j=1}^if_j,通过观察发现,这一部分的答案就是g_r-g_p-f_p\times(r-p)

同样的,p左边的情况也是类似

复杂度O(n\log n)

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,inf=2e9;
typedef int arr[N];
typedef long long ll;
int n,m,Top,Mi[17],f[N][17];arr a,pre,suf,S,Log;ll fl[N],fr[N],gl[N],gr[N];
inline int cmp(const int x,const int y){return a[x]<a[y]?x:y;}
inline int qry(int L,int R){int t=Log[R-L+1];return cmp(f[L][t],f[R-Mi[t]+1][t]);}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);sd(m);a[n+1]=a[0]=inf;
    Mi[0]=1;fp(i,1,16)Mi[i]=Mi[i-1]<<1;
    fp(i,2,n)Log[i]=Log[i>>1]+1;
    fp(i,1,n)sd(a[i]),f[i][0]=i;
    fp(j,1,Log[n])fp(i,1,n-Mi[j-1]+1)
        f[i][j]=cmp(f[i][j-1],f[i+Mi[j-1]][j-1]);
    fp(i,1,n){
        while(Top&&a[S[Top]]>a[i])suf[S[Top--]]=i;
        pre[i]=S[Top];S[++Top]=i;
    }while(Top)pre[S[Top]]=S[Top-1],suf[S[Top--]]=n+1;
    fp(i,1,n)fr[i]=(ll)a[i]*(i-pre[i])+fr[pre[i]],gr[i]=gr[i-1]+fr[i];
    fd(i,n,1)fl[i]=(ll)a[i]*(suf[i]-i)+fl[suf[i]],gl[i]=gl[i+1]+fl[i];
    int l,r,p;
    while(m--){
        sd(l),sd(r),p=qry(l,r);
        we((ll)(p-l+1)*(r-p+1)*a[p]+
            gr[r]-gr[p]-fr[p]*(r-p)+
            gl[l]-gl[p]-fl[p]*(p-l));
    }
return Ot(),0;
}

到这里我们可以发现,这个算法的复杂度瓶颈就在于rmq了

朴素倍增rmq预处理速度太慢

我们可以O(n)建立笛卡尔树来进行rmq,设单次询问复杂度=k\lt\log n

所以这题可以做到O(n+km)

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,inf=2e9;
typedef int arr[N];
typedef long long ll;
int n,m,rt;arr a,lc,rc,pre,suf,S,Log;ll fl[N],fr[N],gl[N],gr[N];
inline int cmp(const int x,const int y){return a[x]<a[y]?x:y;}
inline int qry(int L,int R){for(int x=rt;;x=(x>R?lc:rc)[x])if(L<=x&&x<=R)return x;}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);sd(m);a[n+1]=a[0]=inf;int*Top=S;
    fp(i,1,n){
        sd(a[i]);
        while(Top!=S&&a[*Top]>=a[i])lc[i]=*Top--;
        rc[*Top]=i;*++Top=i;
    }rt=S[1];int top=0;
    fp(i,1,n){
        while(top&&a[S[top]]>a[i])suf[S[top--]]=i;
        pre[i]=S[top];S[++top]=i;
    }while(top)pre[S[top]]=S[top-1],suf[S[top--]]=n+1;
    fp(i,1,n)fr[i]=(ll)a[i]*(i-pre[i])+fr[pre[i]],gr[i]=gr[i-1]+fr[i];
    fd(i,n,1)fl[i]=(ll)a[i]*(suf[i]-i)+fl[suf[i]],gl[i]=gl[i+1]+fl[i];
    int l,r,p;
    while(m--){
        sd(l),sd(r),p=qry(l,r);
        we((ll)(p-l+1)*(r-p+1)*a[p]+
            gr[r]-gr[p]-fr[p]*(r-p)+
            gl[l]-gl[p]-fl[p]*(p-l));
    }
return Ot(),0;
}

从O(n\log n+n\sqrt n)\to O(n\log n)\to O(n+km)可见这题多么~~毒瘤一般的~~优秀

貌似可以出一道加强版(强制在线,数据范围n,m\le 2\times 10^6)

upd:2018.4.5

唔~笛卡尔树被hack了

看来这题还是只能做到O(n\log n)

感谢@兔子接烧饼指出我程序的错误