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
50000
50000
10003
1000003
10003
1000003
Returns: 53447291985080
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.
47
42
7654321
1234567
23
10
Returns: 41156782009
500000
500000
1003
1000003
1003
1000003
Returns: 534747796685940
500000
500000
2
1
2
1
Returns: 534618713588573
500000
500000
220373064
708017183
925153796
555638517
Returns: 534776054705465
500000
500000
849195462
174530381
918879387
911912779
Returns: 534725827034200
500000
500000
743630977
699033140
834354869
740600103
Returns: 534662413848230
500000
500000
226015266
692929830
443095625
812777654
Returns: 532672003595283
500000
500000
108058582
466862768
961645056
823120705
Returns: 534576983459520
499993
500000
809382521
784443218
801953417
264492295
Returns: 534739872781085
499994
500000
50665378
904547622
368627318
902194004
Returns: 534660516431403
499990
500000
182837299
405591419
631163983
871011017
Returns: 534632910677328
499990
500000
827823889
758616188
248513425
853603504
Returns: 534726601601367
499993
500000
559783360
587243334
874107638
191082356
Returns: 534699249117356
500000
500000
1000000006
1
1
232532424
Returns: 500000
1
1
2
1
2
123456789
Returns: 0
500000
500000
100
99
97
103
Returns: 534735155797080