只有一个整数，表示乐曲美妙度的最大值。
正解：ST表＋堆。然而我写的主席树。
跪求压常数大法，我的代码虽然bzoj上过了，但是只是总时间过了而已。。2s的点要跑3s。。
我们考虑建一棵主席树，第i棵树表示以i为起点的符合条件的和弦。然后我们就可以二分一个权值。当我们二分出权值后，把所有>=权值的数的个数都算出来，并求出这些和弦的和，如果个数>=k，那么就是合法的，如果<k就是不合法的。还有最后计算答案的时候，一定要减去重复的和弦。如果是主席树的话，那么要离散化，把空间压下来。我调了很久都是因为空间问题。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (500000000) 15 #define N (500010) 16 #define il inline 17 #define RG register 18 #define ll long long 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 20 21 using namespace std; 22 23 struct node{ ll tot,sum; }; 24 25 int ls[40*N],rs[40*N],rt[N],a[N],v[N],hsh[N],k,l,r,n,nn,TT,sz; 26 ll tt[40*N],ss[40*N],ans; 27 28 il int gi(){ 29 RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 30 if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x; 31 } 32 33 il void insert(RG int x,RG int &y,RG int l,RG int r,RG int k,RG int v,RG int fg){ 34 tt[y=++sz]=tt[x]+fg,ss[y]=ss[x]+v*fg,ls[y]=ls[x],rs[y]=rs[x]; 35 if (l==r) return; RG int mid=(l+r)>>1; 36 k<=mid ? insert(ls[x],ls[y],l,mid,k,v,fg) : insert(rs[x],rs[y],mid+1,r,k,v,fg); return; 37 } 38 39 il node query(RG int x,RG int l,RG int r,RG int v){ 40 RG int mid; RG ll tot=0,sum=0; 41 while (l<r){ 42 mid=(l+r)>>1; 43 if (v<=mid) tot+=tt[rs[x]],sum+=ss[rs[x]],r=mid,x=ls[x]; 44 else l=mid+1,x=rs[x]; 45 } 46 return (node){tot+tt[x],sum+ss[x]}; 47 } 48 49 il node check(RG int key){ 50 RG ll tot=0,sum=0; RG node res; 51 for (RG int i=1;i<=nn;++i){ 52 if (key+v[i-1]>hsh[TT]) continue; 53 RG int kk=lower_bound(hsh+1,hsh+TT+1,key+v[i-1])-hsh; 54 res=query(rt[i],1,TT,kk),tot+=res.tot,sum+=res.sum-res.tot*v[i-1]; 55 } 56 return (node){tot,sum}; 57 } 58 59 il void work(){ 60 n=gi(),k=gi(),l=gi(),r=gi(),nn=n-l+1; 61 for (RG int i=1;i<=n;++i) hsh[++TT]=a[i]=gi()+a[i-1]; 62 sort(hsh+1,hsh+TT+1),TT=unique(hsh+1,hsh+TT+1)-hsh-1; 63 for (RG int i=1;i<=n;++i) v[i]=a[i],a[i]=lower_bound(hsh+1,hsh+TT+1,a[i])-hsh; 64 for (RG int i=l;i<=r;++i) insert(rt[1],rt[1],1,TT,a[i],v[i],1); 65 for (RG int i=2;i<=nn;++i){ 66 insert(rt[i-1],rt[i],1,TT,a[l+i-2],v[l+i-2],-1); 67 if (r+i-1<=n) insert(rt[i],rt[i],1,TT,a[r+i-1],v[r+i-1],1); 68 } 69 RG int l=-inf,r=inf,mid; RG ll tot,res; 70 while (l<=r){ 71 mid=(l+r)>>1; RG node bl=check(mid); 72 if (bl.tot<k) r=mid-1; else tot=bl.tot,ans=bl.sum,res=mid,l=mid+1; 73 } 74 printf("%lld\n",ans-(ll)res*(tot-(ll)k)); return; 75 } 76 77 int main(){ 78 File("piano"); 79 work(); 80 return 0; 81 }
原文：http://www.cnblogs.com/wfj2048/p/6508853.html