MojiDeletes | Topcoder Archive

Problem Statement

This problem has a time limit of 3 seconds and memory limit of 512 MB.

Arpa has an array A with N elements (indexed 0 through N-1) and Q questions about elements of the array. Each question asks about some non-empty contiguous segment of the array. Arpa initially just wanted to know the bitwise xor of those elements, but that's not what we are doing in this problem.

Mojtaba is Arpa's kind teacher. He wants to give Arpa large answers. Therefore, he decided that whenever Arpa asks a question, he will ignore exactly one of the elements in the specified range. He will always choose the element that maximizes the bitwise xor of the remaining elements in the range. (Note that by definition the bitwise xor of no elements is zero.)

Today, Mojtaba is occupied by preparing a holiday celebration, so you will have to do his job. Compute the answers to all of Arpa's queries, and return their sum.

Both the contents of the array and the queries are generated pseudorandomly. The array A is constructed as follows:

A[0] = Add.
For each i from 1 to N-1: A[i] = (A[i-1] * Base + Add) modulo (10^9 + 7).

Parameters L and R for the queries are generated as follows:

L[0] = QAdd modulo N, and R[0] = (L[0] * QBase + QAdd) modulo N.
For each i from 1 to Q-1: L[i] = (R[i-1] * QBase + QAdd) modulo N, and R[i] = (L[i] * QBase + QAdd) modulo N.

For query number i, consider all elements of the array A at indices between min(L[i],R[i]) and max(L[i],R[i]), inclusive.

Definition

Class:: MojiDeletes
Method:: maximumXor
Parameters:: int, int, int, int, int, int
Returns:: long
Method signature:: long maximumXor(int N, int Q, int Base, int Add, int QBase, int QAdd)
(be sure your method is public)

Constraints

N will be between 1 and 500,000, inclusive.
Q will be between 1 and 500,000, inclusive.
Base, Add, QBase and QAdd will each be between 1 and 10^9 + 6, inclusive.

Examples

```
5
```
```
3
```
```
10
```
```
3
```
```
2
```
```
2
```
```
Returns: 37292
```
The array A is { 3, 33, 333, 3333, 33333 }. The same numbers in base 2 (with some leading zeros added for readability) look as follows: 0000000000000011 0000000000100001 0000000101001101 0000110100000101 1000001000110101 Query 0 is about elements A[1] and A[2]. Mojtaba will ignore A[1] and answer A[2] = 333. Query 1 is about the entire array. Mojtaba will ignore A[2] and answer (A[0] xor A[1] xor A[3] xor A[4]) = 36,626. Query 2 is the same as query 0. Thus, the correct return value is 333 + 36,626 + 333 = 37,292.

Returns: 41156782009

Returns: 534618713588573

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.