龙逐千灯幻
题目背景
![](https://cdn.luogu.com.cn/upload/image_hosting/6w2vttoo.png)
龙年到,帆帆也举起了自己的彩龙灯,他自己也要变成大彩龙啦!
题目描述
帆帆一共有 $n$ 盏龙灯,第 $i$ 盏的颜色是 $a_i$。
帆帆认为一段区间 $[l,r]$ 的美观度 $f(l,r)$ 为 $a_l\cdots a_r$ 中的不同颜色个数。
帆帆准备带着自己的龙灯去玩,他一共计划去玩 $m$ 天,第 $i$ 天,他会带着自己的 $1\cdots x_i$ 号龙灯,但是他发现如果把很多龙灯装在一起,那么别人只会注意到其中有多少种不同的颜色。
因此帆帆准备把这 $x_i$ 个龙灯按照编号顺序分成恰好 $k_i$ 个区间,满足每盏灯恰好在一个区间内。
那么帆帆这次出行的美观度就为所有区间的美观度的和。
请你帮帮帆帆最大化每一次出行的美观度。
输入输出格式
输入格式
第一行五个整数 $n,m,id,seed,limx$,分别代表序列长度,询问次数,以及 $\texttt{subtask}$ 编号(样例中的 $id=0$),随机数种子,以及一个和询问有关的参数 $limx$。
因为本题输入量过大,因此采用如下方式生成询问:
我们使用下面的代码生成一个伪随机数列:
```cpp
uint64_t PRG_state;
uint64_t get_number()
{
PRG_state ^= PRG_state << 13;
PRG_state ^= PRG_state >> 7;
PRG_state ^= PRG_state << 17;
return PRG_state;
}
int readW(int l,int r)
{
return get_number()%(r-l+1)+l;
}
```
一开始 `PRG_state=seed`,你每次调用 `readW(l,r)` 会返回一个 $[l,r]$ 内的随机数。
第二行 $n$ 个整数,第 $i$ 个整数代表 $a_i$。
设 $x_i,k_i,c_i$ 表示第 $i$ 组询问需要的参数 $x,k,c$,其中 $c$ 的作用见输出格式,那么所有询问的参数可以用以下程序生成:
```cpp
for (int i = 1; i <= m; ++i) {
x[i] = readW(limx, n);
k[i] = readW(1, x[i]);
c[i] = readW(0, 1e7);
}
```
注:**请不要在运行上述代码段获得各组询问的参数之前调用 `readW()` 函数,否则无法获得正确的询问信息。** 本题不需要利用该伪随机数生成器的特殊性质,你只需将 `get_number()` 视为一个每次调用独立且均匀随机地生成一个无符号 $64$ 位整数的生成器即可。本题也不需要优化伪随机数生成器的内部实现。
输出格式
为了减少输出量,我们使用如下方式进行信息压缩:
如果第 $i$ 组询问的答案为 $ans_i$,其生成参数为 $c_i$,那么你需要输出:
$$\bigoplus\limits_{i=1}^m(ans_i\times c_i)$$
其中 $\bigoplus $ 为异或运算,该值显然一定位于 `long long` 能表示的整数范围内。
输入输出样例
输入样例 #1
5 5 0 956144375 1
2 4 1 5 2
输出样例 #1
21971409
输入样例 #2
10 10 0 478178732 1
2 2 1 1 2 1 2 1 2 1
输出样例 #2
2834792
说明
### 【样例1解释】
询问分别是:
```
3 1 6121576
5 3 3089509
1 1 4506170
3 1 2821007
1 1 7941511
```
答案分别是:
```
3
5
1
3
1
```
对于第一组询问,要分成一个区间,那么就是 $[1,3]$,美观度就是 $f(1,3)=3$ 。
对于第二组询问,最优的方案是分成 $[1,3],[4,4],[5,5]$,美观度是 $f(1,3)+f(4,4)+f(5,5)=5$
后三个询问同理。
### 【样例2解释】
询问分别是:
```
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
```
询问答案分别是:
```
7
3
2
5
8
7
2
2
4
2
```
### 【数据范围】
本题采用捆绑测试。
- 子任务一($10$ 分):$1 \leq n\leq 500$。
- 子任务二($15$ 分):$1\leq n\leq 3000$。
- 子任务三($15$ 分):$m=1$。
- 子任务四($20$ 分):$1\le a_i\le 30$。
- 子任务五($20$ 分):$1\leq n\leq 4\times 10^4$。
- 子任务六($20$ 分):无特殊限制。
对于 $100\%$ 的数据,$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$。