Segment Tree

Bitmasks are cool. A bitmask is a string of binary bits (0s and 1s). For example: “01010” is a bitmask. Kuldeep is a naughty but brilliant computer scientist. In his free time, he writes some random programs to play with bitmasks. He has a PhD student under him and to test him (and entertain himself), he has given him the following task: Given a number N, write a bitmask of length N containing all 0s. Now, you are given Q operations. Each operation contains two numbers (l, r) as input. An operation can be one of the following:
Update operation: Take the XOR of all the bits in the bitmask from index l to r (both inclusive) with 1.
Query operation: Count the number of set bits in the bitmask between index l to r (both inclusive).You need to find the sum of all the queries. Note:

  1. In case there are no queries, return 0.
  2. As the answer can be large, output the answer mod 1000000007
  3. Consider 0 based indexing
    1 <= N <= 100000
    1 <= Q <= 100000
    0 <= l, r < N
    Input format:
    int A: Number N as described above
    vector<vector > B: Q operations as described above.
    Each row contains three numbers (type, l, r). If type is 0, its an update operation else a query operation.
    N = 5
    Operations: [[0, 1, 3], [1, 1, 2], [0, 0, 4], [1, 3, 4]]


Initial mask: 00000
Operation 1: Update (1,3) , Resulting mask = 01110
Operation 2: Query (1,2), Answer to query = 2
Operation 3: Update (0, 4), Resulting mask = 00001
Operation 4: Query (3,4), Answer to query = 1

Sum of all the queries = 2+1 = 3
Answer = 3%1000000007 = 3
You need to find the sum of all the queries.

Can anyone solve this problem.

This question can be solved using segment tree with lazy propagation.
I found a similar problem here. (solution)

1 Like