题意
给一个长度为 (n) 的序列, (q) 次询问,次给一个 (k_i) ，问最少将序列划分成多少次，满足每一段的极差不超过(w−k_i).
(1 leq n, q leq 10^5, 1 leq w leq 10^9,1 leq k_i leq w，0 leq x_i leq 10^9)
分析
-
每次直接贪心是正确的，可以考虑从第一段的影响证明，一定是尽量减少第二段的负担。
-
记 (k=w-k) ，把询问按照 (k) 排序，那么段数显然单调不升。
-
记 ({nxt}_i) 表示 (i) 位置在当前询问的 (k) 下合法的最远位置 (+1) ，连边 (i ightarrow {nxt}_i)。
-
考虑在 (k) 变大的时候，我们修改一些位置的 (nxt)，并使用 (lct) 加删边。如果 ({nxt}_i-i geq sqrt n) 则不再连边。
查询时如果走到了一棵树的树根便进行二分找到树根的 (nxt) ，因为二分时一定至少跳了 (sqrt n) 步，所以这样的操作不会超过 (sqrt n) 个。 -
总时间复杂度为 (O(nsqrt nlogn))。
-
感觉这种按数据根号分类的题都是平衡了两种暴力之间的复杂度
代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5 + 7;
int n,w,Q,sz;
int x[N],nxt[N],mi[N][20],mx[N][20],Log[N],ans[N];
struct qs{
int k,id;
bool operator <(const qs &rhs)const{
return k<rhs.k;
}
}q[N];
int fa[N],tr[N][2],son[N],rev[N];
#define pa fa[o]
#define Ls tr[o][0]
#define Rs tr[o][1]
bool isrt(int o){return tr[pa][0]^o&&tr[pa][1]^o;}
int side(int o){return tr[pa][1]==o;}
void pushup(int o){ son[o]=son[Ls]+son[Rs]+1; }
void rotate(int o){
int f=pa,y=fa[pa],x=side(o),s=tr[o][x^1];
if(!isrt(f)) tr[y][side(f)]=o;fa[o]=y;
tr[f][x]=s,fa[s]=f;
tr[o][x^1]=f,fa[f]=o;
pushup(f),pushup(o);
}
void splay(int o){
for(;!isrt(o);rotate(o))
if(!isrt(pa)) rotate(side(o)==side(pa)?pa:o);
}
void access(int o){
for(int y=0;o;y=o,o=pa) splay(o),Rs=y,pushup(o);
}
void link(int a,int b){
access(a),splay(a);
fa[a]=b;
}
void cut(int a,int b){
access(a),splay(a);
int x=tr[a][0];
fa[x]=tr[a][0]=0;
pushup(a);
}
int dep(int o){
access(o);splay(o);
return son[o];
}
int findr(int o){
access(o);splay(o);
while(Ls) o=Ls;
return o;
}
vector<int>G[N];
int qmx(int l,int r){
int k=Log[r-l+1];
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int qmi(int l,int r){
int k=Log[r-l+1];
return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
int main(){
n=gi(),w=gi(),Q=gi();sz=sqrt(n);
rep(i,1,n) x[i]=mi[i][0]=mx[i][0]=gi();
x[n+1]=mi[n+1][0]=mx[n+1][0]=2e9+1;
Log[1]=0; rep(i,2,n+1) Log[i]=Log[i>>1]+1;
for(int k=1;1<<k<=n+1;++k)
for(int i=1;i+(1<<k)-1<=n+1;++i){
mi[i][k]=min(mi[i][k-1],mi[i+(1<<k-1)][k-1]);
mx[i][k]=max(mx[i][k-1],mx[i+(1<<k-1)][k-1]);
}
rep(i,1,Q){
q[i].id=i,q[i].k=w-gi();
}
sort(q+1,q+1+Q);
rep(i,1,n+1) son[i]=1;
rep(i,1,n) nxt[i]=i,G[1].pb(i);
rep(i,1,Q){
for(auto p:G[i]){
if(i!=1) cut(p,nxt[p]);
int j=nxt[p]+1;
for(;j<=min(p+sz,n+1);++j) if(qmx(p,j)-qmi(p,j)>q[i].k) break;
if(j==p+sz+1) continue;
nxt[p]=j,link(p,j);
int x=lower_bound(q+1,q+1+Q,(qs){qmx(p,nxt[p])-qmi(p,nxt[p]),0})-q;
if(x!=Q+1) G[x].pb(p);
}
int &res=ans[q[i].id];
for(int j=1;j<=n+1;){
res+=dep(j),j=findr(j);
if(j==n+1) break;
int l=j+1,r=n+1;
while(l<r){
int mid=l+r>>1;
if(qmx(j,mid)-qmi(j,mid)>q[i].k) r=mid;
else l=mid+1;
}
j=l;
}
}
rep(i,1,Q) printf("%d
",ans[i]-2);
return 0;
}