NOI2010 超级钢琴
Description:
给定一个序列，求前k大区间和
Solution:
我们用f(i,l,r)表示左端点为i，右端点在[l,r]的最大区间和
设右端点在k时区间和最大 区间和为s[k]-s[i-1]
由于s[i-1]是确定的 我们只要求出最大的s[k]即可
即区间最值 可以用ST表求
这样我们可以[1,n]的每个点作为起点的最大区间和
但是有两个问题：1 这样求出的区间和并不一定都是最优的
可能以一个点为左端点的次优解比以另外一个点为左端点的最优解还要优
2 这样求出的区间和可能不够k个
其实问题就是我们想要求出一些以某点为左端点的次优解并且加入优先队列得出总体最优解
以（i,l,r,k）为四元组加入优先队列（含义见上）
取出优先队列的top 接着把(i,l,k-1,pos),(i,k+1,r,pos)加入优先队列 他们都有可能成为下一个top
这里的pos用ST表求解即可 所以在记录值时还要记录位置（就是code里的id[]）
CODE
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<queue> 5 #define Rg register 6 #define go(i,a,b) for(Rg int i=a;i<=b;i++) 7 #define ll long long 8 using namespace std; 9 int rd() 10 { 11 int x=0,y=1;char c=getchar(); 12 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 13 while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} 14 return x*y; 15 } 16 const int N=500005,T=20; 17 int n,k,L,R,s[N],f[N][T],id[N][T]; 18 ll ans; 19 struct node 20 { 21 int u,l,r,pos;//u:begin v:[l,r] 22 bool operator <(node y)const 23 { 24 return s[pos]-s[u-1]<s[y.pos]-s[y.u-1]; 25 } 26 }tmp; 27 priority_queue<node>q; 28 void sol(int &pos,int l,int r) 29 { 30 int j=log2(r-l+1); 31 if(f[l][j]>f[r-(1<<j)+1][j]) pos=id[l][j]; 32 else pos=id[r-(1<<j)+1][j]; 33 } 34 int main() 35 { 36 n=rd(),k=rd(),L=rd(),R=rd(); 37 go(i,1,n) s[i]=s[i-1]+rd(),f[i][0]=s[i],id[i][0]=i; 38 go(j,1,T-1) 39 go(i,1,n) 40 { 41 if(i+(1<<j)-1>n) break; 42 if(f[i][j-1]>f[i+(1<<j-1)][j-1]) f[i][j]=f[i][j-1],id[i][j]=id[i][j-1]; 43 else f[i][j]=f[i+(1<<j-1)][j-1],id[i][j]=id[i+(1<<j-1)][j-1]; 44 } 45 go(i,1,n) 46 { 47 int l=i+L-1,r=min(i+R-1,n),pos,u=i; 48 if(i+L-1>n) break; 49 sol(pos,l,r);tmp=(node){u,l,r,pos};q.push(tmp); 50 } 51 while(k--) 52 { 53 tmp=q.top();q.pop(); 54 int u=tmp.u,l=tmp.l,r=tmp.r,pos=tmp.pos,tps=pos; 55 ans+=s[pos]-s[u-1]; 56 if(tps>l) 57 {sol(pos,l,tps-1);tmp=(node){u,l,tps-1,pos};q.push(tmp);} 58 if(tps<r) 59 {sol(pos,tps+1,r);tmp=(node){u,tps+1,r,pos};q.push(tmp);} 60 } 61 printf("%lld",ans); 62 return 0; 63 }