題目鏈接

https://codeforces.com/contest/671/problem/E

題解

完全不會做……基本是抄lk的代碼
ruogu的題解: https://www.luogu.com.cn/blog/ruogu-pupil/cf671esoj809-tan-xin-er-fen-tan-suo-shen-xian#
Orz lk & ruogu
注: 本文中\(a,b,m\)分別表示原題中的\(g,w,k\)
首先考慮如何分配方案，有一個顯然的貪心是從左往右遇到不得不加油的時候就加上，保證從左到右合法，最后剩下的錢全都加到右端點，以盡可能地保證從右往左合法。
設\(f_i=f_{i-1}+a_{i-1}-b_{i-1},g_i=g_{i-1}+b_{i-1}-a_i\)
不考慮\(a\)的增加，區間\([l,r]\)合法當且僅當\(f_l=\min^r_{i=l}f_i, g_r=\min^r_{i=l}g_i\)
若\(a_i\)增加\(1\), 則對于\(j\ge i\), \(f_j\)增加\(1\), 對于\(j\gt i\), \(g_j\)減少\(1\), 設改變后的\(g\)為\(h\)數組
我們從后往前枚舉\(l\), 順便維護單調棧，考慮從\(l\)往右可達的最大的\(r\)可以直接在單調棧上二分求出，記為\(R\). 我們在維護單調棧的同時也可以利用線段樹區間加維護出\(h\)
則對于\(r\)有\(h_r=g_r+m\)，要查詢滿足\(g_r-m\le min^{r-1}_{i=l}h_i\)且\(l\le i\le R\)的最大\(r\)
（所以其實使用前綴和而非后綴和是一個很妙的思路，它保證了當\(r\)取不同值時\(g_r\)的增加量恒為\(m\)）
考慮直接線段樹上二分，當走到線段樹上一個節點時，若\(R>mid\)且左半邊的\(h\)的最小值大于等于右邊\(g\)的最小值\(-k\), 那么就遞歸右邊，右邊一定有答案（但不一定在\(R\)的左邊）。這是因為顯然左半邊的\(h_i\ge g_i-k\), 右半邊的點都滿足\(h_i\le g_i-k\le g_r-k\). 如果找到的點在\(R\)的右邊，那么返回無解，這種情況只會發生一次，不影響復雜度。如果右邊返回無解或\(R\le mid\), 在這種情況下，若當前最小的\(h\)大于等于左邊\(g\)的最小值\(-m\)則遞歸左邊, 否則仍然返回無解。對于一次向左遞歸，能夠保證找到解，因此復雜度正確。（可能講得不清楚……詳見代碼）
時間復雜度\(O(n\log n)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x=0,f=1; char ch=getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-'0';}return x*f; }const int N = 1e6; const llong INF = 1e16; llong a[N+3],b[N+3],f[N+3],g[N+3]; int stk[N+3]; int n,tp; llong m; int ans;struct SgTNode {llong h,g,tag;SgTNode() {h = INF,g = -INF;} } sgt[(N<<2)+3]; void pushdown(int u) {if(!sgt[u].tag) return; llong tag = sgt[u].tag;sgt[u<<1].h += tag,sgt[u<<1].tag += tag;sgt[u<<1|1].h += tag,sgt[u<<1|1].tag += tag;sgt[u].tag = 0ll; } void updateg(int u,int le,int ri,int pos) {if(le==ri) {sgt[u].g = sgt[u].h = g[pos]; return;}int mid = (le+ri)>>1; pushdown(u);if(pos<=mid) {updateg(u<<1,le,mid,pos);}else {updateg(u<<1|1,mid+1,ri,pos);}sgt[u].g = min(sgt[u<<1].g,sgt[u<<1|1].g); sgt[u].h = min(sgt[u<<1].h,sgt[u<<1|1].h); } void addh(int u,int le,int ri,int lb,int rb,llong x) {if(le>=lb && ri<=rb) {sgt[u].h += x,sgt[u].tag += x; return;}int mid = (le+ri)>>1; pushdown(u);if(lb<=mid) {addh(u<<1,le,mid,lb,rb,x);}if(rb>mid) {addh(u<<1|1,mid+1,ri,lb,rb,x);}sgt[u].h = min(sgt[u<<1].h,sgt[u<<1|1].h); } int query(int u,int le,int ri,int rb,llong x) {if(le>rb) {return -1;}if(le==ri) {return le;}int mid = (le+ri)>>1; pushdown(u);llong lv = min(x,sgt[u<<1].h);if(rb>mid && lv>=sgt[u<<1|1].g-m){int ret = query(u<<1|1,mid+1,ri,rb,lv);if(ret!=-1) return ret;}if(sgt[u<<1].g-m<=x) return query(u<<1,le,mid,rb,x);return -1; }int main() {scanf("%d%I64d",&n,&m);for(int i=1; i<n; i++) scanf("%I64d",&b[i]);for(int i=1; i<=n; i++) scanf("%I64d",&a[i]);for(int i=1; i<=n; i++) f[i] = f[i-1]+a[i-1]-b[i-1];for(int i=1; i<=n; i++) g[i] = g[i-1]+b[i-1]-a[i];stk[0] = n+1; f[n+1] = -INF;for(int i=n; i>=1; i--){updateg(1,1,n,i);while(tp>0 && f[stk[tp]]>=f[i]){if(tp>1){addh(1,1,n,stk[tp-1]-1,n,f[stk[tp]]-f[stk[tp-1]]);}tp--;}tp++; stk[tp] = i;if(tp>1){addh(1,1,n,stk[tp-1]-1,n,f[stk[tp-1]]-f[stk[tp]]);}int left = 0,right = tp;while(left<right){int mid = (left+right+1)>>1;if(f[i]-f[stk[mid]]>m) {left = mid;}else {right = mid-1;}}int r = stk[left]-1;int ret = query(1,1,n,r,INF);ans = max(ans,ret-i+1);}printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 671E Organizing a Race (贪心、线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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