NOI 2010. DAY 1. T2. 슈퍼 피아노

제목 의 대의:
n 개의 숫자 에서 k 개의 서로 다른 길이 가 l - r 사이 의 연속 서브 시퀀스 를 찾 아 가중치 와 최대 (n < = 500000, k < = 500000) 를 찾 습 니 다.
연감
이 문 제 는 합 법 적 인 하위 서열 이 매우 많은 데, 만약 소박 하면 분명히 이 문 제 를 풀 수 없다.
아주 아름 다운 생각 이 있 습 니 다. 주어진 출발점 에 대해 출발점 의 가중치 가 이미 알 고 있 습 니 다. 하위 서열 의 개 수 는 확실 합 니 다.
그러면 접두사 와 s [i] 를 기록 하고 주어진 출발점 에 대해 실제 적 으로 출발점 이 대표 하 는 구간 의 최대 가중치 를 묻 는 것 입 니 다. 이것 이 바로 RMQ 문제 입 니 다. ST 알고리즘 은 O (nlogn) - O (1) 시간 에 완성 할 수 있 습 니 다.
그러면 각 점 i 에 대해 pos [i] 가 i 에 대응 하 는 구간 에서 s [j] 의 최대 치 를 가리 키 고 있 습 니 다.
더미 로 5 원 그룹 (st, idx, l, r, v) 을 유지 하고 st 는 출발점 을 대표 하 며 idx 는 출발점 에 대응 하 는 구간 에서 최대 값 의 하 표, l, r 는 대응 하 는 구간 을 대표 하고 v 는 이 하위 서열 의 값 을 대표 합 니 다.
그러면 우 리 는 매번 더미 에서 이러한 5 원 조 를 꺼 낸 후에 구간 을 분열 시 켜 야 한다. 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, 이 문 제 는 나 무 를 나 누 거나 나 무 를 병합 하 는 연습 문제 로 사용 할 수 있 습 니 다. 그때 다시 한 번 쓰 겠 습 니 다.

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