题解 P2048 【[NOI2010]超级钢琴】
shadowice1984 · · 题解
st表太神啦~
但是似乎主席树吸氧之后跑的飞起呢~(或者是因为stl的问题？反正开O2和不开O2大概差了4倍常数)
本题题解
这道题简单来说，就是给你一个序列a，求前k大长度在(l,r)内的子串和
然后简单来说，我们可以
然而显然会t的飞起对吧……
所以我们需要想一些机智的方法
这道题呢我们可以采取类似于贪心的思路，先找到最大值，然后删掉最大值，继续找剩下值中的最大值就可以了
假设现在我们一个区间都没删，现在要找最大值，
那么我们枚举左端点l，然后考虑对于一个给定的左端点l哪个是最优的右端点r 因为长度限制是[l,r]因此对于这个l来讲，所有合法的右端点r形成一个区间
当然是一个区间的前缀和值的最大值所对应的r了，因为总之你都要减去左端点的前缀和……，因此当然是要r的前缀和最大咯
这是一个区间最大值问题，当然可以使用st表解决这个问题
但是如果使用主席树解决这个静态区间第k大问题也不是不可以对吧……
然后我们对于每一个左端点都求出了一个最大合法的子串和
所以把这些值放进堆里取就可以找到最大值，好了我们现在有了一个最大值！
现在我们取出了这个最大值……我们发现此时这个左端点对应的区间第2大可能是此时最大的值，因此我们再求一遍区间第2大插堆里去，同理如果我们取出来来了区间第2大就插区间第3大，当然如果取掉了区间最小值就不能插入了……
(什么？你不会使用主席树求静态区间第k大？出门右转你站膜板区，包教包会~)
上代码~
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=5*1e5+10;typedef long long ll;
int n;int k;int l;int r;int sum[N];ll res;int lsh[N];int rk[N];
int dl[N];int dr[N];
inline bool cmp(int a,int b){return sum[a]<sum[b];}//离散化
struct data
{
int rk;int l;int v;
friend bool operator <(data a,data b){return a.v<b.v;}
};priority_queue <data> pq;//保存答案的堆
struct per_linetree//主席树板子，压行之后还是比较短小的
{
int s[25*N][2];int val[25*N];int root[N];int ct;int tim;
per_linetree(){ct=root[0]=1;}
inline void setadd(int p1,int p2,int l,int r,int pos)
{
val[p2]=val[p1]+1;if(r-l==1){return;}int mid=(l+r)/2;
if(pos<=mid){s[p2][0]=++ct;s[p2][1]=s[p1][1];setadd(s[p1][0],ct,l,mid,pos);}
else {s[p2][1]=++ct;s[p2][0]=s[p1][0];setadd(s[p1][1],ct,mid,r,pos);}
}
inline int kth(int p1,int p2,int l,int r,int rk)
{
if(r-l==1){return r;}int nv=val[s[p2][0]]-val[s[p1][0]];int mid=(l+r)/2;
if(rk>nv){return kth(s[p1][1],s[p2][1],mid,r,rk-nv);}
else {return kth(s[p1][0],s[p2][0],l,mid,rk);}
}
inline void cadd(int pos){setadd(root[tim],root[tim+1]=++ct,0,n,pos);tim++;}
inline int ckth(int l,int r,int rk){return kth(root[l],root[r],0,n,rk);}
}plt;
int main()
{
scanf("%d%d%d%d",&n,&k,&l,&r);
for(int i=1;i<=n;i++){scanf("%d",&sum[i]);sum[i]+=sum[i-1];}//前缀和
for(int i=1;i<=n;i++){lsh[i]=i;}sort(lsh+1,lsh+n+1,cmp);//离散化
rk[lsh[1]]=1;for(int i=2;i<=n;i++){rk[lsh[i]]=(sum[lsh[i]]==sum[lsh[i-1]])?rk[lsh[i-1]]:i;}
for(int i=1;i<=n;i++){plt.cadd(rk[i]);}
dl[0]=l-1;dr[0]=r-1;//求出每个i对应的区间左右端点
for(int i=1;i<=n;i++)//插入的东西会比较恶心，凑合着看吧……
{
dl[i]=dl[i-1]+1;dr[i]=min(dr[i-1]+1,n);if(dl[i]>dr[i]){break;}
pq.push((data){dr[i]-dl[i]+1,i,sum[lsh[plt.ckth(dl[i]-1,dr[i],dr[i]-dl[i]+1)]]-sum[i-1]});
}
for(int i=1;i<=k;i++)
{
data nw=pq.top();pq.pop();int v=nw.l;res+=nw.v;
if(nw.rk==1){continue;}//判一下是不是最小值
pq.push((data){nw.rk-1,v,sum[lsh[plt.ckth(dl[v]-1,dr[v],nw.rk-1)]]-sum[v-1]});//不是最小值就接着插入
}printf("%lld",res);return 0;//拜拜程序~
}