Making a implicit segtree that actually gets AC

[GaurangTandon]

Reference code: https://codeforces.com/contest/915/submission/35567497 Pros: doesn't get memory and time limit. See my submissions on problem E :sadface:

[GaurangTandon]

#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl "\n"
#endif
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

template <typename Type>
class ImplicitSegtree {
    struct Node {
        Type data = 0, lazy = 0;
        int lc = 0, rc = 0;
        inline void setup() {
            if (not lc) {
                lc = allocNode();
                rc = allocNode();
            }
        }
        inline int l_child() {
            setup();
            return lc;
        }
        inline int r_child() {
            setup();
            return rc;
        }
    };

    constexpr static int ROOT_IDX = 0;
    struct Node nodes[int(1.5e7)];
    static int nodes_used;
    static int allocNode() {
        return nodes_used++;
    }
    int size;
    Type _default;

    inline Type _setter(Type x, Type y) {
        return y;
    }

    inline Type _operation(Type x, Type y) { 
        return x + y;
    }

    void split(Node *node) {
        node->l_child()->lazy = _setter(node->l_child()->lazy, node->lazy);
        node->r_child()->lazy = _setter(node->r_child()->lazy, node->lazy);
        node->l_child()->data = _setter(node->l_child()->data, node->lazy);
        node->r_child()->data = _setter(node->r_child()->data, node->lazy);
        node->lazy = _default;
    }
    void merge(Node *node) {
        node->data = _operation(node->l_child()->data, node->r_child()->data);
    }

   public:
    Node *root;

    ImplicitSegtree(int n, const Type identity) {
        size = n;
        _default = identity;
        root = &nodes[allocNode()];
    }

    void modify(int l, int r, Type delta, int node_idx = ROOT_IDX, int x = 0,
                int y = -1) {
        Node* node = nodes + node_idx;
        if (node == nullptr)
            node = root, y = size;
        if (r <= x || l >= y)
            return;
        if (l <= x && y <= r) {
            node->lazy = _setter(node->lazy, delta);
            node->data = _setter(node->data, delta);
            return;
        }
        split(node);
        modify(l, r, delta, node->l_child(), x, (x + y) / 2);
        modify(l, r, delta, node->r_child(), (x + y) / 2, y);
        merge(node);
    }
    Type query(int l, int r, int node_idx = ROOT_IDX, int x = 0, int y = -1) {
        Node* node = nodes + node_idx;

        if (node == nullptr)
            node = root, y = size;
        if (r <= x || l >= y)
            return _default;
        if (l <= x && y <= r) {
            return node->data;
        }
        split(node);
        Type lres = query(l, r, node->l_child(), x, (x + y) / 2);
        Type rres = query(l, r, node->r_child(), (x + y) / 2, y);
        merge(node);
        return _operation(lres, rres);
    }
};

void solve() {
    int n, q; cin >> n >> q;

    ImplicitSegtree<int> is(n, 0);
    is.modify(1, n + 1, 1);

    while (q--) {
        int l, r, k; cin >> l >> r >> k;

        is.modify(l, r + 1, k == 2);
        cout << is.root->data << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // int t;cin >> t;while(t--)
    solve();
    return 0;
}

I tried to fit in the approach into your code but it's not working out. Getting a stupid C++ compile time error. See if you can resolve it. Much thanks.

The two changes are:

1. Fitting all nodes into a node array and not passing around pointers in structs, as pointers take a lot more memory.
2. Making separate inline able functions for _operation and _setter as otherwise they're slower.