#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mxN=2e5+5;
const ll inf=1e18;
ll h[mxN];
ll a[mxN];
ll b[mxN];
ll n, q;
vll add[mxN];
vll minu[mxN];
struct segtree{
vll tree;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcountll(treelen)!=1){
treelen++;
}
tree=vll(2*treelen, 0);
}
void update(ll idx, ll val){
ll tar=treelen+idx;
tree[tar]=val;
tar/=2;
while(tar>0){
tree[tar]=max(tree[2*tar], tree[2*tar+1]);
tar/=2;
}
}
ll getmax(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return 0;
}
ll mid=(low+high)/2;
return max(getmax(2*idx, low, mid, qlow, qhigh),
getmax(2*idx+1, mid+1, high, qlow, qhigh));
}
};
struct segtree2{
vll tree;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcountll(treelen)!=1){
treelen++;
}
tree=vll(2*treelen, inf);
}
void update(ll idx, ll val){
ll tar=treelen+idx;
tree[tar]=val;
tar/=2;
while(tar>0){
tree[tar]=min(tree[2*tar], tree[2*tar+1]);
tar/=2;
}
}
ll getmin(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return inf;
}
ll mid=(low+high)/2;
return min(getmin(2*idx, low, mid, qlow, qhigh),
getmin(2*idx+1, mid+1, high, qlow, qhigh));
}
};
segtree seg1;
segtree2 seg2;
ll solve2(ll l, ll r){
seg1=vll(2*seg.treelen, 0);
seg2=vll(2*seg.treelen, inf);
/*for(auto it:seg2.tree){
cout<<it<<' ';
}
cout<<'\n';*/
for(ll i=l;i<=r;i++){
add[i].clear();
minu[i].clear();
}
ll re=-1;
for(ll i=l;i<=r;i++){
for(auto it:add[i]){
seg1.update(it, h[it]);
seg2.update(it, h[it]);
}
for(auto it:minu[i]){
seg1.update(it, 0);
seg2.update(it, inf);
}
if(i+a[i]<=r){
add[i+a[i]].pb(i);
}
if(i+b[i]+1<=r){
minu[i+b[i]+1].pb(i);
}
ll low=i-b[i], high=i-a[i];
low=max(low, l);
//cout<<i<<' '<<low<<' '<<high<<'\n';
if(high<low) continue;
ll mn=seg2.getmin(1, 0, seg2.treelen-1, low, high);
//cout<<mn<<'\n';
if(mn!=inf){
re=max(re, abs(h[i]-mn));
}
ll mx=seg1.getmax(1, 0, seg1.treelen-1, low, high);
//cout<<mx<<'\n';
if(mx!=0){
re=max(re, abs(h[i]-mx));
}
}
return re;
}
void solve(){
cin>>n;
for(ll i=0;i<n;i++){
cin>>h[i]>>a[i]>>b[i];
}
cin>>q;
for(ll i=0;i<q;i++){
ll l, r;
cin>>l>>r;
l--; r--;
cout<<solve2(l, r);
if(i<q-1) cout<<'\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
antennas.cpp: In function 'll solve2(ll, ll)':
antennas.cpp:95:16: error: 'seg' was not declared in this scope; did you mean 'seg2'?
95 | seg1=vll(2*seg.treelen, 0);
| ^~~
| seg2
