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

花了一个星期，总算把这一道该死的毒瘤题做完了。

这道题有很多种解法，我是用优先队列+主席树。

首先每一个区间的和，可以表示为两个前缀和之差。

我们显然可以知道，每一次找到的那个最大值必然在以一个点为最后一个点的区间之内。

所以我们可以把每一个点为最后一个点的最大值的区间求出来，先打入队列。

然后每一次打出来一个值，我们就把这个区间的最后一个值的位置的排名前一名的那一个区间打入队列。

这样重复计算即可。

至于实现，我们可以将每一个前缀和建一个主席树，然后我们维护一个三元组(add,cnt,end)

add维护区间和。

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

 end维护结尾的点。

具体实现有点迷，注意在建主席树的时候记得把0给建进去，会少不少麻烦。

剩下的就是主席树区间第k大了。

贴上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define maxn 500100
using 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
*/

有什么写的不好的地方大家尽管提出。

谢谢！！