RT

根号分治，二分，没有用题解里LCT的做法。问问是不是假掉了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=1e5+5;
int n,w,T,a[MAX];
struct Q{
	int l,pos;
}q[MAX]; 
inline int cmp(Q A,Q B){return A.l<B.l;}
inline int abs(int x){return x<0?-x:x;}
inline int sol(int k){
	register int ret=1,mxa=a[1],mni=-1; 
	for(register int t,i=2;i<=n;++i){
		if(mni==-1){
			if(abs(a[i]-mxa)>k)++ret,mxa=a[i],mni=-1;
			else {
				t=mxa;
				mxa=max(a[i],t);
				mni=min(a[i],t); 
			}
		}else {
			if(a[i]>mxa)
				if(a[i]-mni>k)++ret,mxa=a[i],mni=-1;
				else mxa=a[i];
			if(a[i]<mni)
				if(mxa-a[i]>k)++ret,mxa=a[i],mni=-1;
				else mni=a[i];
		}
	}
	return ret-1;
}
int ans[MAX];
signed main(){
	n=read(),w=read(),T=read();
	for(register int i=1;i<=n;++i)a[i]=read();
	for(register int i=1;i<=T;++i)q[i]=(Q){w-read(),i};		
	sort(q+1,q+1+T,cmp);
	int P=sqrt(q[T].l*log2(q[T].l));
	for(register int i=1;i<=T;){
		if(q[i].l<=P){
			ans[q[i].pos]=sol(q[i].l);++i;
			continue;
		}
		register int tmp=sol(q[i].l),l=q[i].l,r=q[T].l,u=0,mid=0;
		while(l<=r){
			mid=l+r>>1;
			if(sol(mid)<=tmp)u=mid,l=mid+1;
			else r=mid-1;
		}
		for(;q[i].l<=u&&i<=T;++i)ans[q[i].pos]=tmp;
	}
	for(register int i=1;i<=T;++i)printf("%d\n",ans[i]);
	return 0;
}