首页 > 代码库 > 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]序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。