首页 > 代码库 > bzoj4540: [Hnoi2016]序列

bzoj4540: [Hnoi2016]序列

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

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

预处理每个a[i]数作为最左的最小值向左右延伸到的位置L[i],R[i],则l=L[i]..i,r=i..R[i]的区间的最小值为a[i],且最后每个区间不重不漏

让区间端点l,r对应平面上的点(x=l,y=r),则询问转化为求一个矩形内的和,预处理的修改转化为矩形加上一个数

令与y轴平行的扫描线沿x轴负方向扫描,维护扫描线上每个y坐标上的答案关于x坐标的一次函数的系数,可以发现每个矩形加操作可以拆成四次区间加(进入/离开扫描线时对区间内的一次函数的两个系数的影响均为一个常数),而询问则为区间求和(区间内一次函数加起来再代入当前x求一次值),至此可以树状数组/线段树维护

时间复杂度O((n+q)logn+qlogq),树状数组实现时约有16n+4q次树状数组操作,常数较大

#include<cstdio>#include<algorithm>typedef long long i64;const int N=100007;int n,q,a[N],ss[N],sp=0,ls[N],rs[N];i64 ans[N];char buf[N*50],*ptr=buf-1;int _(){    int x=0,f=1,c=*++ptr;    while(c<48)c==-&&(f=-1),c=*++ptr;    while(c>47)x=x*10+c-48,c=*++ptr;    return x*f;}i64 ks[2][N],bs[2][N];void add(i64*f1,i64*f2,int w0,i64 x){    if(!w0)return;    for(int w=w0;w;w-=w&-w)f1[w]+=x;    x*=w0;    for(int w=w0;w<=n;w+=w&-w)f2[w]+=x;}i64 sum(i64*f1,i64*f2,int w0){    if(!w0)return 0;    i64 s=0;    for(int w=w0;w<=n;w+=w&-w)s+=f1[w];    s*=w0;    for(int w=w0-1;w;w-=w&-w)s+=f2[w];    return s;}struct Q{    int l,r,id;    void run(){        ans[id]=sum(ks[0],ks[1],r)*l+sum(bs[0],bs[1],r);    }}qs[N];bool operator<(Q a,Q b){return a.l>b.l;}struct ev{    int l,r1,r2;    i64 k,b;    void run(){        add(ks[0],ks[1],r2,k);        add(ks[0],ks[1],r1-1,-k);        add(bs[0],bs[1],r2,b);        add(bs[0],bs[1],r1-1,-b);    }}e[N*2];bool operator<(const ev&a,const ev&b){return a.l>b.l;}int ep=0;int main(){    fread(buf,1,sizeof(buf),stdin);    n=_();q=_();    for(int i=1;i<=n;++i)a[i]=_();    for(int i=1;i<=n;++i){        while(sp&&a[ss[sp]]>a[i])rs[ss[sp--]]=i-1;        ss[++sp]=i;    }    while(sp)rs[ss[sp--]]=n;    for(int i=n;i;--i){        while(sp&&a[ss[sp]]>=a[i])ls[ss[sp--]]=i+1;        ss[++sp]=i;    }    while(sp)ls[ss[sp--]]=1;    for(int i=1;i<=n;++i){        e[ep++]=(ev){i+1,i,rs[i],-a[i],i64(i+1)*a[i]};        e[ep++]=(ev){ls[i],i,rs[i],a[i],i64(-ls[i])*a[i]};    }    std::sort(e,e+ep);    for(int i=0;i<q;++i){        qs[i].l=_();        qs[i].r=_();        qs[i].id=i;    }    std::sort(qs,qs+q);    for(int i=0,p=0;i<q;++i){        while(p<ep&&e[p].l>=qs[i].l)e[p++].run();        qs[i].run();    }    for(int i=0;i<q;++i)printf("%lld\n",ans[i]);    return 0;}

 

bzoj4540: [Hnoi2016]序列