正題

題目鏈接:https://www.luogu.com.cn/problem/P7408

---

題目大意

一個有$n+1$層的地牢，從$i$到$i+1$層要$A_i$點能量，第$i$層可以花費$B_i$獲得$1$點能量。

$m$次詢問從$S_i$層出發到第$T_i$層在能量上限為$U_i$的情況下至少需要花費多少。

$1\le n,m\le 2\times 10^5$

---

解題思路

模型可以轉換成坐標軸上有$n$個點，第$i$個在$A_i$，考慮使用一個點獲得的能量走的路就是這個點伸出的線覆蓋的范圍，然后使得范圍乘上$B_i$的和最小。

考慮能量上限的限制其實就是每個點覆蓋的范圍不能超過自身的$U_i$格。

考慮一個點覆蓋范圍根據$U_i$變化的變化：

• 沒有其他影響，自己正常延伸，此時覆蓋范圍為一個和$U_i$有關的一次函數
• 延伸到下一個比自己大的位置，不能繼續延伸，此時為一個常數
• 上一個比自己小的數延伸過來，此時為一個單調下降的一次函數
• 完全被上一個比自己小的覆蓋，此時為$0$

也就是意味著每個點只需要考慮前后兩個比自己小的數分成若干種情況即可。

考慮倒序枚舉點，然后用樹狀數組記錄一次項系數的和與二次項系數的和。

對于結尾的限制，我們找到能到達終點的最后的點直接走向它，然后減去那個點的貢獻即可。

時間復雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=2e5+10,inf=1e18; struct node{ll l,r,u; }q[N]; ll n,m,a[N],b[N],s[N],ans[N]; ll cnt,u[N],nxt[N],pre[N]; ll f[N][20],g[N][20],lg[N]; vector<ll> d[N],v[N]; stack<ll> st; ll rmqf(ll l,ll r){ll z=lg[r-l+1];l=f[l][z];r=f[r-(1<<z)+1][z];return (b[l]<b[r])?l:r; } ll rmqg(ll l,ll r){ll z=lg[r-l+1];l=g[l][z];r=g[r-(1<<z)+1][z];return (a[l]>a[r])?l:r; } struct TreeBinary{ll t[N];void Updata(ll x,ll val){while(x<=cnt){t[x]+=val;x+=lowbit(x);}return;}ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;}void Change(ll l,ll r,ll val){if(l>r)return;l=lower_bound(u+1,u+1+cnt,l)-u;r=upper_bound(u+1,u+1+cnt,r)-u;Updata(l,val);Updata(r,-val);return;} }K,B; signed main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),s[i+1]=s[i]+a[i];for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);for(ll i=2;i<=n+1;i++)lg[i]=lg[i>>1]+1;for(ll i=1;i<=n+1;i++)f[i][0]=g[i][0]=i;for(ll j=1;(1<<j)<=n+1;j++)for(ll i=1;i+(1<<j)-1<=n+1;i++){ll x=f[i][j-1],y=f[i+(1<<j-1)][j-1];f[i][j]=(b[x]<b[y])?x:y;x=g[i][j-1];y=g[i+(1<<j-1)][j-1];g[i][j]=(a[x]>a[y])?x:y;}for(ll i=n;i>=1;i--){while(!st.empty()&&b[i]<=b[st.top()]){pre[st.top()]=i;st.pop();}if(st.empty())nxt[i]=n+1;else nxt[i]=st.top();st.push(i);}for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].u);u[i]=q[i].u;ll las=lower_bound(s+1,s+1+n,s[q[i].r]-u[i])-s;las=min(las,q[i].r-1);las=max(min(las,q[i].r-1),q[i].l);las=rmqf(las,q[i].r-1);v[q[i].l].push_back(i);v[las].push_back(-i);ans[i]+=(s[q[i].r]-s[las])*b[las];}sort(u+1,u+1+m);cnt=unique(u+1,u+1+m)-u-1;for(ll i=n;i>=1;i--){K.Change(0,s[nxt[i]]-s[i],b[i]);B.Change(s[nxt[i]]-s[i]+1,inf,b[i]*(s[nxt[i]]-s[i]));d[pre[i]].push_back(i);for(ll j=0;j<d[i].size();j++){ll x=d[i][j];K.Change(s[x]-s[i],s[nxt[x]]-s[i],-b[x]);B.Change(s[x]-s[i],s[nxt[x]]-s[i],b[x]*(s[x]-s[i]));B.Change(s[nxt[x]]-s[i]+1,inf,-b[x]*(s[nxt[x]]-s[x]));}for(ll j=0;j<v[i].size();j++){ll x=v[i][j],op=1;if(x<0)x=-x,op=-op;ll w=lower_bound(u+1,u+1+cnt,q[x].u)-u;ans[x]+=op*(q[x].u*K.Ask(w)+B.Ask(w));}}for(ll i=1;i<=m;i++){if(a[rmqg(q[i].l,q[i].r-1)]>q[i].u)puts("-1");else printf("%lld\n",ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的P7408-[JOI 2021 Final]ダンジョン 3【贪心,树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

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