Muraglia (Segment Tree)

Aiuto
1

Buongiorno, sto provando a risolvere il problema Muraglia e ho letto un po di informazioni sui segment tree ma credo di non averli capiti molto bene, al momento il mio codice con i 2 casi di esempio sembra dare i valori esatti per la fortezza a sinistra di x ma non per quella a destra. Qualcuno sarebbe in grado di aiutarmi a trovare il problema?

Ecco il mio codice che ho fatto fino ad ora

class SegmentTree {
public:
    int N;
    std::vector<int> tree;

    SegmentTree(const std::vector<int>& A) {
        N = A.size();
        tree.resize(N * 4);

        build(1, 0, N, A);
    }

    int build(int i, int left, int right, const std::vector<int>& A) {
        if (right - left == 1) {
            tree[i] = A[left];
            return tree[i];
        }

        int mid = (left + right) / 2;

        tree[i] = std::max(build(2 * i, left, mid, A), build(2 * i + 1, mid, right, A));
        return tree[i];
    }

    void update(int i, int left, int right, int posToUpdate, int val) {
        if (right - left == 1) {
            tree[i] = val;
            return;
        }

        int mid = (left + right) / 2;

        if (posToUpdate < mid) {
            update(2 * i, left, mid, posToUpdate, val);
        }
        // posToUpdate >= mid
        else {
            update(2 * i + 1, mid, right, posToUpdate, val);
        }
            
        tree[i] = std::max(tree[2 * i], tree[2 * i + 1]);
    }

    void update(int pos, int val) {
        update(1, 0, N, pos, val);
    }

    int get_destra(int i, int tl, int tr, int l, int r, int val) {
        if (tl > r || tr < l) return -1;
        if (tree[i] <= val) return -1;

        if (tr - tl == 1) return tl;

        int tm = tl + (tr - tl) / 2;
        int left = get_destra(2 * i, tl, tm, l, r, val);
        if (left != -1) return left;
        return get_destra(2 * i + 1, tm + 1, tr, l, r, val);
    }

    int get_destra(int pos, int val)
    {
        return get_destra(1, 0, N, pos, N, val);
    }

    int get_sinitra(int i, int tl, int tr, int l, int r, int val) {
        if (tl > r || tr < l) return -1;
        if (tree[i] <= val) return -1;

        if (tr - tl == 1) return tl;

        int tm = tl + (tr - tl) / 2;
        int right = get_sinitra(2 * i + 1, tm + 1, tr, l, r, val);
        if (right != -1) return right;
        return get_sinitra(2 * i, tl, tm, l, r, val);
    }

    int get_sinitra(int pos, int val)
    {
        return get_sinitra(1, 0, N, 0, pos, val);
    }
};

SegmentTree* tree;
std::vector<int> bastionH;

void inizializza(int N, std::vector<int> H) {
    tree = new SegmentTree(H);
    bastionH = H;
    return;
}

void cambia(int x, int h) {
    tree->update(x, h);
    bastionH[x] = h;
    return;
}

std::pair<int, int> chiedi(int x) {
    int curH = bastionH[x];

    int s = tree->get_sinitra(x, curH);
    int d = tree->get_destra(x, curH);

    if (s == -1) s = 0;
    if (d == -1) d = bastionH.size() - 1;

    return std::make_pair(s, d);
}