傳送門

考慮維護前綴和 $sum[i]$

那么對于每一個位置 $i$ ，左端點為 $i$ 右端點在 $[i+L-1,i+R-1]$ 區(qū)間的區(qū)間最大值容易維護

維護三元組 $(o,l,r)$ ，表示左端點為 $o$ ，右端點 $\in [l,r]$ 的區(qū)間最大值，然后把它扔到一個堆里，每次彈出最大值計算貢獻

計算完后，設(shè)此三元組右端點為 $t$，還要記得把 $(o,l,t-1)$，和 $(o,t+1,r)$ 扔到堆里

具體看代碼，不難理解

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=1e6+7; int n,K; int sum[N],f[N][21],Log[N]; namespace ST {//維護sum區(qū)間最大值的位置void init(){for(int i=1;i<=n;i++) f[i][0]=i;Log[0]=-1; for(int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;for(int k=1;(1<<k)<=n;k++)for(int i=1;i+(1<<k-1)<=n;i++){if(sum[f[i][k-1]]>sum[ f[ i+(1<<k-1) ][k-1] ]) f[i][k]=f[i][k-1];else f[i][k]=f[ i+(1<<k-1) ][k-1];}}inline int query(int l,int r){int k=Log[r-l+1];if(sum[ f[l][k] ]>sum[ f[r-(1<<k)+1][k] ]) return f[l][k];return f[r-(1<<k)+1][k];} } struct dat {int o,l,r,t;dat (int o,int l,int r) : o(o),l(l),r(r),t(ST::query(l,r)) {}inline bool operator < (const dat &tmp) const {return sum[t]-sum[o-1]<sum[tmp.t]-sum[tmp.o-1];} }; priority_queue <dat> Q; ll ans; int main() {n=read(),K=read(); int l=read(),r=read(),a;for(int i=1;i<=n;i++) a=read(),sum[i]=sum[i-1]+a;ST::init();for(int i=1;i<=n;i++)if(i+l-1<=n) Q.push( dat(i,i+l-1,min(n,i+r-1)) );while(K--){dat T=Q.top(); Q.pop(); ans+=(sum[T.t]-sum[T.o-1]);if(T.l<T.t) Q.push(dat(T.o,T.l,T.t-1));if(T.r>T.t) Q.push(dat(T.o,T.t+1,T.r));}printf("%lld",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LLTYYC/p/10682537.html

總結(jié)

以上是生活随笔為你收集整理的P2048 [NOI2010]超级钢琴的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。