★★★☆?? 輸入文件：piano.in?? 輸出文件：piano.out?? 簡單對比
時間限制：2 s?? 內存限制：512 MB
超級鋼琴
【問題描述】
小Z是一個小有名氣的鋼琴家，最近C博士送給了小Z一架超級鋼琴，小Z希望能夠用這架鋼琴創作出世界上最美妙的音樂。
這架超級鋼琴可以彈奏出n個音符，編號為1至n。第i個音符的美妙度為Ai，其中Ai可正可負。
一個“超級和弦”由若干個編號連續的音符組成，包含的音符個數不少于L且不多于R。我們定義超級和弦的美妙度為其包含的所有音符的美妙度之和。兩個超級和弦被認為是相同的，當且僅當這兩個超級和弦所包含的音符集合是相同的。
小Z決定創作一首由k個超級和弦組成的樂曲，為了使得樂曲更加動聽，小Z要求該樂曲由k個不同的超級和弦組成。我們定義一首樂曲的美妙度為其所包含的所有超級和弦的美妙度之和。小Z想知道他能夠創作出來的樂曲美妙度最大值是多少。
【輸入格式】
輸入文件名為piano.in。
輸入文件第一行包含四個正整數n, k, L, R。其中n為音符的個數，k為樂曲所包含的超級和弦個數，L和R分別是超級和弦所包含音符個數的下限和上限。
接下來n行，每行包含一個整數Ai，表示按編號從小到大每個音符的美妙度。
【輸出格式】
輸出文件為piano.out。
輸出文件只有一個整數，表示樂曲美妙度的最大值。
【樣例輸入】
4 3 2 3
3
2
-6
8
【樣例輸出】
11
【樣例說明】
共有5種不同的超級和弦：
- 音符1 ~ 2，美妙度為3 + 2 = 5
- 音符2 ~ 3，美妙度為2 + (-6) = -4
- 音符3 ~ 4，美妙度為(-6) + 8 = 2
- 音符1 ~ 3，美妙度為3 + 2 + (-6) = -1
- 音符2 ~ 4，美妙度為2 + (-6) + 8 = 4
最優方案為：樂曲由和弦1，和弦3，和弦5組成，美妙度為5 + 2 + 4 = 11。
【數據規模和約定】
總共10個測試點，數據范圍滿足：
所有數據滿足：-1000 ≤ Ai ≤ 1000，1 ≤ L ≤ R ≤ n且保證一定存在滿足要求的樂曲。
這題考慮貪心，用一個三元組記錄node為起點，能取到的右端點區間。
用ST可以O(1)求出區間中應取哪一個右端點，每次取最大的，處理成兩個子區間，放回heap中，繼續貪心。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int maxn=500010; 6 int n,K,L,R,s[maxn],pos; 7 struct Node{ 8 int node,l,r; 9 Node(int NODE=0,int L=0,int R=0){ 10 node=NODE;l=L;r=R; 11 } 12 }; 13 int mm[maxn],Max[maxn][25],Mpos[maxn][25]; 14 15 int Query(int l,int r){ 16 if(Max[l][mm[r-l+1]]<Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]]){ 17 pos=Mpos[r-(1<<mm[r-l+1])+1][mm[r-l+1]]; 18 return Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]]; 19 } 20 else{ 21 pos=Mpos[l][mm[r-l+1]]; 22 return Max[l][mm[r-l+1]]; 23 } 24 } 25 26 int Q(Node x){ 27 return Query(x.l,x.r)-s[x.node-1]; 28 } 29 30 struct Heap{ 31 int cnt; 32 Node h[maxn<<1]; 33 void Insert(Node x){ 34 int p=++cnt; 35 while(p!=1){ 36 if(Q(x)<=Q(h[p>>1]))break; 37 h[p]=h[p>>1]; 38 p>>=1; 39 } 40 h[p]=x; 41 } 42 43 void Delete(){ 44 int p=1,a,b; 45 Node x=h[cnt--]; 46 while(p*2<=cnt){ 47 a=p<<1;b=a|1; 48 if(b<=cnt&&Q(h[a])<Q(h[b]))a=b; 49 if(Q(h[a])<=Q(x))break; 50 h[p]=h[a]; 51 p=a; 52 } 53 h[p]=x; 54 } 55 }q; 56 57 int main(){ 58 freopen("piano.in","r",stdin); 59 freopen("piano.out","w",stdout); 60 scanf("%d%d%d%d",&n,&K,&L,&R); 61 62 for(int i=1;i<=n;i++) 63 scanf("%d",&s[i]); 64 for(int i=1;i<=n;i++) 65 s[i]+=s[i-1]; 66 67 mm[0]=-1; 68 for(int i=1;i<=n;i++){ 69 mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1]; 70 Max[i][0]=s[i]; 71 Mpos[i][0]=i; 72 } 73 74 for(int k=1;k<=mm[n];k++) 75 for(int i=1;i+(1<<k)-1<=n;i++){ 76 if(Max[i][k-1]>Max[i+(1<<(k-1))][k-1]){ 77 Max[i][k]=Max[i][k-1]; 78 Mpos[i][k]=Mpos[i][k-1]; 79 } 80 else{ 81 Max[i][k]=Max[i+(1<<(k-1))][k-1]; 82 Mpos[i][k]=Mpos[i+(1<<(k-1))][k-1]; 83 } 84 } 85 86 for(int i=1;i<=n-L+1;i++) 87 q.Insert(Node(i,i+L-1,min(i+R-1,n))); 88 89 long long ans=0; 90 int p; 91 Node x; 92 while(K--){ 93 ans+=Q(q.h[1]); 94 x=q.h[1];p=pos; 95 q.Delete(); 96 97 if(x.l<p)q.Insert(Node(x.node,x.l,p-1)); 98 if(x.r>p)q.Insert(Node(x.node,p+1,x.r)); 99 } 100 printf("%lld\n",ans); 101 return 0; 102 }
?
 - 不要吝惜贊美)
)
