P10181 Dragon Chasing a Thousand Lanterns

 The Year of the Dragon has arrived, and Fanfan has also raised his own colorful dragon lantern. He wants to become a big colorful dragon too.

Fanfan has a total of $n$ dragon lanterns. The color of the $i$-th lantern is $a_i$. Fanfan defines the beauty value $f(l,r)$ of an interval $[l,r]$ as the number of distinct colors in $a_l \cdots a_r$. Fanfan is going out to have fun with his dragon lanterns. He plans to go out for $m$ days. On day $i$, he will bring lanterns No. $1 \cdots x_i$. However, he finds that if many lanterns are bundled together, others will only notice how many different colors there are. So Fanfan plans to divide these $x_i$ lanterns, in order of their indices, into exactly $k_i$ intervals, such that each lantern belongs to exactly one interval. Then the beauty value of this trip is the sum of the beauty values of all intervals. Please help Fanfan maximize the beauty value for each trip.

The first line contains five integers $n,m,id,seed,limx$, representing the sequence length, the number of queries, the $\texttt{subtask}$ id (in the samples, $id=0$), the random seed, and a parameter $limx$ related to the queries. Because the input size is too large, the queries are generated in the following way. We use the following code to generate a pseudo-random sequence: ```cpp uint64_t PRG_state; uint64_t get_number() { PRG_state ^= PRG_state > 7; PRG_state ^= PRG_state

To reduce the amount of output, we use the following compression method. If the answer to the $i$-th query is $ans_i$, and its generation parameter is $c_i$, then you need to output: $$\bigoplus\limits_{i=1}^m(ans_i\times c_i)$$ where $\bigoplus$ denotes the bitwise XOR operation. This value is guaranteed to be within the integer range representable by `long long`.

### Sample 1 Explanation The queries are: ``` 3 1 6121576 5 3 3089509 1 1 4506170 3 1 2821007 1 1 7941511 ``` The answers are: ``` 3 5 1 3 1 ``` For the first query, it must be divided into one interval, so it is $[1,3]$, and the beauty value is $f(1,3)=3$. For the second query, the optimal plan is to divide into $[1,3],[4,4],[5,5]$, and the beauty value is $f(1,3)+f(4,4)+f(5,5)=5$. The last three queries are similar. ### Sample 2 Explanation The queries are: ``` 8 4 6858024 3 2 236530 2 2 8140891 5 3 4562139 8 7 4749403 7 4 4319971 5 1 5063575 3 1 7343109 6 2 1566851 3 1 7959241 ``` The query answers are: ``` 7 3 2 5 8 7 2 2 4 2 ``` ### Constraints This problem uses bundled testdata. - Subtask 1 ($10$ points): $1 \leq n\leq 500$. - Subtask 2 ($15$ points): $1\leq n\leq 3000$. - Subtask 3 ($15$ points): $m=1$. - Subtask 4 ($20$ points): $1\le a_i\le 30$. - Subtask 5 ($20$ points): $1\leq n\leq 4\times 10^4$. - Subtask 6 ($20$ points): No special restrictions. For $100\%$ of the testdata, $1 \leq n\leq 10^5$, $1\leq m\leq 10^6$, $0\leq seed\leq 10^9$, $1\leq limx\leq n$, $1\leq a_i\leq n$。 Translated by ChatGPT 5