Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

XOR Is Fun

By adnan_toky · Limits 2s, 1.0 GB

Efa hates numbers. But she loves the XOR operation. This time, you have to solve another problem for her.

You are given a sequence a1, a2, a3, , ana_1,~a_2,~a_3,~…,~a_n of nn integers and qq queries. In each query, you are given four integers ll, rr, kk and xx. Let ss be a kk length subsequence of the segment al, al+1, al+2, , ara_l,~a_{l+1},~a_{l+2},~…,~a_r. Print the maximum value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x} among all possible ss and the number of such subsequences that maximizes the value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x}. Since the number of subsequences can be large, print it modulo 109+710^9+7.

Here, \oplus denotes the bitwise XOR operation.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.


The first line of input contains two space-separated integers nn and qq (1n,q105)(1 \leq n, q \leq 10^5) denoting the number of integers and the number of queries.

The next line contains nn space-separated integers a1, a2, a3, , ana_1, ~a_2, ~a_3,~…, ~a_n​ (1ai109)(1 \leq a_i \leq 10^9).

Following qq lines contain four integers each. llrr (1lrn)(1 \leq l \leq r \leq n), kk (1krl+1)(1 \leq k \leq r-l+1) and xx (1x109)(1 \leq x \leq 10^9).


For each query, print two space-separated integers. The maximum value and the number of subsequences as described above.


5 3
2 1 2 4 3
1 3 2 7
1 3 2 5
1 5 3 5
11 2
14 1
20 1

In the first query, the sequence {2,1,2}\{2, 1, 2\} has three subsequences of length 22. {2,1}\{2, 1\}, {2,2}\{2, 2\} and {1,2}\{1, 2\}.

For the first subsequence: (27)+(17)=11(2 \oplus 7) + (1 \oplus 7) = 11.

For the second subsequence: (27)+(27)=10(2 \oplus 7) + (2 \oplus 7) = 10.

For the third subsequence: (17)+(27)=11(1\oplus 7) + (2 \oplus 7) = 11.

So, the maximum value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x} is 1111 and the number of such subsequences is 22.



44% Solution Ratio

rfpermenEarliest, 1M ago

MrBrionixFastest, 0.4s

adnan_tokyLightest, 530 MB

Soumya1Shortest, 2702B


Login to submit


Let's solve the problem for the whole sequence instead of a given range. We can store each number i...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.