Getting TLE on the BIT while calculating the [L R] xor of elements

help
, , , ,
21

No Bro , Not possible via BIT for sure bcz u r doing range update + range query , very very few questions can be done with this type bro , u have to learn segment tree .

and also Let me read your code once more , btw how many test cases your code passes ?

1 Like
22

So this could be solved via segment tree?

1 Like
23

Yes , but i have weak segment tree , so no comment on that.

how many TC ? passes ?

1 Like
24

also , in that question can we access solution / editorial / hint ? if this is the case then please open and check (if u think u r unable to solve)

1 Like
25

Codechef was limited my messaging count, so couldn’t replay till now, sorry about that bro.
There were only two test cases. One is passing, and the second one gives TLE.
This problem has no editorial.

26

but seems, segtree is the way to go, thanks for that hint.

27

I’ve implemented a segment tree-based solution, but still, one test case gives TLE.
How this can be optimized?

#include <iostream>
#include <vector>

using namespace std;

#define MAX_SIZE 200000

int tree[4 * MAX_SIZE];  

void update_xor(int v, int val, int start, int end, int l, int r) {
    if(end < l || start > r || start > end) {
        return;
    }
    if(start == end) {
        tree[v] ^= val;
    } else {
        int m = start + (end - start) / 2;
        update_xor(2 * v, val, start, m, l, r);
        update_xor(2 * v + 1, val, m + 1, end, l, r);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

void update_and(int v, int val, int start, int end, int l, int r) {
    if(end < l || start > r || start > end) {
        return;
    }
    if(start == end) {
        tree[v] &= val;
        return;
    } else {
        int m = start + (end - start) / 2;
        update_and(2 * v, val, start, m, l, r);
        update_and(2 * v + 1, val, m + 1, end, l, r);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

void update_or(int v, int val, int start, int end, int l, int r) {
    if(end < l || start > r || start > end) {
        return;
    }
    if(start == end) {
        tree[v] |= val;
        return;
    } else {
        int m = start + (end - start) / 2;
        update_or(2 * v, val, start, m, l, r);
        update_or(2 * v + 1, val, m + 1, end, l, r);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

int query(int v, int start, int end, int l, int r) {
    if(l > r) {
        return 0;
    }
    if(start == l && end == r) {
        return tree[v];
    }
    int m = start + (end - start) / 2;
    return query(2 * v, start, m, l, min(r, m)) + query(2 * v + 1, m + 1, end, max(m + 1, l), r);
}

void query_xor(int v, int& _xor, int start, int end, int l, int r) {
    if(end < l || start > r || start > end) {
        return;
    }
    if(start == end) {
        _xor ^= tree[v];
        return;
    } else {
        int m = start + (end - start) / 2;
        query_xor(2 * v, _xor, start, m, l, r);
        query_xor(2 * v + 1, _xor, m + 1, end, l, r);
    }
}

int main() {
	int n = 0;
	cin >> n;
	int q = 0;
	cin >> q;      	
	while(q--) {
		int type = 0;
		cin >> type;
		if(type == 5) {
			int l = 0;
			cin >> l;
			int r = 0;
			cin >> r;			
    		int _xor = 0;	
			query_xor(1, _xor, 1, n, l, r);		
			cout << _xor << "\n";
		} else if(type == 4) {
			int l = 0;
			cin >> l;
			int r = 0;
			cin >> r;    		
			int ans = query(1, 1, n, l, r);
			cout << ans << "\n";			
		} else if(type == 1) {
			int l = 0;
			cin >> l;
			int r = 0;
			cin >> r;
			int val = 0;
			cin >> val;			
			update_or(1, val, 1, n, l, r);  				
		} else if(type == 2) {
			int l = 0;
			cin >> l;
			int r = 0;
			cin >> r;
			int val = 0;
			cin >> val;			
			update_and(1, val, 1, n, l, r);		    		
		} else if(type == 3) {
			int l = 0;
			cin >> l;
			int r = 0;
			cin >> r;
			int val = 0;
			cin >> val;
			update_xor(1, val, 1, n, l, r);			
		}
	}
	return 0;
}