У меня проблемы с реализацией дерева сегментов с ленивым распространением. Я только что прочитал о деревьях сегментов и попытался задать простой вопрос (https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/blocks-2/description/), и получаю неправильный ответ.
Пожалуйста, помогите мне с реализацией. Мой код почти полностью похож на тот, который приведен в редакционной статье, поскольку я использовал его в качестве справочного материала при изучении того, как применять деревья сегментов к задачам. Я не могу найти каких-либо серьезных изменений между моим кодом и редакционным кодом, которые могли бы повлиять на вывод. Пожалуйста, скажите мне, где я иду не так.
#include<bits/stdc++.h>
#define mid (lo+(hi-lo)/2)
#define left (2*tidx+1)
#define right (2*tidx+2)
using namespace std;
typedef long long ll;
const ll sz=1e5;
ll st[3*sz]; //segment tree array
ll lazy[3*sz];
void clear_lazy(ll tidx)
{
st[tidx]=lazy[tidx];
lazy[left]=lazy[right]=lazy[tidx];
lazy[tidx]=0;
}
void update(ll tidx, ll lo, ll hi, ll l, ll r, ll val)
{
if(lazy[tidx]) //lo-hi represent segments; l-r represent update range
clear_lazy(tidx); //tidx represents segmentTreeIndex
if(lo>hi || hi<l || lo>r)
return;
if(l<=lo && hi<=r){
st[tidx]=val;
lazy[left]=lazy[right]=val;
return;
}
update(left,lo,mid,l,r,val);
update(right,mid+1,hi,l,r,val);
st[tidx]=max(st[left],st[right]);
return;
}
ll query(ll tidx, ll lo, ll hi, ll l, ll r)
{
if(lazy[tidx])
clear_lazy(tidx);
if(lo>hi || hi<l || lo>r)
return 0;
if(l<=lo && hi<=r)
return st[tidx];
ll q1=query(left,lo,mid,l,r);
ll q2=query(right,mid+1,hi,l,r);
return(max(q1,q2));
}
int main()
{
ll n,l,h,p,c,x;
cin>>n;
while(n--)
{
cin>>l>>h>>p>>c>>x;
ll mx=query(0,0,sz-1,x,x+l-1);
if(c){
update(0,0,sz-1,x,x+l-1,mx+1);
update(0,0,sz-1,x+p-1,x+p-1,mx+h+1);
}
else{
ll qp=query(0,0,sz-1,x+p-1,x+p-1);
if(mx-qp>=h) update(0,0,sz-1,x,x+l-1,mx+1);
else
update(0,0,sz-1,x,x+l-1,qp+h+1);
}
}
cout<<st[0]<<endl;
return 0;
}
Также я не понимаю, где lo> hi на самом деле будет истинным (это одно из условий выхода для функций обновления и запросов).