【BZOJ 2006】[NOI2010] 超级钢琴

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano

这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
	int pos,num,val;
	bool operator < (const Query & B) const {
		return val < B.val;
	}
};
priority_queue<Query> que;

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N],ans_tmp;
	
	void insert(int p, int &w, int l, int r, int v) {
		w = ++cnt; sum[w] = sum[p] + 1;
		memcpy(ch[w],ch[p],sizeof(ch[0]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
			else insert(ch[p][1], ch[w][1], mid, r, v);
		} 
	} 
	
	inline void insert(int p, int w) {
		insert(root[p-1], root[p], 1, INF, w);
	} 
	
	void query(int p, int w, int l, int r, int num) {
		if (l == r) ans_tmp = l;
		else {
			int mid = l + r + 1 >> 1;
			if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
			else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
		}
	}
	
	inline int query(int l, int r, int num) {
		query(root[l-1],root[r],1,INF,num);
		return ans_tmp;
	}
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read(); k = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
	for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
	for (int i=1;i+L-1<=n;i++) {
		Query tmp; tmp.pos = i; tmp.num = 1;
		tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
		que.push(tmp);
	}
	
	LL vout = 0;
	for (int i=1,p;i<=k;i++) {
		Query tmp = que.top(); que.pop();
		vout += tmp.val; 
		if (tmp.num < R - L + 1) {
			tmp.num++; p = tmp.pos;
			if (n - (p+L-1) + 1 < tmp.num) continue;
			tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
			que.push(tmp);
		}
	}
	printf("%lld\n",vout);
	return 0;
}

16 thoughts to “【BZOJ 2006】[NOI2010] 超级钢琴”

  1. I think this is among the most significant information for me. And i’m glad reading your article. But want to remark on some general things, The web site style is ideal, the articles is really nice : D. Good job, cheers

  2. 417649 887467Chaga mushroom tea leaf is thought-about any adverse health elixir at Spain, Siberia and lots of n . Countries in europe sadly contains before you go ahead significantly avoidable the main limelight under western culture. Mushroom 496716

  3. 724091 797185Really good post. I just stumbled upon your weblog and wanted to say that Ive truly enjoyed surfing about your weblog posts. Right after all I will be subscribing to your feed and I hope you write once more extremely soon! 789978

  4. 408297 432383Someone necessarily assist to make critically articles Id state. This is the first time I frequented your web page and thus far? I amazed with the analysis you produced to make this actual submit incredible. Outstanding activity! 648867

  5. 139956 176985Located your weblog and decided to have a study on it, not what I usually do, but this blog is fantastic. Awesome to see a site thats not spammed, and in fact makes some sense. Anyway, fantastic write up. 492635

  6. 982826 39848I usually cant discover it in me to care enough to leaves a comment for articles on the internet but this was really pretty great, thanks and maintain it up, Ill check back once more 751176

  7. 329037 825327 Nice post. I learn something more challenging on different blogs everyday. It will always be stimulating to read content from other writers and practice slightly something from their store. Id prefer to use some with the content on my weblog whether you dont mind. Natually Ill give you a link on your web blog. Thanks for sharing. 853847

Leave a Reply

Your email address will not be published. Required fields are marked *