bzoj 4540: [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。

Solution

我们设 \(f[i][j]\) 表示区间 \([i,j]\) 的最小值,那么答案就是 \(\sum\sum f[i][j]\)

我们把 \(f[i][j]\) 画成一个矩形,例如:

7

5 4

3 3 3

3 3 2 2

那么如果我们枚举了一个右端点 \(j\),那么就相当于是求第 \(j\) 行的和

从这一行到下一行实际上就是先平移下来,然后再把新加进来的元素做一次区间覆盖

设 \(L[i]\) 为 \(i\) 作为最小值能够往左延伸到的最远的位置,那么就是对 \([L[i],i]\) 做一个区间覆盖,并且我们还要维护一个区间和,由于还枚举了右端点,所以还要维护历史信息

那么线段树分别维护 \(s,v,l\) 表示,历史的区间和的总和,当前的区间和,区间长度

并且维护四个标记 \(a,b,c,d\),表示标记生效后, \(v=v*a+b*l\),\(s=s+v*c+d*l\)

标记的合并有一些讨论,见代码

扫描线+线段树维护这个东西即可

#include<bits/stdc++.h>

#define ls (o<<1)

#define rs (o<<1|1)

using namespace std;

typedef long long ll;

const int N=1e5+10;

inline int gi(){

	register int str=0;register char ch=getchar();bool f=0;

	while(ch>'9' || ch<'0'){if(ch=='-')f=1;ch=getchar();}

	while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();

	return f?-str:str;

}

int n,a[N],Q,cnt=0,L[N],st[N],top=0;ll ans[N];

struct Qu{int x,l,r,k,id;}q[N*2];

inline bool comp(const Qu &i,const Qu &j){return i.x<j.x;}

struct tag{

	ll a,b,c,d;

	tag(){a=1;b=0;c=0;d=0;}

	tag(ll _a,ll _b,ll _c,ll _d){a=_a;b=_b;c=_c;d=_d;}

	tag operator +(tag &p){return tag(a*p.a,b*p.a+p.b,a*p.c+c,d+p.d+b*p.c);}

};

struct node{

	ll v,s,l;tag t;

	node(){v=s=l=0;t=tag();}

	node(ll _v,ll _s,ll _l,tag _t){v=_v;s=_s;l=_l;t=_t;}

	node operator +(const node &p){return node(v+p.v,s+p.s,l+p.l,tag());}

	inline void add(tag x){s+=v*x.c+l*x.d;v=x.a*v+x.b*l;t=t+x;}

}tr[N*4];

inline void build(int l,int r,int o){

	if(l==r){tr[o]=node();tr[o].l=1;return ;}

	int mid=(l+r)>>1;

	build(l,mid,ls);build(mid+1,r,rs);

	tr[o]=tr[ls]+tr[rs];

}

inline void pushdown(int o){

	tag t=tr[o].t;

	if(t.a==1 && !t.b && !t.c && !t.d)return ;

	tr[o].t=tag();tr[ls].add(t);tr[rs].add(t);

}

inline void Modify(int l,int r,int o,int sa,int se,tag t){

	if(sa<=l && r<=se){tr[o].add(t);return ;}

	pushdown(o);

	int mid=(l+r)>>1;

	if(se<=mid)Modify(l,mid,ls,sa,se,t);

	else if(sa>mid)Modify(mid+1,r,rs,sa,se,t);

	else Modify(l,mid,ls,sa,mid,t),Modify(mid+1,r,rs,mid+1,se,t);

	tr[o]=tr[ls]+tr[rs];

}

inline node qry(int l,int r,int o,int sa,int se){

	if(sa<=l && r<=se)return tr[o];

	pushdown(o);

	int mid=(l+r)>>1;node ret;

	if(se<=mid)ret=qry(l,mid,ls,sa,se);

	else if(sa>mid)ret=qry(mid+1,r,rs,sa,se);

	else ret=qry(l,mid,ls,sa,mid)+qry(mid+1,r,rs,mid+1,se);

	tr[o]=tr[ls]+tr[rs];

	return ret;

}

int main(){

	freopen("pp.in","r",stdin);

	freopen("pp.out","w",stdout);

	cin>>n>>Q;

	for(int i=1;i<=n;i++)a[i]=gi();

	for(int i=1;i<=n;i++){

      while(top && a[i]<a[st[top]])top--;

      L[i]=st[top]+1;st[++top]=i;

	}

	int x,y;

	for(int i=1;i<=Q;i++){

      x=gi();y=gi();

      q[++cnt]=(Qu){y,x,y,1,i};

	}

	sort(q+1,q+cnt+1,comp);

	build(1,n,1);

	for(int i=1,j=1;i<=n;i++){

      Modify(1,n,1,L[i],i,tag(0,a[i],0,0));tr[1].add(tag(1,0,1,0));

      while(j<=cnt && q[j].x<i)j++;

      for(;j<=cnt && q[j].x==i;j++)

			ans[q[j].id]+=qry(1,n,1,q[j].l,q[j].r).s;

	}

	for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);

	return 0;

}

巴特西

bzoj 4540: [Hnoi2016]序列

Description

Solution

最新文章

热门文章