MojisBag | Topcoder Archive

Problem Statement

Moji has a set S. Initially, this set is empty.

The set S is a multiset: it may contain multiple copies of the same value.

Arpa has Q queries. In each query Arpa either inserts a value into S or erases a value from S.

The queries are generated using a pseudorandom sequence. You are given the numbers base, add, and rate. The sequence is defined as follows:

X[0] = add
for all i, X[i+1] = (X[i] * base + add) modulo (10^9 + 7)

For each i from 0 to Q-1, inclusive:

If X[i] modulo rate is nonzero, Arpa's query number i is to add X[i] to S.
If X[i] modulo rate is zero, Arpa's query number i is to remove an element from S. If S is currently empty, nothing happens. Otherwise, let idx = (X[i] modulo the number of inserts into S so far). Arpa's query is to remove the idx-th element (0-based index) inserted to S. If this element has already been removed from S, S remains unchanged.

Note that when erasing we only erase each specific idx at most once, even if the value has been inserted at other times as well. For example, if the first four queries are "insert 47", "insert 47", "erase 0-th inserted value", and "erase 0-th inserted value", the set S will contain one copy of the value 47 because the second erase didn't do anything.

After each query, Moji wants to know the maximum value that can be obtained by computing the bitwise xor between two elements of S. By definition, if S contains fewer than two elements, this value is 0. Let Y[i] be the largest bitwise xor after processing the query number i. Then, let:

Z[0] = Y[0]
for all i, Z[i+1] = (Z[i] * base + Y[i+1]) modulo (10^9 + 7)

You are given the ints Q, base, add, and rate. Compute and return the value Z[Q-1].

Definition

Class:: MojisBag
Method:: maximumXor
Parameters:: int, int, int, int
Returns:: int
Method signature:: int maximumXor(int Q, int base, int add, int rate)
(be sure your method is public)

Constraints

Q will be between 1 and 100,000, inclusive.
base will be between 2 and 10^9 + 5, inclusive.
add will be between 1 and 10^9 + 6, inclusive.
rate will be between 1 and 10^9 + 7, inclusive.

Examples

```
10
```
```
4747
```
```
7
```
```
3
```
```
Returns: 871911884
```
X = {7, 33236, 157771299, 940351124, 846754394, 543080192, 1653385, 848618553, 392242902, 977042774}. This describes the following sequence of actions: insert 7 insert 33236 attempt erase of value with idx=1 (value 33236, succeeds) insert 940351124 insert 846754394 insert 543080192 insert 1653385 attempt erase of value with idx=3 (value 846754394, succeeds) attempt erase of value with idx=0 (value 7, succeeds) insert 977042774 The maximum xor evolves as follows: Y = {0, 33235, 0, 940351123, 940351123, 940351123, 940942365, 940942365, 940942365, 975521759}.
```
5
```
```
47
```
```
7
```
```
3
```
```
Returns: 34911440
```
Here, we do the following: insert 7 attempt erase of value with idx=0 (value 7, succeeds) insert 15799 attempt erase of value with idx=0 (value 7, fails -- it was erased before) insert 34900327 Y = {0, 0, 0, 0, 34911440}.
```
3
```
```
429
```
```
3558
```
```
2
```
```
Returns: 0
```
Each of the first three operations does nothing, as you cannot erase from an empty set.

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.