NOI2010.Day1.T2.超级钢琴

题目大意：

在n个数字中找出k个不相同的长度在l-r之间的连续子序列，使得权值和最大（n<=500000,k<=500000）

昨天膜拜了一下10年的年鉴

这道题合法的子序列是非常多的，如果朴素显然是无法做出这道题

有一个非常美妙的想法，对于给定的起点，起点的权值已知了，子序列的个数是确定的

那么记录一下前缀和s[i]，对于给定的起点，实际上就是询问起点所代表的那一段区间的最大权值，这个就是RMQ问题，ST算法可以在O(nlogn)-O(1)的时间完成

那么对于每个点i，有一个pos[i]指向i所对应的区间里s[j]的最大值

用堆来维护一个五元组(st,idx,l,r,v)，st代表起点，idx代表起点对应的区间里最大值的下标，l,r代表对应的区间，v代表这个子序列的值

那么我们每次从堆中取出这样一个五元组以后，要将区间分裂，因为i-j这个区间不能取了，所以要将(st,idx,l,r,v)分裂为(st,idx‘,l,idx-1,v),(st,idx’‘,idx+1,r,v)两个区间

由于最多取k个，堆中最多有n+k个元素，时间复杂度为O((n+k)log(n+k))

具体实现看代码

还有一种方法不分裂区间，而是转而记录应该取这个区间里第k大的元素，这需要用到划分树or归并树这一数据结构，由于多年不写已经忘记……

so，这道题可以作为划分树or归并树的练习题，到时候再写一次

//Lib
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
//Macro
#define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i)
#define rrep(i,a,b) for(int i=a,tt=b;i>=tt;--i)
#define erep(i,e,x) for(int i=x;i;i=e[i].next)
#define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define read() (strtol(ipos,&ipos,10))
#define sqr(x) ((x)*(x))
#define pb push_back
#define PS system("pause");
typedef long long ll;
typedef pair<int,int> pii;
const int oo=~0U>>1;
const double inf=1e20;
const double eps=1e-6;
string name="",in=".in",out=".out";
//Var
struct T
{
	int st,idx,l,r,v;
	T(){}
	T(int s1,int i1,int l1,int r1,int v1):st(s1),idx(i1),l(l1),r(r1),v(v1){}
	bool operator <(const T &o)const{return v<o.v;}
};
priority_queue<T> q;
int n,k,L,R;
long long ans;
int f[20][500008],g[20][500008];
int s[500008],c[500008];
void Init();
void Work();
pii Query(int l,int r);
void ST();
int main()
{
//	freopen((name+in).c_str(),"r",stdin);
//	freopen((name+out).c_str(),"w",stdout);
	Init();
	Work();
	return 0;
}
void Init()
{
	scanf("%d%d%d%d",&n,&k,&L,&R);
	rep(i,1,n)scanf("%d",c+i),s[i]=s[i-1]+c[i];
}
void Work()
{
	ST(); pii t;T x;
	rep(i,1,n)
	{
		if(i-1+L>n)break;
		t=Query(i-1+L,i-1+R<=n?i-1+R:n);
		q.push(T(i,t.first,i-1+L,i-1+R<=n?i-1+R:n,t.second-s[i-1]));
	}
	rep(i,1,k)
	{
		x=q.top();q.pop();
		ans+=x.v;
		if(x.idx-1>=x.l)
		{
			t=Query(x.l,x.idx-1);
			q.push(T(x.st,t.first,x.l,x.idx-1,t.second-s[x.st-1]));
		}
		if(x.idx+1<=x.r)
		{
			t=Query(x.idx+1,x.r);
			q.push(T(x.st,t.first,x.idx+1,x.r,t.second-s[x.st-1]));
		}
	}
	cout<<ans<<endl;
}
void ST()
{
	rep(i,1,n)f[0][i]=s[i],g[0][i]=i;
	int t=(int)(log((double)n)/log(2.0));
	rep(i,1,t)
		rep(j,1,n-(1<<i)+1)
			if(f[i-1][j]>f[i-1][j+(1<<i-1)])
				f[i][j]=f[i-1][j],g[i][j]=g[i-1][j];
			else f[i][j]=f[i-1][j+(1<<i-1)],g[i][j]=g[i-1][j+(1<<i-1)];
}
pii Query(int l,int r)
{
	int t=(int)(log((double)r-l+1)/log(2.0));
	if(f[t][l]>f[t][r-(1<<t)+1])return pii(g[t][l],f[t][l]);
	else return pii(g[t][r-(1<<t)+1],f[t][r-(1<<t)+1]);
}

划分树版本：

//Lib
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
//Macro
#define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i)
#define rrep(i,a,b) for(int i=a,tt=b;i>=tt;--i)
#define erep(i,e,x) for(int i=x;i;i=e[i].next)
#define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define read() (strtol(ipos,&ipos,10))
#define sqr(x) ((x)*(x))
#define pb push_back
#define PS system("pause");
typedef long long ll;
typedef pair<int,int> pii;
const int oo=~0U>>1;
const double inf=1e20;
const double eps=1e-6;
string name="piano",in=".in",out=".out";
//Var
priority_queue<pii> q;
int n,k,L,R;
long long ans;
int d[21][500008],s[21][500008];
int sum[500008],c[500008],same[500008];
int kth[500008],sorted[500008];
void Init();
void Work();
void Build(int l,int r,int h);
int Query(int l,int r,int x,int y,int k,int h);
int main()
{
//	freopen((name+in).c_str(),"r",stdin);
//	freopen((name+out).c_str(),"w",stdout);
	Init();
	Work();
	return 0;
}
void Init()
{
	scanf("%d%d%d%d",&n,&k,&L,&R);
	rep(i,1,n)scanf("%d",c+i),d[1][i]=sorted[i]=sum[i]=sum[i-1]+c[i],kth[i]=1;//,s[i]=s[i-1]+c[i];
	sort(sorted+1,sorted+1+n,greater<int>());
	Build(1,n,1);
}
void Work()
{
	int t;pii x;
	rep(i,1,n-L+1)
	{
		t=Query(1,n,i+L-1,i+R-1<=n?i+R-1:n,kth[i],1);
		q.push(pii(t-sum[i-1],i));
	}
	rep(i,1,k)
	{
		x=q.top();q.pop();
		ans+=x.first;
		kth[x.second]++;
		if(kth[x.second]<=R-L+1&&kth[x.second]<=(x.second+R-1<=n?x.second+R-1:n)-(x.second+L-1)+1)
		{
			t=Query(1,n,x.second+L-1,x.second+R-1<=n?x.second+R-1:n,kth[x.second],1);
			q.push(pii(t-sum[x.second-1],x.second));
		}
	}
	cout<<ans<<endl;
}
void Build(int l,int r,int h)
{
	if(l==r)return;
	int mid=l+r>>1,cnt=mid-l+1,smid=sorted[mid],lpos=l,rpos=mid+1,pos=0;
	rep(i,l,r)if(d[h][i]>smid)cnt--;
	rep(i,l,r)
	{
		if(d[h][i]>smid||d[h][i]==smid&&cnt)
		{
			pos++;if(d[h][i]==smid)cnt--;
			d[h+1][lpos++]=d[h][i];
		}
		else d[h+1][rpos++]=d[h][i];
		s[h][i]=pos;
	}
	Build(l,mid,h+1);
	Build(mid+1,r,h+1);
}
int Query(int l,int r,int x,int y,int k,int h)
{
	if(l==r)return sorted[l];
	int mid=l+r>>1,l1,l2;
	l1=(l==x)?0:s[h][x-1];
	l2=s[h][y];
	if(k<=l2-l1)return Query(l,mid,l+l1,l+l2-1,k,h+1);
	else return Query(mid+1,r,mid+1+x-(l+l1),mid+1+y-(l+l2),k-(l2-l1),h+1);
}