【NOIP2017提高A组集训10.21】Fantasy

题目

Y sera 陷入了沉睡，幻境中它梦到一个长度为N 的序列{Ai}。

对于这个序列的每一个子串，定义其幻境值为这个子串的和，现在Y sera 希望选择K 个不同的子串并使得这K 个子串的幻境值之和最大。

然而由于梦境中的种种限制，这些子串的长度必须在L 到R 之间。

你需要告诉她，最大的幻境值之和。

分析

题目要求求出最大的和，那显然就是找出最大的k个子串。

考虑怎么找出最大的k个子串。

我们求一次前缀和，扔进一个可持久化权值线段树上。

然后二分第k大的子串的值mid，枚举子串的开头，对于第i个开头，查询第i+L-1到i+R-1棵权值线段树上子串值大于等于mid的个数。

将大于等于mid的子串总个数与k比较进行二分。

最后用线段树将大于等于二分出来的值的子串的值加起来就是答案。

时间复杂度O(NlogN)。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

const int maxlongint=2147483647;

const int mo=1e9;

const int N=100005;

const int M=10000;

using namespace std;

struct tree

{

	int l,r,num;

	long long sum;

}tr[N*50];

int a[N],n,k,L,R,rt[N],tot;

long long ans;

int max(int x,int y)

{

	return x>y?x:y;

}

int min(int x,int y)

{

	return x<y?x:y;

}

void put(int v,int l,int r,int x)

{

	tr[v].num++;

	tr[v].sum+=1ll*x;

	if(l==r) return;

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

	if(x<=mid) tr[++tot]=tr[tr[v].l],tr[v].l=tot,put(tr[v].l,l,mid,x);

	else tr[++tot]=tr[tr[v].r],tr[v].r=tot,put(tr[v].r,mid+1,r,x);

}

long long find1(int v,int v1,int l,int r,long long x,int y,int t)

{

	if(v==0 || x>y) return 0;

	if(l==x && r==y)

	{

		if(!t) return tr[v].num-tr[v1].num;

		else return tr[v].sum-tr[v1].sum;

	}

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

	if(y<=mid) return find1(tr[v].l,tr[v1].l,l,mid,x,y,t);

	else

	if(x>mid) return find1(tr[v].r,tr[v1].r,mid+1,r,x,y,t);

	else return find1(tr[v].l,tr[v1].l,l,mid,x,mid,t)+find1(tr[v].r,tr[v1].r,mid+1,r,mid+1,y,t);

}

int main()

{

	scanf("%d%d%d%d",&n,&k,&L,&R);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1];

	a[0]=mo;

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

		a[i]+=mo,rt[i]=++tot,tr[rt[i]]=tr[rt[i-1]],put(rt[i],0,mo*2,a[i]);

	int l=0,r=mo*2;

	while(l+1<r)

	{

		int mid=(1ll*l+r)>>1,cnt=0;

		for(int i=1;i<=n && i+L-2<n;i++) cnt=cnt+find1(rt[min(i+R-1,n)],rt[i+L-2],0,mo*2,max(a[i-1]+mid-mo,0),mo*2,0);//-find(rt[i+L-2],0,mo*2,max(a[i-1]+mid-mo,0),mo*2,0);

		if(cnt>=k) l=mid;

		else r=mid;

	}

	long long cnt=0;

	ans=0;

	for(int i=1;i<=n && i+L-2<n;i++)

	{

		int wz=find1(rt[min(i+R-1,n)],rt[i+L-2],0,mo*2,max(a[i-1]+r-mo,0),mo*2,0);

		cnt=cnt+wz;

		ans=ans+find1(rt[min(i+R-1,n)],rt[i+L-2],0,mo*2,max(a[i-1]+r-mo,0),mo*2,1)-1ll*wz*a[i-1];

	}

	if(cnt>=k)

	{

		ans-=(cnt-1ll*k)*(r-mo);

		printf("%lld",ans);

		return 0;

	}

	ans=cnt=0;

	for(int i=1;i<=n && i+L-2<n;i++)

	{

		int wz=find1(rt[min(i+R-1,n)],rt[i+L-2],0,mo*2,max(a[i-1]+l-mo,0),mo*2,0);

		cnt=cnt+wz;

		ans=ans+find1(rt[min(i+R-1,n)],rt[i+L-2],0,mo*2,max(a[i-1]+l-mo,0),mo*2,1)-1ll*wz*a[i-1];

	}

	ans-=(cnt-1ll*k)*(l-mo);

	printf("%lld",ans);

}

巴特西

【NOIP2017提高A组集训10.21】Fantasy

题目

分析

最新文章

热门文章