题解 P2048 【[NOI2010]超级钢琴】

st表太神啦~ 但是似乎主席树吸氧之后跑的飞起呢~(或者是因为stl的问题？反正开O2和不开O2大概差了4倍常数) ## 本题题解 这道题简单来说，就是给你一个序列a，求前k大长度在(l,r)内的子串和 然后简单来说，我们可以$O(n^2)$的处理出来所有子串的和，然后直接暴力的跑sort或者堆就可以了，为了快速计算子串和当然需要前缀和 然而显然会t的飞起对吧…… 所以我们需要想一些机智的方法 这道题呢我们可以采取类似于贪心的思路，先找到最大值，然后删掉最大值，继续找剩下值中的最大值就可以了 假设现在我们一个区间都没删，现在要找最大值， 那么我们枚举左端点l，然后考虑对于一个给定的左端点l哪个是最优的右端点r 因为长度限制是[l,r]因此对于这个l来讲，所有合法的右端点r形成一个区间 当然是一个区间的前缀和值的最大值所对应的r了，因为总之你都要减去左端点的前缀和……，因此当然是要r的前缀和最大咯 这是一个区间最大值问题，当然可以使用st表解决这个问题 但是如果使用主席树解决这个静态区间第k大问题也不是不可以对吧…… 然后我们对于每一个左端点都求出了一个最大合法的子串和 所以把这些值放进堆里取就可以找到最大值，好了我们现在有了一个最大值！ 现在我们取出了这个最大值……我们发现此时这个左端点对应的区间第2大可能是此时最大的值，因此我们再求一遍区间第2大插堆里去，同理如果我们取出来来了区间第2大就插区间第3大，当然如果取掉了区间最小值就不能插入了…… (什么？你不会使用主席树求静态区间第k大？出门右转你站膜板区，包教包会~) 上代码~ ```C #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;//拜拜程序~ } ```