想到将最优化问题转化为数点问题的一步了，但是因为转化的姿势不太好导致我的数点不太能用特别简洁的数据结构维护，最后只好看题解（
考虑先解决单组询问的问题，对于每个点 \(i\)，我们找出它左边最近的 \(h_l\le h_i-D\) 的点 \(l\)，和它右边最近的 \(h_r\le h_i-D\) 的点 \(r\)，然后新建一条 \([l,r]\) 的线段，那么问题转化为最多能选出的线段条数，使得线段间两两的交不超过 \(1\)，再加一。
直接求好像不太能解决 \(D\) 多组询问的问题，因为 \(D\) 一变线段也会变，而线段一变你不论用什么数据结构维护，都需要进行大幅度的修改，这是不好的。因此考虑发掘些性质，容易得到：
-
任意两个线段要么包含，要么交不超过 \(1\)。
这个性质告诉我们，最优线段集合的大小就是不包含任何其他线段的线段个数。
-
对于两个满足 \(h_i>h_j\) 的 \(i,j\)，不会出现 \(j\) 对应的线段完全包含于 \(i\) 对应的线段的情况。
有了这个性质，我们可以得出 \(i\) 对应的线段不会包含其他任何线段的充要条件：\(i\) 对应的线段中不存在任何一个 \(h\) 比它大的点。
这样思路就出来了，先预处理出 \(w_i\) 表示 \(D\) 的最大值使得 \(i\) 对应的线段能够被纳入答案，然后用主席树维护 \(D\) 时候区间内的答案，查询就在主席树上进行区间查询即可。然后有一个小问题就是有可能一个点虽然它在区间内，但是它对应的所有合法都要用覆盖到区间外的点，但是因为性质一的存在，这样的点只可能是最左边的合法点或者最右边的合法点，主席树二分找到它们即可。
时间复杂度 \(n\log n\)。
const int MAXN=1e5;
const int LOG_N=18;
const int INF=0x3f3f3f3f;
const int MAXP=MAXN<<6;
int n,h[MAXN+5],nd[MAXN+5],pre[MAXN+5],nxt[MAXN+5],stk[MAXN+5],tp;
int st[LOG_N+2][MAXN+5],lg[MAXN+5],w[MAXN+5],key[MAXN+5],uni[MAXN+5],num;
vector<int>vec[MAXN+5];
int query_mn(int l,int r){
if(l>r)return INF;int k=lg[r-l+1];
return min(st[k][l],st[k][r-(1<<k)+1]);
}
struct node{int ch[2],sum;}s[MAXP+5];
int rt[MAXN+5],ncnt;
void build(int &k,int l,int r){
k=++ncnt;if(l==r)return;int mid=l+r>>1;
build(s[k].ch[0],l,mid);build(s[k].ch[1],mid+1,r);
}
int modify(int k,int l,int r,int x){
int z=++ncnt;s[z]=s[k];s[z].sum++;
if(l==r)return z;int mid=l+r>>1;
if(x<=mid)s[z].ch[0]=modify(s[k].ch[0],l,mid,x);
else s[z].ch[1]=modify(s[k].ch[1],mid+1,r,x);
return z;
}
int query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return s[k].sum;int mid=l+r>>1;
if(qr<=mid)return query(s[k].ch[0],l,mid,ql,qr);
else if(ql>mid)return query(s[k].ch[1],mid+1,r,ql,qr);
else return query(s[k].ch[0],l,mid,ql,mid)+query(s[k].ch[1],mid+1,r,mid+1,qr);
}
int find_nxt(int k,int l,int r,int p){
if(!s[k].sum)return 0;if(l==r)return l;
int mid=l+r>>1;
if(p>mid)return find_nxt(s[k].ch[1],mid+1,r,p);
else{
int res=find_nxt(s[k].ch[0],l,mid,p);
if(res)return res;
else return find_nxt(s[k].ch[1],mid+1,r,p);
}
}
int find_pre(int k,int l,int r,int p){
if(!s[k].sum)return 0;if(l==r)return l;
int mid=l+r>>1;
if(p<=mid)return find_pre(s[k].ch[0],l,mid,p);
else{
int res=find_pre(s[k].ch[1],mid+1,r,p);
if(res)return res;
else return find_pre(s[k].ch[0],l,mid,p);
}
}
void init(int N,vector<int>H){
n=N;for(int i=0;i<N;i++)h[i+1]=H[i];
for(int i=1;i<=n;i++){
while(tp&&h[stk[tp]]<h[i])--tp;
pre[i]=stk[tp];stk[++tp]=i;
}stk[tp=0]=n+1;
for(int i=n;i;i--){
while(tp&&h[stk[tp]]<h[i])--tp;
nxt[i]=stk[tp];stk[++tp]=i;
}
for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)st[0][i]=h[i];
for(int i=1;i<=LOG_N;i++)for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=1;i<=n;i++)w[i]=h[i]-max(query_mn(pre[i]+1,i-1),query_mn(i+1,nxt[i]-1));
for(int i=1;i<=n;i++)key[i]=w[i];sort(key+1,key+n+1);key[0]=-INF;
for(int i=1;i<=n;i++)if(key[i]!=key[i-1])uni[++num]=key[i];
for(int i=1;i<=n;i++){
int pos=lower_bound(uni+1,uni+num+1,w[i])-uni;
vec[pos].pb(i);
}
build(rt[num+1],1,n);
for(int i=num;i;i--){
rt[i]=rt[i+1];
for(int id:vec[i])rt[i]=modify(rt[i],1,n,id);
}
}
bool check(int l,int r,int x,int D){return h[x]-max(query_mn(max(pre[x]+1,l),x-1),query_mn(x+1,min(nxt[x]-1,r)))>=D;}
int max_towers(int l,int r,int x){
++l;++r;int p=lower_bound(uni+1,uni+num+1,x)-uni,cnt=query(rt[p],1,n,l,r);
if(!cnt)return 1;int L=find_nxt(rt[p],1,n,l),R=find_pre(rt[p],1,n,r);
return cnt-(!check(l,r,L,x))-(L!=R&&!check(l,r,R,x))+1;
}