9
19
2016
5

codeforces 720F

假如我死在了这道题上，给我烧点纸钱。

英文题解细节实现没有提及，但细节实现非常之麻烦。这里主要是翻译解释并加了细节的如何实现。

记p=max(k-n,0)+x，q=k-p,x是一个随便选的0到n-1的数。

选的区间由两部分构成，第一部分是为了使总和尽可能大的p个区间，显然要选前p大的区间，第二部分是为了覆盖第一部分没有覆盖的位置而选的q个区间。非常显然q≤n所以x取值范围是1到n。

我们维护出第一部分没有覆盖的点{i1,i2,...is}，考虑怎么选才能让第二部分的贡献尽可能大。

易证第二部分选的区间没有重叠部分且一定覆盖某个i，否则答案一定不优。

记q个区间是[l1,r1],[l2,r2]...[lq,rq]，很显然sum(r)取得越大越好，sum(l)取得越小越好。易证rj和lj+1一定会落在某个区间[ij,ij+1]内。所以sum(l1)的最小值就是min(sum(j)(j<i1)),sum(rq)同理，对于中间的rj和lj+1，易得它们的最大贡献是-区间[ij+1,ij+1]内的最小子序列和。所以第二部分对答案的最大贡献就是min(sum(j)(j<i1))+max(sum(j)(j>=iq))-前(q-1)小的区间[ij+1,ij+1]内的最小子序列和。

然后考虑第一部分的贡献，可以用树状数组求>=mid的子序列数量，所以我们可以二分第p大的子序列个数，可以用类似的方法求出他们的和以及对于某个r来说最小的合法的l。

然后可以用堆维护第k大的子序列，维护对于以某个位置结尾的子序列来说，比当前值小的子序列中最大的子序列。每次从第k大的序列转移到第k+1大的序列就从堆顶拖一个子序列出来，然后对于它的结尾找下一个子序列到堆里。

整理一下。我们先做x=0的情况，用树状数组求出前p大的区间和的和记为ans1,然后在线段树上覆盖这些区间，从而找出没有被覆盖的点。第一二项直接查，第三项用线段树维护出区间最小子序列和，然后用一个支持删除，插入，求前k小项的和的数据结构（我选择splay）维护前(q-1)小的区间[ij+1,ij+1]内的最小子序列和。得出第二部分的贡献ans2。总贡献就是ans1+ans2。

然后将x从1枚举到n-1，每次x++的时候，找出新加入的区间，ans1加上它的值，暴力找出所有它覆盖的点，维护那个数据结构从而维护ans2，就可以在均摊O(nlog)时间内得出min(ans1+ans2)。

明天再写。

UPDATE 9.23：一位红名大爷证明了子序列值相等的话无论按照什么顺序都一定可以得出最优解。并且之前的写法是有问题的。不能直接维护那个堆，算了写完之后看代码再说吧。

UPDATE9.27：终于胖出来了，弄了半天WA27的原因是checksum里少加了一个else导致某个子区间被加到堆里不止一次然后就狗带了。智商低出新高度

PS:http://pan.baidu.com/s/1o8TMZxS RCC2016的数据和std，省的后来的人去胖俄文了

 

#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#define inf 8333583335000000000ll
using namespace std;
int n,lcnt;
long long m,p,q;
int a[100005],lsum[100005];
long long sum[100005],rmax[100005],lmin[100005],ls[100005];
long long ans1,ans2,ans;
set<int>unu;
inline long long Min(long long x,long long y){return x<y?x:y;}
inline long long Max(long long x,long long y){return x>y?x:y;}
inline int lowbit(int k){return k&-k;}
struct ta{
	long long t[100005];
	void add(int k,long long x){for(;k<=lcnt;k+=lowbit(k))t[k]+=x;}
	inline long long query(int k){long long ans=0;for(;k;k-=lowbit(k))ans+=t[k];return ans;}
}tsum,tnum;
struct ta2{
	int t[100005];
	void build(){for(int i=1;i<=lcnt;i++)t[i]=n+1;}
	void add(int k,int x){for(;k<=lcnt;k+=lowbit(k))t[k]=Min(t[k],x);}
	inline int query(int k){int ans=n+1;for(;k;k-=lowbit(k))ans=Min(ans,t[k]);return ans;}
}tmin;
struct subs{
	int l,r;long long w;
	bool operator >(const subs k)const{
		if(w!=k.w)return w>k.w;
		else if(r!=k.r)return r>k.r;
		else return l>k.l;
	}
	bool operator <(const subs k)const{
		if(w!=k.w)return w<k.w;
		else if(r!=k.r)return r<k.r;
		else return l<k.l;
	}
	bool operator ==(const subs k)const{return (k.l==l)&&(k.r==r)&&(k.w==w);}
	bool operator !=(const subs k)const{return (k.l!=l)||(k.r!=r)||(k.w!=w);}	
};
struct heap{
	subs h[100005];
	int top;
	void pushdown(int k){
		while((k<<1)<=top){
			int v=k<<1;
			if(v+1<=top)if(h[v|1]>h[v])v++;
			if(h[v]>h[k])swap(h[v],h[k]);
			else break;
			k=v;
		}
	}
	void pushup(int k){
		while(k>1){
			int v=k>>1;
			if(h[v]<h[k])swap(h[v],h[k]);
			else break;
			k=v;
		}
	}
	void push(subs k){
		h[++top]=k;
		pushup(top);
	}
	void pop(){
		h[1]=h[top--];
		pushdown(1);
	}
}subsq;
void del(int k);
#define lson index<<1
#define rson index<<1|1
#define mid ((l+r)>>1)
struct sg1{
	bool b[400005];
	void cover(int L,int R,int l,int r,int index){
		if(L>R)return;
		if(b[index])return;
		if(l==r){del(l);b[index]=true;return;}
		if(L<=mid)cover(L,R,l,mid,lson);
		if(R>mid)cover(L,R,mid+1,r,rson);
		b[index]=b[lson]&&b[rson];
	}
}s1;
struct t{
	long long max[100005][17],min[100005][17];
	int lo[100005];
	void build(int l,int r,int index){
		lo[1]=0;
		for(int i=2;i<=n;i++)if((1<<(lo[i-1]+1))==i)lo[i]=lo[i-1]+1;
		else lo[i]=lo[i-1];
		for(int i=0;i<=n;i++)max[i][0]=min[i][0]=sum[i];
		for(int i=1;i<=lo[n];i++)
			for(int j=0;j+(1<<i)-1<=n;j++)max[j][i]=Max(max[j][i-1],max[j+(1<<(i-1))][i-1]),min[j][i]=Min(min[j][i-1],min[j+(1<<(i-1))][i-1]);
	}
	long long query(int l,int r){
		int tmp=lo[r-l+1];
		return Max(max[l][tmp],max[r-(1<<tmp)+1][tmp])-Min(min[l][tmp],min[r-(1<<tmp)+1][tmp]);
	}
}s2;
#undef lson
#undef rson
struct node3{
	int l,r,s;
};
struct sg3{
	node3 t[4000005];
	int root[100005],cnt;
	void ins(int &rt,int l,int r,int k){
		if(rt==0)rt=++cnt;
		t[rt].s++;
		if(l==r)return;
		if(k<=mid)ins(t[rt].l,l,mid,k);
		else ins(t[rt].r,mid+1,r,k);
	}
	void build(){for(int i=0;i<=n;i++)ins(root[lsum[i]],0,n,i);}
	inline int qsum(int rt,int l,int r,int k){
		if(rt==0)return 0;
		if(r==k)return t[rt].s;
		if(k<=mid)return qsum(t[rt].l,l,mid,k);
		else return t[t[rt].l].s+qsum(t[rt].r,mid+1,r,k);
	}
	inline int query(int rt,int l,int r,int k){
		if(l==r)return r;
		if(k<=t[t[rt].l].s)return query(t[rt].l,l,mid,k);
		else return query(t[rt].r,mid+1,r,k-t[t[rt].l].s);
	}
}s3;
struct sg4{
	node3 t[4000005];
	int cnt,root[100005];
	void ins(int &rt,int Rt,int l,int r,int k){
		rt=++cnt;
		if(l==r)return;
		if(k<=mid){
			t[rt].r=t[Rt].r;
			ins(t[rt].l,t[Rt].l,l,mid,k);
		}else{
			t[rt].l=t[Rt].l;
			ins(t[rt].r,t[Rt].r,mid+1,r,k);
		}
	}
	void build(){ins(root[0],0,1,lcnt,lsum[0]);for(int i=1;i<=n;i++)ins(root[i],root[i-1],1,lcnt,lsum[i]);}
	inline int query(int rt,int l,int r,int k){
		if((k>r)||(rt==0))return 0;
		if(l==r)return l;
		if(k>mid)return query(t[rt].r,mid+1,r,k);
		else{
			int tmp=query(t[rt].l,l,mid,k);
			if(tmp)return tmp;
			else return query(t[rt].r,mid+1,r,k);
		}
	}
}s4;
struct splaynode{
	int l,r,size,fa;
	subs s;
	long long sum;
};
struct Splay{
	splaynode t[100005];
	int root,top,cnt,stack[100005];
	inline int newnode(){return stack[top--];}
	void pushup(int rt){
		t[rt].size=t[t[rt].l].size+t[t[rt].r].size+1;
		t[rt].sum=t[t[rt].l].sum+t[t[rt].r].sum+t[rt].s.w;
	}
	void rorate(int k,int i){
	    int tmp=t[k].fa;
	    t[k].fa=t[tmp].fa;
	    if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
	    else t[t[tmp].fa].r=k;
	    t[tmp].fa=k;
	    if(i==0){
		    if(t[k].l>0)t[t[k].l].fa=tmp;
		    t[tmp].r=t[k].l;
		    t[k].l=tmp;
		}else{
		    if(t[k].r>0)t[t[k].r].fa=tmp;
		    t[tmp].l=t[k].r;
		    t[k].r=tmp;
   		}
		pushup(tmp);pushup(k);
	}
	void splay(int k,int g){
		while(t[k].fa!=g){
			int tmp=t[k].fa;
			if(t[tmp].fa==g)if(t[tmp].r==k)rorate(k,0);
			else rorate(k,1);
			else{
				int Tmp=t[tmp].fa;
				if(t[Tmp].l==tmp){
				    if(t[tmp].l==k)rorate(tmp,1);
				    else rorate(k,0);
				    rorate(k,1);
				}else{
				    if(t[tmp].r==k)rorate(tmp,0);
					else rorate(k,1);
					rorate(k,0);
				}
			}
		}
		if(g==0)root=k;
	}
	void build(int l,int r,int &rt){
		rt=++cnt;
		t[rt].s=(subs){mid+1,mid,0};
		if(mid>l){
			build(l,mid-1,t[rt].l);
			t[t[rt].l].fa=rt;
		}
		if(r>mid){
			build(mid+1,r,t[rt].r);
			t[t[rt].r].fa=rt;
		}
		pushup(rt);
	}
	inline long long query(int k){
		if(k>t[root].size)return -inf;
		if(k==t[root].size)return t[root].sum;
		int p=root;
		while(t[t[p].r].size!=k){
			if(k<t[t[p].r].size)p=t[p].r;
			else k-=t[t[p].r].size+1,p=t[p].l;
		}
		splay(p,0);
		return t[t[p].r].sum;
	}
	void ins(subs k){
		if(root==0){
			root=newnode();
			t[root].l=t[root].r=t[root].fa=0;t[root].s=k;pushup(root);
			return;
		}
		int p=root,v;
		while(true){
			if(k<t[p].s)
				if(t[p].l)p=t[p].l;
				else{t[p].l=v=newnode();break;}
			else
				if(t[p].r)p=t[p].r;
				else{t[p].r=v=newnode();break;}
		}
		t[v].fa=p;t[v].l=t[v].r=0;t[v].s=k;pushup(v);splay(v,0);
	}
	void del(subs k){
		if(t[root].size==1){root=0;return;}
		int p=root;
		while(t[p].s!=k){
			if(k<t[p].s)p=t[p].l;
			else p=t[p].r;
		}
		splay(p,0);
		int tmp=t[p].l;
		if(tmp==0){
			t[t[p].r].fa=0;
			root=t[p].r;
			stack[++top]=p;
			return;
		}
		while(t[tmp].r)tmp=t[tmp].r;
		splay(tmp,root);
		t[tmp].fa=0;root=tmp;
		if(t[p].r)t[t[p].r].fa=tmp,t[tmp].r=t[p].r;
		pushup(tmp);stack[++top]=p;
	}
}s;
inline long long read(){
	long long ret=0,p=1;char c=getchar();
	while((c<'0')||(c>'9')){if(c=='-')p=-1;c=getchar();}
	while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ret*p;
}
inline int find(long long k){
	int l=0,r=lcnt+1;
	while(r-l>1){
		if(ls[mid]>k)r=mid;
		else l=mid;
	}
	return l;
}
inline long long checknum(long long std){
	long long ans=0;
	for(int i=0;i<=n;i++){
		ans+=tnum.query(find(sum[i]-std));
		tnum.add(lsum[i],1);
	}
	for(int i=0;i<=n;i++)tnum.add(lsum[i],-1);
	return ans;
}
void del(int k){
	set<int>::iterator p=unu.find(k),st=unu.begin(),ed=unu.end();
	ed--;
	if(p!=st){
		set<int>::iterator pre=p;pre--;
		s.del((subs){(*pre)+1,k-1,s2.query((*pre),k-1)});
	}
	if(p!=ed){
		set<int>::iterator nex=p;nex++;
		s.del((subs){k+1,(*nex)-1,s2.query(k,(*nex)-1)});
	}
	if((p!=st)&&(p!=ed)){
		set<int>::iterator pre=p,nex=p;pre--;nex++;
		s.ins((subs){(*pre)+1,(*nex)-1,s2.query((*pre),(*nex)-1)});	
	}
	unu.erase(k);
}
inline subs Next(subs now){
	int l=now.l,r=now.r,L,R=r;
	int tmp=s3.qsum(s3.root[lsum[l]],0,n,l);
	if(tmp==1){
		int S=s4.query(s4.root[r-1],1,lcnt,lsum[l]+1);
		if(S==0)return (subs){0,R,-inf};
		int Sum=s3.qsum(s3.root[S],0,n,r-1);
		L=s3.query(s3.root[S],0,n,Sum);
	}else L=s3.query(s3.root[lsum[l]],0,n,tmp-1);
	return (subs){L,R,sum[R]-sum[L]};
}
inline long long checksum(long long std,long long rest){
	long long ans=0;tmin.build();
	for(int i=0;i<=n;i++){
		int t=find(sum[i]-std);
		rest-=tnum.query(t);
		ans+=tnum.query(t)*sum[i];
		ans+=tsum.query(t);
		s1.cover(tmin.query(t)+1,i,1,n,1);
		tnum.add(lsum[i],1);
		tsum.add(lsum[i],-sum[i]);
		tmin.add(lsum[i],i);
	}
	for(int i=0;i<=n;i++)tnum.add(lsum[i],-1);
	std--;
	ans+=rest*std;
	tnum.add(lsum[0],1);
	for(int i=1;i<=n;i++){
		int Tmp=find(sum[i]-std);
		if(ls[Tmp]!=sum[i]-std){
			Tmp++;tnum.add(lsum[i],1);
			int p=s4.query(s4.root[i-1],1,lcnt,Tmp);
			if(p==0)continue;
			int L=s3.query(s3.root[p],0,n,s3.qsum(s3.root[p],0,n,i-1));
			subsq.push((subs){L,i,sum[i]-sum[L]});
		}else{
			int tmp=tnum.query(Tmp)-tnum.query(Tmp-1);
			tnum.add(lsum[i],1);
			if(tmp==0){
				Tmp++;
				int p=s4.query(s4.root[i-1],1,lcnt,Tmp);
				if(p==0)continue;
				int L=s3.query(s3.root[p],0,n,s3.qsum(s3.root[p],0,n,i-1));
				subsq.push((subs){L,i,sum[i]-sum[L]});		
			}else if(tmp<=rest){
				int L=s3.query(s3.root[Tmp],0,n,1);	
				s1.cover(L+1,i,1,n,1);rest-=tmp;
				Tmp++;
				int p=s4.query(s4.root[i-1],1,lcnt,Tmp);
				if(p==0)continue;
				L=s3.query(s3.root[p],0,n,s3.qsum(s3.root[p],0,n,i-1));
				subsq.push((subs){L,i,sum[i]-sum[L]});
			}else{
				int L;
				if(rest){
					L=s3.query(s3.root[Tmp],0,n,tmp-rest+1);
					s1.cover(L+1,i,1,n,1);
				}
				L=s3.query(s3.root[Tmp],0,n,tmp-rest);
				subsq.push((subs){L,i,sum[i]-sum[L]});rest=0;
			}
		}
	}
	return ans;
}
void upans2(){
	if(unu.empty()){ans2=-inf;return;}
	ans2=s.query(q-1);
	if(ans2==-inf)return;
	set<int>::iterator p=unu.begin();
	ans2-=lmin[(*p)-1];
	p=unu.end();p--;
	ans2+=rmax[(*p)];
}
void work(){
	for(int i=1;i<=n;i++)unu.insert(i);
	long long l=ls[1]-ls[lcnt]-5,r=ls[lcnt]-ls[1]+5;
	while(r-l>1){
		if(checknum(mid)>=p)l=mid;
		else r=mid;
	}
	ans1=checksum(r,p);
	upans2();
	if(ans2>-inf)ans=ans1+ans2;
	else ans=-inf;
}
void pre(){
	n=read();m=read();
	for(int i=1;i<=n;i++){a[i]=read();ls[i]=sum[i]=sum[i-1]+a[i];}
	ls[n+1]=0;
	sort(ls+1,ls+2+n);
	ls[0]=-inf;
	for(int i=1;i<=n+1;i++)if(ls[i]!=ls[i-1])ls[++lcnt]=ls[i];
	for(int i=0;i<=n;i++)lsum[i]=find(sum[i]);
	lmin[0]=sum[0];
	for(int i=1;i<=n;i++)lmin[i]=Min(lmin[i-1],sum[i]);
	rmax[n]=sum[n];
	for(int i=n-1;i>=0;i--)rmax[i]=Max(rmax[i+1],sum[i]);
	s2.build(1,n-1,1);s3.build();s4.build();s.build(1,n-1,s.root);
	if(m>n)p=m-n,q=n;
	else p=0,q=m;
	work();
}
void doit(){
	q--;p++;
	for(;q;q--,p++){
		subs tmp=subsq.h[1],Tmp=Next(tmp);
		if(Tmp.w>-inf)subsq.h[1]=Next(tmp),subsq.pushdown(1);
		else subsq.pop();
		s1.cover(tmp.l+1,tmp.r,1,n,1);
		ans1+=tmp.w;upans2();
		if(ans2>-inf)ans=Max(ans,ans1+ans2);
	}
	ans1+=subsq.h[1].w;
	s1.cover(subsq.h[1].l+1,subsq.h[1].r,1,n,1);
	if(s1.b[1])ans=ans1;
	printf("%I64d",ans);
}
int main(){
	pre();
	doit();
}
Category: codeforces | Tags: 堆 树状数组 线段树 codeforces Splay | Read Count: 2641
Small_feed 评论 (5)
1
[回复]
Avatar_small
qiancl 说:
2016年9月20日 09:17

%%%%%%%%%%%%%%%%%%%%%%%%%%%

2
[回复]
Avatar_small
WasteRice 说:
2016年9月23日 09:45

If some pair of subsegments have same sum, it doesn't matter, which of them you will take in "k - n" (k > n) set. Let's see, why:
Let's sort all subsegment by decreasing of their sum (we don't care now about subsegments with equal sum). Suppose, we didn't take first k - n segments, and x (x ≤ k - n) is 1-based index of first subsegment which is not in optimal answer. Obviously, there are k - x + 1 segments in answer with indexes bigger than x. We can see that k - x + 1 ≥ k - (k - n) + 1 = n + 1. We can always choose one subsegment from  ≥ n + 1 segments so that other  ≥ n segments cover whole array (suppose we can't: every segment covers some index in array that is not covered by any of other segments, but we have n + 1 segments and only n values in array). Let's delete this segment from our answer, and add segment with index x to answer. We didn't lose property that our set of segments cover whole array, and we didn't decrease sum of our segments: segment with index x had greater or equal sum than segment that we deleted from our set.
So, if there is an optimal answer, we showed that there is an optimal answer with any k - n subsegments with maximal sum, without worrying about subsegments with equal sum.

3
[回复]
Avatar_small
WasteRice 说:
2016年9月23日 09:46

You can do that faster than in O(n2log) if you, for example, sort segments by tuple <sum[l..r], r, l>. Suppose there are x (x < k) segments with sum  > y for some y, and there are  > k segments with sum  ≥ y. Indeed, there can be a lot (about O(n2)) subsegments with sum equal to y, so it is not easy to enumerate n segments that we need. We need just to skip first k - n - x segments with sum y, and then you can take segments with sum y one by one, because we will do that only n times.
In order to skip first segments we can use some data structure that can add new integer into structure and answer 2 types of questions: how many integers less than given are there in the structure, and what is i-th integer in structure. It can be done by fenwick tree (built on sorted prefix sums), or by advanced C++ STL data structures, like this.
When we have such data structure, when we fixed r bound of current subsegment, we need to ask how many integers equal to s[r] - y are there in our structure (because s[r] - s[l - 1] should be equal to y). If we can add them all to "k-n" set, just skip all segments with this r. Otherwise, you need to skip first k - n - currentSzeOfKnSet, and enumerate next few segments. Here you will need to know i-th integer in the structure.

4
[回复]
Avatar_small
qiancl 说:
2016年9月27日 12:31

楼上的就是那个红名大爷吗？

5
[回复]
Avatar_small
Tripura Board Questi 说:
2022年8月19日 14:47

Tripura Board Model Paper 2023 Class 1 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Tripura Board Question Paper Class 1 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com