Yet another xor problem

★★★★★

0 votes

Datastructures, Dynamic Programming, Algorithms, Hard

Details

Problem

You are given an array of integers, let's name it *drumroll* $A$ . You need to answer $Q$ queries of $2$ types.

The first type of query asks you to insert a number after some index in the array. It is guaranteed that this newly inserted value is greater than or equal to any value in the array at that moment. Note that this query changes the array.

In the second type query, you are given $4$ integers $l, r, p$ and $q$ . Using these integers, you would calculate $L, R, P$ and $Q$ by the code described below. Let's create another sorted array $B$ of all numbers that lie between the indices $L$ and $R$ (inclusive) of the array $A$ . For the second type query, you need to find the bitwise xor of all numbers that lie between indices $P$ and $Q$ (inclusive) of the array $B$ .

To find $L, R, P$ and $Q$ from $l, r, p$ and $q$ , you follow this process given below.

You maintain the answer to the last query of type 2 in variable ans. Note that ans is initially $0$ . Now, whenever you get a query of type $2$ ,

L = 1 + ((ans ^ l) % SIZE);
R = 1 + ((ans ^ r) % SIZE);
if(L > R) swap(L, R);
P = 1 + ((p ^ ans) % (R - L + 1));
Q = 1 + ((q ^ ans) % (R - L + 1));
if(P > Q) swap(P, Q);

Here ^ denotes the bitwise xor operator, and % denotes the modulo operator and $SIZE$ is the current size of the array.

Input:

First line of input contains $2$ integers $N$ and $Q$ , denoting the number of elements in the array $A$ and the number of queries you need to answer. Next line contains $N$ space separated integers denoting the elements of the array $A$ .

Each of the next $Q$ lines describe a query. Each query contains several space separated integers.

If it is a type $1$ query, the query contains $3$ space separated integers. The first integer is $1$ , denoting that it is a type $1$ query and next $2$ integers are $G$ and $X$ , meaning that you need to insert $X$ after the $G^{th}$ index in the array.

If it is a type $2$ query, the query contains $5$ space separated integers. The first integer is $2$ , denoting that it is a type $2$ query and next $4$ integers are $l, r, p$ and $q$ , with their meaning explained in the problem statement.