为了方便，这里将下标均\(+1\)，并在\(0\)和\(n+1\)处建立无穷高的塔
记\(i\)左右两侧第一个\(\ge h_{i}+\delta\)的塔为\(l_{i}\)和\(r_{i}\)，则通信条件也即\(r_{i}<j\)且\(l_{j}>i\)
将条件转换到塔上，即集合\(S\)合法当且仅当\(\forall i\in S,S\cap (l_{i},r_{i})=\empty\)
（本来应该是\([l_{i},r_{i}]\)，但如果选了\(l_{i}\)或\(r_{i}\)，则对于所选塔仍不合法）
不妨假设\(h_{l_{i}}<h_{r_{i}}\)，则\((l_{i},r_{i})\)即为笛卡尔树上\(l_{i}\)右儿子的子树（反之同理）
记\(z_{i}\)为\((l_{i},r_{i})\)对应子树的根，则限制等价于\(\forall i\in S,z_{i}\)两两（不同且）不成祖先-后代关系
显然可以贪心选极深的\(z_{i}\)，即统计节点\(k\)满足\(\min_{i\in sub_{k}\cap [L,R]}h_{i}\in (h_{k}-\delta,h_{fa_{k}}-\delta]\)
-
对于\(L,R\not\in sub_{k}\)，容斥为全体\(-[l_{k}\le L]-[R\le r_{k}]+[[L,R]\subseteq sub_{k}]\)
前三类均可用主席树维护，第\(4\)类即\(lca(L,R)\)的祖先，在树上维护主席树即可
-
对于\(L\)或\(R\in sub_{k}\)，即\(L\)或\(R\)的祖先，根据单调性倍增+ST表维护即可
时间复杂度为\(O(n\log n+q\log n)\)
#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
#define mid (l+r>>1)
const int N=100005,M=20000000;
int n,rt,ans,h[N],st[N],ls[M],rs[M];
int fa[N][20],dep[N],l[N],r[N],mn[N];
int V,lg[N],ST[N][20],rtl[N],rtr[N],rtt[N],f[M];
vector<int>vl[N],vr[N];
int Cpy(int k){
ls[++V]=ls[k],rs[V]=rs[k],f[V]=f[k];
return V;
}
void update(int &k,int l,int r,int x,int y){
k=Cpy(k),f[k]+=y;
if (l==r)return;
if (x<=mid)update(ls[k],l,mid,x,y);
else update(rs[k],mid+1,r,x,y);
}
int query(int k,int l,int r,int x,int y){
if ((!k)||(l>y)||(x>r))return 0;
if ((x<=l)&&(r<=y))return f[k];
return query(ls[k],l,mid,x,y)+query(rs[k],mid+1,r,x,y);
}
int query(int l,int r){
int m=lg[r-l+1];
return min(ST[l][m],ST[r-(1<<m)+1][m]);
}
int lca(int x,int y){
if (dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--)
if (dep[fa[x][i]]>=dep[y])x=fa[x][i];
if (x==y)return x;
for(int i=19;i>=0;i--)
if (fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs(int k,int f,int s){
if (!k)return;
fa[k][0]=f,dep[k]=s;
for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1];
dfs(ls[k],k,s+1),dfs(rs[k],k,s+1);
l[k]=(ls[k] ? l[ls[k]] : k);
r[k]=(rs[k] ? r[rs[k]] : k);
mn[k]=min(min(mn[ls[k]],mn[rs[k]]),h[k]);
vl[l[k]].push_back(k),vr[r[k]].push_back(k);
}
void Dfs(int k){
if (!k)return;
rtt[k]=rtt[fa[k][0]];
update(rtt[k],1,1e9,h[k]-mn[k]+1,1);
if (k!=rt)update(rtt[k],1,1e9,h[fa[k][0]]-mn[k]+1,-1);
Dfs(ls[k]),Dfs(rs[k]);
}
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++){
int lst=0;
while ((st[0])&&(h[st[st[0]]]<h[i])){
rs[st[st[0]]]=lst;
lst=st[st[0]--];
}
ls[i]=lst,st[++st[0]]=i;
}
int lst=0;
while (st[0]){
rs[st[st[0]]]=lst;
lst=st[st[0]--];
}
rt=lst,mn[0]=1e9,dfs(rt,0,1);
lg[0]=-1;
for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=n;i;i--){
ST[i][0]=h[i];
for(int j=1;j<20;j++)ST[i][j]=min(ST[i][j-1],ST[min(i+(1<<j-1),n)][j-1]);
}
V=n;
for(int i=1;i<=n;i++){
rtl[i]=rtl[i-1],rtr[i]=rtr[i-1];
for(int j:vl[i]){
update(rtl[i],1,1e9,h[j]-mn[j]+1,1);
if (j!=rt)update(rtl[i],1,1e9,h[fa[j][0]]-mn[j]+1,-1);
}
for(int j:vr[i]){
update(rtr[i],1,1e9,h[j]-mn[j]+1,1);
if (j!=rt)update(rtr[i],1,1e9,h[fa[j][0]]-mn[j]+1,-1);
}
}
Dfs(rt);
}
int max_towers(int L,int R,int D){
L++,R++;
int k=lca(L,R);
if (h[k]-D<query(L,R))return 1;
ans=query(rtr[R-1],1,1e9,1,D)-query(rtl[L],1,1e9,1,D)+query(rtt[k],1,1e9,1,D);
if (h[L]-D<query(L,r[L])){
k=L;
for(int i=19;i>=0;i--)
if ((fa[k][i])&&(h[fa[k][i]]-D<query(L,r[fa[k][i]])))k=fa[k][i];
if (query(L,r[k])<=h[fa[k][0]]-D)ans++;
}
if (h[R]-D<query(l[R],R)){
k=R;
for(int i=19;i>=0;i--)
if ((fa[k][i])&&(h[fa[k][i]]-D<query(l[fa[k][i]],R)))k=fa[k][i];
if (query(l[k],R)<=h[fa[k][0]]-D)ans++;
}
return ans;
}