Что не так с этим кодом дерева сегментов (ленивым распространением), который я написал для блоков (вопрос о hackerearth)? - PullRequest
0 голосов
/ 13 апреля 2019

У меня проблемы с реализацией дерева сегментов с ленивым распространением. Я только что прочитал о деревьях сегментов и попытался задать простой вопрос (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 на самом деле будет истинным (это одно из условий выхода для функций обновления и запросов).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...