Array queries | Practice Problems

Array queries

★★★★★

2 votes

XOR, Implementation, Linear Algebra, Lazy Propagation in Interval/Segment Trees, C++, Combinatorics, Gaussian Elimination, Math

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ consisting of $N$ positive integers. You are also given $Q$ queries of the following type:

$\text{1 L R X}$ : Perform $A[i] = X$ for all $L \leq i \leq R$
$\text{2 L R K}$ : Consider the numbers in the range $[L..R]$ (inclusive). Find the bitwise XOR of all possible non-empty subsets (individually) of these numbers and insert them in a set $S$ (equivalently remove duplicates). Also, remove the element $0$ from $S$ if it is present. Next, consider all subsets of $S$ of size at most $K$ and calculate the sum of numbers overall these subsets. The sum can be very large, output it modulo $1000000007$ $(10^9 + 7)$ .

You are given $T$ test cases.

Warning: Use fast I/O Methods.

Input format

The first line contains a single integer $T$ denoting the number of test cases.
For each test case:
- The first line contains a single integer $N$ denoting the length of the array.
- The second line contains $N$ space-separated integers denoting the integer array $A$ .
- The third line contains an integer $Q$ denoting the number of queries.
- $Q$ lines follow. Each line is a query of the type $\text{1 L R X}$ or $\text{2 L R K}$ .

Output format

For each test case (in a separate line), print the answers corresponding to the queries $\text{2 L R K}$ in a single line.

Constraints

$1 \le T \le 1000 \\ 1 \le N \le 4 \times 10^5 \\ 1 \le A_i < 2^{20} \\ 1 \le Q \le 10^5 \\ 1 \le L \le R \le N \\ 1\le X < 2^{20} \\ 1 \le K \le 10^9 \\ \text{Sum of N over all test cases does not exceed } 4 \times 10^5 \\ \text{Sum of Q over all test cases does not exceed } 10^5 \\ \text{There is atleast one query of the type 2 L R K in each test case}$

Time Limit: 6

Memory Limit: 512

Source Limit:

Explanation

In the first test case, we have $N = 4, A = [4, 2, 3, 1], Q = 3$ . Let's look at the queries:

2 1 2 1 :
- Consider numbers in range $[1, 2]$ , they are $\{4, 2\}$ .
- All non empty subsets of these numbers are $\{4\}, \{2\}, \{4, 2\}$ .
- Bitwise XOR of all these subsets(individually) are $4, 2, 6$ . Therefore, $S = \{4, 2, 6\}$ .
- We have $K = 1$ . All non-empty subsets of $S$ of size atmost $K = 1$ are $\{4\}, \{2\}, \{6\}$ and their sum is $4 + 2 + 6 = 12$ .
$\text{1 2 3 5}$ : Array $A$ becomes $[4, 5, 5, 1]$ .
2 1 2 2 :
- Consider numbers in range $[1, 2]$ , they are $\{4, 5\}$ .
- All non empty subsets of these numbers are $\{4\}, \{5\}, \{4, 5\}$ .
- Bitwise XOR of all these subsets(individually) are $4, 5, 1$ . Therefore, $S = \{4, 5, 1\}$ .
- We have $K = 2$ . All non-empty subsets of $S$ of size atmost $K = 2$ are $\{4\}, \{5\}, \{1\}, \{4, 5\}, \{4, 1\}, \{5, 1\}$ and their sum is $4 + 5 + 1 + 9 + 5 + 6 = 30$ .
Note that we output answers in a single line.

In the second test case, we have $N = 3, A = [2, 1, 1], Q = 1$ . Let's look at the queries:

2 1 3 2 :
- Consider numbers in range $[1, 3]$ , they are $\{2, 1, 1\}$ .
- All non empty subsets of these numbers are $\{2\}, \{1\}, \{1\}, \{2, 1\}, \{2, 1\}, \{1, 1\}, \{2, 1, 1\}$ . Note that if there are same numbers we count them multiple times.
- Bitwise XOR of all these subsets(individually) are $2, 1, 1, 3, 3, 0, 2$ . Therefore, $S = \{2, 1, 3\}$ . Remember that in S, we need to insert only distinct values and remove the element 0.
- We have $K = 2$ . All non-empty subsets of $S$ of size atmost $K = 2$ are $\{2\}, \{1\}, \{3\}, \{2, 1\}, \{1, 3\}, \{2, 3\}$ and their sum is $2 + 1 + 3 + 3 + 4 + 5 = 18$ .
Note that we output answers in a single line.