[数据结构与算法]CF1039E-Summer Oenothera Exhibition【LCT根号分治】

正题

题目链接: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;
}