[NOI2010]超级钢琴 主席树

[NOI2010]超级钢琴

链接

luogu

思路

和12省联考的异或粽子一样。

堆维护n个左端点，每次取出来再放回去次

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int _=5e5+7,INF=0x3f3f3f3f;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,k,l,r,sum[_],rt[_];

namespace seg {

	struct node {int l,r,siz;}e[_*20];

	int cnt;

	void insert(int l,int r,int k,int x,int &y) {

		e[y=++cnt]=e[x];

		e[y].siz++;

		if(l==r) return;

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

		if(k<=mid) insert(l,mid,k,e[x].l,e[y].l);

		else insert(mid+1,r,k,e[x].r,e[y].r);

	}

	int query(int l,int r,int k,int x,int y) {

		if(l==r) return l;

		int mid=(l+r)>>1,h=e[e[y].l].siz-e[e[x].l].siz;

		if(k<=h) return query(l,mid,k,e[x].l,e[y].l);

		else return query(mid+1,r,k-h,e[x].r,e[y].r);

	}

}

struct node {

	int val,l,r,k,id;

	bool operator < (const node &b) const {

		return val<b.val;

	}

};

priority_queue<node> q;

int lsh[_];

int main() {

	n=read(),k=read(),l=read(),r=read();

	for(int i=1;i<=n;++i) lsh[i]=sum[i]=sum[i-1]+read();

	sort(lsh+1,lsh+1+n);

	int len=unique(lsh+1,lsh+1+n)-lsh-1;

	for(int i=1;i<=n;++i) sum[i]=lower_bound(lsh+1,lsh+1+len,sum[i])-lsh;

	for(int i=1;i<=n;++i) seg::insert(1,n,sum[i],rt[i-1],rt[i]);

	for(int i=0;i<=n-l;++i) {

		int L=i+l,R=min(i+r,n);

		q.push(node{lsh[seg::query(1,n,R-L+1,rt[L-1],rt[R])]-lsh[sum[i]],L,R,R-L+1,i});

	}

	ll ans=0;

	while(k --> 0) {

		node u=q.top();q.pop();

		ans+=u.val;

		u.k--;

		if(u.k<=0) continue;

		u.val=lsh[seg::query(1,n,u.k,rt[u.l-1],rt[u.r])]-lsh[sum[u.id]];

		q.push(u);

	}

	cout<<ans<<"\n";

	return 0;

}