NOI 201.Day 1.T 2.スーパーピアノ

タイトルの大意:
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、dx-1、v)に分割します.
最大k個の採取により、n＋k個の要素が最大で、時間複雑度はO(n＋k)log(n＋k)となります.
具体的な実現はコードを見ます.
もう一つの方法は区間を分割するのではなく、この区間のk番目の大きさの要素を記録するために必要です.これは木を区分するか、あるいは木を并木するというデータ構造が必要です.何年も書かないので、もう忘れてしまいました.
そして、この問題は木を分ける練習問題として、また書きます.

//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);
}