正題

題目鏈接:https://www.luogu.org/problemnew/show/P2048

---

題目大意

一個長度為$n$序列$a$。尋找$k$個子序列要求長度在$L～R$之間，求這$k$個子序列的最大和。

---

解題思路

首先對$a$求出前綴和數組$s$。題目轉換為求$k$個數對要求兩兩之間距離在$L～R$且差最大。

因為數對之間互不影響，所以顯然求前$k$大的數對就好了。

我們在大根堆之中存儲一個五元組$(l,r,id,x,val)$。表示對于后面的數$id$在$l～r$之間求一個$x$使得$val=a_{id}?a_x$最大。堆以$val$為關鍵字。$x$和$val$我們可以用$RMQ$快速計算出來。

然后我們開始時對于每個$i$我們將$(i?R,i?L,i,x,val)$丟入堆中。

之后執行$k$次取出對頂$(l,r,id,x,val)$使$ans+=val$。
然后將$(l,x?1,id,x^{\prime },va{l}^{\prime })$和$(x+1,r,id,x^{\prime },va{l}^{\prime })$重新丟入堆中，這樣就保證了對于不同的$id$，$x$不會重復而且也能取到最大。

時間復雜度$:O(nlog(n+k))$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=501000; ll n,k,L,R,lg[N],f[30][N],a[N],ans,w[30][N]; ll RMQ(ll l,ll r) {ll z=lg[r-l+1];return f[z][l]<f[z][r+1-(1<<z)]?w[z][l]:w[z][r+1-(1<<z)]; } struct node{ll l,r,x,id,val;node(ll _l=0,ll _r=0,ll _id=0){l=_l;r=_r;id=_id;x=RMQ(l,r);val=a[id]-a[x];} }; bool operator <(const node &a,const node &b) {return a.val<b.val;} priority_queue<node> q; int main() {scanf("%lld%lld%lld%lld",&n,&k,&L,&R);lg[0]=-1;for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]+=a[i-1];f[0][i]=a[i];w[0][i]=i;lg[i]=lg[i/2]+1;}for(ll i=1;(1<<i)<=n;i++)for(ll j=0;j+(1<<i)-1<=n;j++){if(f[i-1][j+(1<<i-1)]<f[i-1][j])w[i][j]=w[i-1][j+(1<<i-1)];elsew[i][j]=w[i-1][j];f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);}for(ll i=L;i<=n;i++)q.push(node(max(i-R,0ll),i-L,i));while(k--){node z=q.top();ans+=z.val;q.pop();if(z.x>z.l) q.push(node(z.l,z.x-1,z.id));if(z.x<z.r) q.push(node(z.x+1,z.r,z.id));}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P2048-[NOI2010]超级钢琴【RMQ,堆】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。