正題

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

---

題目大意

給出$n$個數的序列，$m$次詢問至少將這個序列分成多少段才能滿足每一段的和不超過$w?q_i$。

$1\le n,m\le 10^5,1\le w,a_i\le 10^9$

---

解題思路

考慮暴力的做法，我們可以每次走到必須要分段時才分段顯然是正確的。

根據$w?q_i$從小到大來做，設$t_i$表示以$i$為左端點時，最長能分到的區間長度$t_i$，那么我們從$i$就能直接到達$i+t_i$。

那么我們從$1$出發一直往右跳看跳的次數就可以了，這個和[HNOI2010]彈飛綿羊很像，考慮用$LCT$去維護。

不過這個$t_i$是可能每次都在改變的，所以不能只靠這樣來做，但是注意到$i$每次會直接跳過$t_i?1$個位置，我們不需要統計全局的值。

所以我們考慮根號分治，對于一個$T=\sqrt{n}$，我們當$t_i\le T$時我們在$LCT$上條，當$t_i>T$時我們直接暴力跳。

同樣的我們不需要去維護這些$>T$的$t_i$，而是到達這些位置時直接二分下一個位置即可。

用一個堆去存$t_i\le T$的位置以方便更改。

時間復雜度：$O(n\sqrt{n}\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1e5+10,Q=230; int n,m,w,a[N],t[N],ans[N]; int f[N][19],g[N][19],lg[N]; pair<int,int> q[N]; priority_queue<pair<int,int> >h; struct LCT{int t[N][2],siz[N],fa[N];stack<int> s;bool r[N];bool Nroot(int x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(int x){return (t[fa[x]][1]==x);}void PushUp(int x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;}void PushR(int x){swap(t[x][0],t[x][1]);r[x]^=1;return;}void PushDown(int x){if(r[x]){PushR(t[x][0]);PushR(t[x][1]);r[x]=0;}return;}void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];t[x][xs^1]=y;t[y][xs]=w;if(Nroot(y))t[z][ys]=x;if(w)fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);PushUp(x);return;}void Splay(int x){int y=x;s.push(y);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y=0;x;y=x,x=fa[x])Splay(x),t[x][1]=y,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);PushR(x);return;}void Link(int x,int y){Access(x);fa[x]=y;return;}void Cut(int x,int y){Access(x);Splay(y);fa[x]=t[y][1]=0;PushUp(y);return;}int FindRoot(int x){Access(x);Splay(x);PushDown(x);while(t[x][0])x=t[x][0],PushDown(x);Splay(x);return x;} }T; int MIX(int l,int r){if(r>n)return 1e9+7;int z=lg[r-l+1];int x=max(g[l][z],g[r-(1<<z)+1][z]);int y=min(f[l][z],f[r-(1<<z)+1][z]);return x-y; } int nxts(int x,int w){int l=x,r=n;while(l<=r){int mid=(l+r)>>1;if(MIX(x,mid)<=w)l=mid+1;else r=mid-1;}return l; } int main() {scanf("%d%d%d",&n,&w,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i][0]=g[i][0]=a[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++){f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);g[i][j]=max(g[i][j-1],g[i+(1<<j-1)][j-1]);}for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int i=1;i<=n+1;i++)T.siz[i]=1;for(int i=1;i<=n;i++){t[i]=1,T.Link(i,i+t[i]);h.push(mp(-MIX(i,i+1),i));}for(int i=1;i<=m;i++)scanf("%d",&q[i].first),q[i].second=i;sort(q+1,q+1+m);reverse(q+1,q+1+m);for(int i=1;i<=m;i++){int x=w-q[i].first;while(!h.empty()&&-h.top().first<=x){int p=h.top().second;h.pop();T.Cut(p,p+t[p]);t[p]++;if(t[p]<=Q){T.Link(p,p+t[p]);h.push(mp(-MIX(p,p+t[p]),p));}else t[p]=-1;}int now=1,sum=0;while(now<n+1){if(t[now]==-1)now=nxts(now,x),sum++;else{T.Access(now);T.Splay(now);sum+=T.siz[now]-1;now=T.FindRoot(now);}}ans[q[i].second]=sum;}for(int i=1;i<=m;i++)printf("%d\n",ans[i]-1);return 0; }

總結

以上是生活随笔為你收集整理的CF1039E-Summer Oenothera Exhibition【LCT,根号分治】的全部內容，希望文章能夠幫你解決所遇到的問題。

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