Link
先把询问离线，从小到大枚举(r)，求出所有右端点在(r)的左端点在(l)的询问的答案。
维护数组({a_n})，(a_i)表示((i,r])内的可以与天线(i)互发消息的最大成本，如果不存在那么(a_i=-infty)。
维护数组({b_n})，(b_i)表示天线(i)是否可以向天线(r)发消息。
那么对于当前询问([l,r])，答案为(maxlimits_{i=l}^ra_i)。
考虑用线段树维护({a_n})的区间最大值。
当我们将右端点从(r-1)扩展至(r)时，首先我们需要将(B_i+i=r-1)的(b_i)设为(0)，这种操作总共只有(O(n))种。
然后我们需要对所有(iin[r-B_r,r-A_r])，(a_ileftarrowmax(a_i,b_i|h_r-h_i|))。
绝对值是不好处理的，因此我们只需要先将其视为(h_i-h_r)跑一遍，再将所有(h)取反之后再跑一遍即可。
维护数组({c_n})，(c_i)表示((i,r])内的可以与天线(i)互发消息的最小(h)，若不存在则(c_i=+infty)，那么(a_i=h_i-c_i)。
线段树维护即可。
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using pi=std::pair<int,int>;
const int N=200007,inf=1e9;
char ibuf[1<<23|1],*iS=ibuf;int n,q,a[N],b[N],h[N],ans[N],c[4*N],d[4*N],tag[4*N];
std::vector<pi>opt[N],qry[N];
int read(){int x=0;while(isspace(*iS))++iS;while(isdigit(*iS))(x*=10)+=*iS++&15;return x;}
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)/2)
void pushup(int p){c[p]=std::max(c[ls],c[rs]),d[p]=std::max(d[ls],d[rs]);}
void modify(int p,int x){tag[p]=std::max(tag[p],x),d[p]=std::max(d[p],c[p]+x);}
void pushdown(int p){if(tag[p]!=-inf)modify(ls,tag[p]),modify(rs,tag[p]),tag[p]=-inf;}
void build(int p,int l,int r)
{
tag[p]=c[p]=d[p]=-inf;if(l==r) return ;
build(ls,l,mid),build(rs,mid+1,r);
}
void update(int p,int l,int r,int x,int v)
{
if(l==r) return tag[p]=-inf,c[p]=v,void();
pushdown(p),x<=mid? update(ls,l,mid,x,v):update(rs,mid+1,r,x,v),pushup(p);
}
void update(int p,int l,int r,int L,int R,int x)
{
if(r<L||R<l||R<L) return ;
if(L<=l&&r<=R) return modify(p,x);
pushdown(p),update(ls,l,mid,L,R,x),update(rs,mid+1,r,L,R,x),pushup(p);
}
int query(int p,int l,int r,int L,int R)
{
if(r<L||R<l||R<L) return -inf;
if(L<=l&&r<=R) return d[p];
return pushdown(p),std::max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
#undef ls
#undef rs
#undef mid
void work()
{
build(1,1,n);
for(int i=1;i<=n;++i)
{
for(auto[id,o]:opt[i]) update(1,1,n,id,~o? h[id]:-inf);
if(i>a[i]) update(1,1,n,std::max(i-b[i],1),i-a[i],-h[i]);
for(auto[id,l]:qry[i]) ans[id]=std::max(ans[id],query(1,1,n,l,i));
}
}
int main()
{
fread(ibuf,1,1<<23,stdin);
n=read();
for(int i=1;i<=n;++i)
{
h[i]=read(),a[i]=read(),b[i]=read();
if(i+a[i]<=n) opt[i+a[i]].emplace_back(i,1);
if(i+b[i]+1<=n) opt[i+b[i]+1].emplace_back(i,-1);
}
q=read(),memset(ans+1,-1,4*q);
for(int i=1,l;i<=q;++i) l=read(),qry[read()].emplace_back(i,l);
work();
for(int i=1;i<=n;++i) h[i]=1000000000-h[i];
work();
for(int i=1;i<=q;++i) printf("%d
",ans[i]);
}