# [luogu2048] [bzoj2006] [NOI2010] 超级钢琴 题解

2018-02-06 08:09:23来源:cnblogs.com作者:justin_cao人点击

cnt维护当前在以这个最后一个位置最后的区间的排名。

end维护结尾的点。

`#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<queue>#define maxn 500100using namespace std;typedef long long ll;ll a[maxn];ll b[maxn];int lx,rx,n,k;int root[maxn];int tot;struct P{	int l,r,sum;}tree[maxn*20];struct X{	ll add;	int cnt,end;};map<ll,int>ma; struct cmp{	bool operator () (const X a,const X b) const	{		return a.add<b.add;	}};priority_queue<X,vector<X>,cmp > q;void update(int k1,int k2,int l,int r,int x)//k1-build,k2-find{    if(l==r)    {        tree[k1].sum=tree[k2].sum+1;        return;    }    else    {        int mid=(l+r)/2;        if(x>=l&&x<=mid)        {            tot++;            tree[k1].l=tot;            tree[k1].r=tree[k2].r;            update(tree[k1].l,tree[k2].l,l,mid,x);        }        else        {            tot++;            tree[k1].r=tot;            tree[k1].l=tree[k2].l;            update(tree[k1].r,tree[k2].r,mid+1,r,x);        }    }    tree[k1].sum=tree[tree[k1].l].sum+tree[tree[k1].r].sum;}int query(int i,int j,int k,int l,int r){    if(l==r)  return l;    int t=tree[tree[j].l].sum-tree[tree[i].l].sum;    int mid=(l+r)/2;    if(k<=t)  return query(tree[i].l,tree[j].l,k,l,mid);    else      return query(tree[i].r,tree[j].r,k-t,mid+1,r);}void work(int a,int b,int c){	X y;	y.add=a;	y.end=b;	y.cnt=c;	q.push(y);}ll ans;int main(){	scanf("%d%d%d%d",&n,&k,&lx,&rx);	for(int i=1;i<=n;i++)	{		 ll x;		 scanf("%lld",&x);		 a[i+1]=a[i]+x; 	}	for(int i=1;i<=n+1;i++)  b[i]=a[i];	sort(b+1,b+n+2);	int o=unique(b+1,b+n+2)-b-1;	for(int i=1;i<=o;i++)    ma[b[i]]=i;	for(int i=1;i<=n+1;i++)    root[i]=i;	tot=n+1;	for(int i=1;i<=n+1;i++)  update(root[i],root[i-1],1,o,ma[a[i]]);	for(int i=lx;i<=n;i++)	{		int p1=i-lx+1;		int p2=max(1,i-rx+1);		ll t=b[query(root[p2-1],root[p1],1,1,o)];		work(a[i+1]-t,i,1);	}	int sumx=0;	while(true)	{		X now=q.top();		q.pop();		ans+=now.add;		sumx++;		if(sumx==k)  break;		int p1=now.end;		int p2=now.cnt;		int k1=p1-lx+1;		int k2=max(p1-rx+1,1);		if(p2==k1-k2+1)  continue;		else{ll u=b[query(root[k2-1],root[k1],p2+1,1,o)];work(a[p1+1]-u,p1,p2+1);		}	}	cout<<ans<<endl;	return 0;}/*4 3 2 3 3 2 -6 8*/`