I've learnt the O(VE) Bipartite Matching solution but I'm not sure what the algorithm is called and how it is implemented. It is the one similar to this here, that doesn't use flows, only finding and extending augmenting paths till there is none: http://www.columbia.edu/~cs2035/courses/ieor8100.F12/lec4.pdf Could anyone share code please?

I'm solving this problem on Codechef: https://www.codechef.com/problems/PSHTTR

This problem can be solved online with persistent segment tree (can also be solved offline without persistence), but my solution is giving TLE when I implement it using pointers. Is there any reason why pointers may be significantly slower?? I get AC without pointers in 0.63s but TLE with a time limit of 1.5s.

Here is my implementation using pointers: https://www.codechef.com/viewsolution/17104558 And implementation without pointers: https://www.codechef.com/viewsolution/17104790

Here is the crux of my implementation using pointers. Its simple point updates and range xor queries:

Note: This is a dynamic persistent segment tree, i.e memory of my tree is not predefined but index of element can be in range of 1 to 1e9. I'm assigning new nodes whenever I find nullptr in left or right positions. Maybe I'm doing something wrong here, or maybe this itself is a very slow method. Any ideas how to speed this up, or is there a better method? I don't know much about pointers so please forgive me :P

struct node {
    int val;
    node *left, *right;
    node (int v, node* l, node* r) {
        val = v;
        left = l;
        right = r;
    }
};
#define null new node (0, NULL, NULL);
 
node *version[maxn];
 
void update(node *prev, node *curr, int L, int R, int idx, int val) {
    curr->val = prev->val;
    if (L == R) {
        assert(idx == L);
        curr->val ^= val;
    }
    else {
        if (prev->left == nullptr) prev->left = null;
        if (prev->right == nullptr) prev->right = null;
        int mid = (L+R)/2;
        if (idx <= mid) {
            curr->right = prev->right;
            curr->left = null;
            update(prev->left, curr->left, L, mid, idx, val);
        }
        else {
            curr->left = prev->left;
            curr->right = null;
            update(prev->right, curr->right, mid+1, R, idx, val);
        }
        curr->val = curr->left->val ^ curr->right->val;
    }
}
 
int query (node *curr, int L, int R, int li, int ri) {
    if (curr == nullptr || ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return curr->val;
    int mid = (L+R)/2;
    return query(curr->left, L, mid, li, ri) ^ query(curr->right, mid+1, R, li, ri);
}

Crux of my implementation using a buffer array, without pointers:

struct node {
    int val;
    int left, right;
    node() : val(0), left(0), right(0) {}
    node(int val) : val(val), left(0), right(0) {}
    node(int val, int l, int r) : val(val), left(l), right(r) {}
};
 
node stree[35*maxn];
int root[maxn], nodeCnt = 0;
 
void update(int old, int &curr, int L, int R, int idx, int val) {
    curr = ++nodeCnt;
    stree[curr] = stree[old];
    if (L == R) {
        assert(idx == L);
        stree[curr].val ^= val;
    }
    else {
        int mid = (L+R)/2;
        if (idx <= mid) {
            update(stree[old].left, stree[curr].left, L, mid, idx, val);
        }
        else {
            update(stree[old].right, stree[curr].right, mid+1, R, idx, val);
        }
        stree[curr].val = stree[stree[curr].left].val ^ stree[stree[curr].right].val;
    }
}
 
int query (int curr, int L, int R, int li, int ri) {
    if (curr == 0 || ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return stree[curr].val;
    int mid = (L+R)/2;
    return query(stree[curr].left, L, mid, li, ri) ^ query(stree[curr].right, mid+1, R, li, ri);
}

Help would be much appreciated!