FastPrep

Description

Solutions

Salvage Humankind

📚RELATED PROBLEMS

Cooper is stuck in the 5th dimension with TARS. They have to find a way to transmit gravitational data to Murph so that she can solve Dr. Brand's equation to harness gravity. The higher dimensional beings agreed to help them out, but only if they are able to solve a task for them.

Cooper and TARS are presented with n rocks. Each rock has a mass attached to it (m1, m2, m3, m4, . . . mn). They can perform two types of operations on this ordered set of rocks:

Given two indexes x and y, find the total mass of the rocks with indices in the range x to y, i.e, m_x + m_x+1 + ... + m_y and print it.
They are also presented with a machine capable of altering the mass of any rock. Presented again with two indexes x and y, and a number z, alter the masses of the rocks with indices in the range x to y such that m_i (x <= i <= y) gets altered to m_i ^ z, where ^ is the xor operation.

They have been asked to perform ops number of operations, where each operation can either be of the type 1 or 2.

Input Format and Constraints

An integer n, denoting the number of rocks. 1 ≤ n ≤ 10^5.
The second line contains n integers denoting the initial masses of the rocks. 0 ≤ m[i] ≤ 10^6.
The third line contains the number of operations, ops, to be performed on the rocks. 1 ≤ ops ≤ 5*10^4.
The above is followed by ops number of lines, where each line consists of:
- An integer type, which is either 1 or 2, denoting the operation performed.
- If type is 1, it is followed by two integers, s and e, denoting the range for which total mass is to be calculated. 1 ≤ s ≤ e ≤ n.
- If type is 2, it is followed by three integers, s, e, and z. z is the number using which the mass of the rocks in the range s to e is to be altered using ^ which is the xor operation. 1 ≤ s ≤ e ≤ n and 1 ≤ z ≤ 10^6. The changes made in this query persist for all future operations as well.

Example 1:

Input:  n = 4, masses = [1, 5, 2, 4], ops = 3, queries = [[1, 1, 4], [2, 2, 3, 4], [1, 1, 4]]
Output: [12, 12] 
Explanation:
      
        - In the first query of type 1, the sum of masses of rocks in the range 1 to 4 is asked for, hence 12 is printed.
        - In the second query of type 2, the masses of rocks in the range 2 to 3 is modified by performing xor with 4.
          The new array becomes -> 1 1 6 4.
        - In the third query of type 1, the masses of rocks in the range 1 to 4 is asked for, hence, 12 is printed.

Example 2:

Input:  n = 5, masses = [10, 6, 1, 9, 2], ops = 3, queries = [[1, 1, 5], [2, 1, 3, 8], [1, 2, 4]]
Output: [28, 32] 
Explanation:
      
        - In the first query of type 1, the sum of masses of rocks in the range 1 to 5 is asked for, hence 28 is printed.
        - In the second query of type 2, the masses of rocks in the range 1 to 3 is modified by performing xor with 8.
          The new array becomes -> 2 14 9 9 2.
        - In the third query of type 1, the masses of rocks in the range 2 to 4 is asked for, hence, 32 is printed.

Constraints: