$\text{subtask 1}$

设 $dp_{i,j}$ 表示把前 $i$ 个位置划分成 $j$ 段的最小代价，转移：

$$dp_{i,j}=\max\limits_{k=1}^idp_{k-1,j-1}+f(k,i)$$

其中 $f(k,i)$ 为区间 $[k,i]$ 内的颜色数，可以预处理出来。

询问是 $O(1)$ 的，总复杂度 $O(n^3+m)$。

$\text{subtask 2}$

有至少两个做法。

sol 1

优化第一部分的 DP，以 $j$ 为阶段，那么我们只需要维护 $dp_{k-1,j-1}+f(k,i)$ 的最大值。

开一棵线段树，第 $k$ 个位置维护 $g_k=dp_{k-1,j-1}+f(k,i)$，当我们 $i\to i+1$ 时：

• $g_{k+1}=dp_{j-1,k}$
• $\forall k>lst_{i+1},g_k=g_k+1$

其中 $lst_i$ 为 $i$ 左边第一个等于 $a_i$ 的数的下标，没有则为 $0$。

上面的转移只需要线段树支持区间加即可。

询问还是 $O(1)$ 的，总复杂度 $O(n^2\log n+m)$。

sol 2

我们不难证明 $f(k,i)$ 满足四边形不等式，因此 DP 可以用决策单调性优化。

直接分治，两个指针移动来维护 $f(k,i)$，总复杂度 $O(n^2\log n+m)$。

$\text{subtask 3}$

因为 $m=1$，所以我们只需要解决一个询问。

由于蒙日矩阵 $\max+$ 卷积的 $k$ 次幂的每个位置都关于 $k$ 凸，因此 $dp_{i,j}$ 关于 $j$ 是一个凸函数，这种区间划分问题的经典做法是 $wqs$ 二分。

二分斜率 $c$，转移为：

$$dp_{i}=\max_k dp_{k-1}+f(k,i)-c$$

然后同上用线段树优化转移，复杂度 $O(n\log^2n+m)$。

$\text{subtask 4}$

我们考虑一下 $wqs$ 二分的斜率 $c$。

那么因为 $a_i\leq 30$，所以 $f(k,i)\leq 30$，那么当 $c>30$ 时，$f(k,i)-c<0$，此时切点一定是分一段，因此只有 $c\leq 30$ 的 $c$ 有意义。

对于 $c=0\cdots 30$ 各做一遍线段树优化 DP，存下每个前缀的答案即可。

复杂度 $O(\max a_in\log n+m)$。

$\text{subtask 5}$

上一个做法告诉我们，当 $c$ 过大时，切点就会很小。

我们可以具体分析一下，设 $F(k)=dp_{*,k},D(k)=F(k)-F(k-1)$，因为 $F$ 是凸函数，所以 $D(k)\geq D(k+1)$ 恒成立。

同时，因为 $F(k)\leq n$，那么有 $(k-1)D(k)\leq \sum_{i=2}^k D(i)\leq F(k)-F(1)\leq n$，即 $D(k)\leq \lfloor\frac{n}{k-1}\rfloor$。

设斜率为 $c$ 时的切点为 $G(c)$ ，那么 $F(G(c)-1)-c\times (G(c)-1)\leq F(G(c))-c \times G(c)$ ，即 $F(G(c))-F(G(c)-1)\geq c$ ，$c\leq D(G(c))\leq \lfloor \frac{n}{G(c)-1}\rfloor$。

我们取阈值 $B$，

• 对于 $k\leq B$ 的询问，我们可以预处理所有普通 DP 值。

• 对于 $k>B$ 的询问，根据上面的性质，$G(c)\geq k$ 的 $c$ 满足 $c\leq \lfloor\frac{n}{B} \rfloor$ ，我们预处理这些 $c$ 对应的 DP 值。

都采用线段树优化，单次 DP 都是 $O(n\log n)$，取 $B=\sqrt n$，我们预处理的复杂度是 $O(n\sqrt n\log n)$。

询问时，前部分可以 $O(1)$ 回答，后半部分可以直接二分，不过这样空间是 $O(n\sqrt n)$ 的。

同时注意到 $G(c)$ 是单调的，因此可以把询问按照 $k$ 排序后，用一个指针维护转移点，空间就是线性了。

排序可以用桶排序，该做法时间复杂度 $O(n\sqrt n\log n+m)$，空间复杂度 $O(n+m)$。

注意到线段树的常数比较大，如果被卡常可以把第一部分的 $dp$ 换成决策单调性分治，因为访问时连续的所以常数小很多。如果实现较好，也可以直接获得满分。

$\text{subtask 6}$

考虑能不能把线段树的 $\log$ 去掉。

观察一下我们实际需要支持的操作：

• 向末尾加入一个数
• 后缀加 $1$
• 求最大值

维护一个单调递减的单调栈，那么 $1$ 操作可以直接不断弹栈维护，$3$ 操作就是查询栈底元素。

对于 $2$ 操作，我们找到该后缀在单调栈上对应的位置，这个可以用并查集维护，然后相当于把这个部分往前面合并弹出若干元素，最后打上 $+1$ 标记。

因为要支持中间弹出元素，所以我们用链表维护这个单调栈，至于 $+1$ 标记，我们可以发现我们相当于只需要查询栈底，查询栈顶，查询某相邻两个位置的差值，因此直接维护单调栈内元素的差分值即可，打标记是简单的。

瓶颈在于并查集，因此单次 $dp$ 的复杂度优化到了 $O(n\alpha (n))$，如果采用严格线性并查集，我们可以做到 $O(n)$。

剩下部分不变，复杂度 $O(n\sqrt n+m)$，空间 $O(n+m)$，可以通过此题。

值得一提的是，在本题中你可以发现，我们优化单次 DP 和优化多次询问的部分是独立的，也就是说，我们把 $f(l,r)$ 换成任意凸函数，在值域不大的情况下都可以在根号的代价内求出所有函数值。

代码不放了，需要的可以私聊。

来一篇无脑题解，但可能需要卡常。

思路

我们发现有一个很显然的 $O(n^2)$ dp，即 $dp_{i,j}$ 表示当前结尾是 $i$，我们选了 $j$ 段的最大价值。

转移可以用线段树优化从而做到 $O(n^2 \log n)$。

进一步的，我们会发现 $dp_{i,j}$ 在固定 $i$ 的情况下 $(j,dp_{i,j})$ 构成一个整点凸包。而这题的整点凸包上的转折点不会超过 $O(\sqrt n)$ 个。（可能有更优的分析进一步减小上界）

所以我们维护线段树一个节点对应区间 dp 凸包取 max 的凸包，其余和暴力作法基本一致。

但直接做可能常数过大，所以我们可以通过一些观察注意到：

1. 凸包合并形式为取靠左凸包的前缀和靠右凸包的后缀拼接而成。（决策单调性）
2. 转折点可以被刻画成左凸包的一个转折点。

时间复杂度 $O(q \log n + n \sqrt n \log n )$。

空间复杂度 $O(q + n \sqrt n \log n )$。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, id, seed, limx;
int a[100005], pre[100005], now[100005];
struct{
    int x, k, c;
}b[1000005];
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;
}
void gen(){
    for(int i = 1; i <= m; ++i){
        b[i].x = readW(limx, n);
        b[i].k = readW(1, b[i].x);
        b[i].c = readW(0, 1e7);
    }
}
vector<pair<int, int>> f[(1<<18)+5];
int tag[(1<<18)+5];
int p[100005];
void chkmax(int &x, int y){
    if(x < y)x = y;
}
int qry(vector<pair<int, int>> &f, int pl){
    if(pl < f[0].first || pl > f.back().first)return -1;
    int l_ = 0, r_ = f.size()-1, res = -1;
    while(l_ <= r_){
        int mid = l_+r_>>1;
        if(f[mid].first <= pl){
            res = mid;
            l_ = mid + 1;
        }else{
            r_ = mid - 1;
        }
    }
    return pl == f[res].first?f[res].second:f[res].second+(f[res+1].second-f[res].second)/(f[res+1].first-f[res].first)*(pl-f[res].first);
}
pair<int, int> qwq[1005];
int len;
void run(){
    if(len <= 1)return;
    if(qwq[len-2].first == qwq[len-1].first){
        len--;
        return;
    }
    if(len <= 2)return;
    if((qwq[len-1].second-qwq[len-2].second)/(qwq[len-1].first-qwq[len-2].first) == (qwq[len-2].second-qwq[len-3].second)/(qwq[len-2].first-qwq[len-3].first)){
        swap(qwq[len-1], qwq[len-2]);
        len--;
        return;
    }
}
void merge(vector<pair<int, int>> &ans, vector<pair<int, int>> &f, vector<pair<int, int>> &g){
    ans.clear();
    if(!f.size() || !g.size()){
        ans = f;
        return;
    }
    int L = f[0].first, R = g.back().first;
    int l = 0, r = f.size()-1, res = L-1;
    while(l <= r){
        int mid = l+r>>1;
        if(f[mid].second > qry(g, f[mid].first)){
            res = f[mid].first;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    len = 0;
    if(res >= L){
        for(int i = 0; i < f.size(); i++){
            if(f[i].first > res){
                qwq[len++] = {res, f[i-1].second+(f[i].second-f[i-1].second)/(f[i].first-f[i-1].first)*(res-f[i-1].first)};
                run();
                break;
            }
            qwq[len++] = f[i];
        }
    }
    for(int i = 0; i < g.size(); i++){
        if(g[i].first > res){
            if(i){
                qwq[len++] = {res+1, g[i-1].second+(g[i].second-g[i-1].second)/(g[i].first-g[i-1].first)*(res+1-g[i-1].first)};
                run();
            }
            for(int j = i; j < g.size(); j++){
                qwq[len++] = g[j];
                if(j<i+3)run();
            }
            break;
        }
    }
    ans.resize(len);
    for(int i = 0; i < len; i++)ans[i] = qwq[i];
    return;
}
void run(int now, int k){
    tag[now] += k;
    for(auto &[x,y] : f[now])y += k;
}
void down(int now){
    if(tag[now]){
        run(now*2, tag[now]);
        run(now*2+1, tag[now]);
        tag[now] = 0;
    }
}
int ok = 0;
void chg(int now, int l, int r, int x, int y, int k){
    if(x <= l && r <= y){
        run(now, k);
        return;
    }
    down(now);
    int mid = l+r>>1;
    if(x <= mid)chg(now*2, l, mid, x, y, k);
    if(y > mid)chg(now*2+1, mid+1, r, x, y, k);
    auto pre = f[now];
    merge(f[now], f[now*2], f[now*2+1]);
}
void chg(int now, int l, int r, int x){
    if(l == r){
        if(x == 0)f[now] = vector<pair<int, int>>{make_pair(0, 0)};
        else{
            f[now] = f[1];
            for(auto &[x, y] : f[now])x++;
        }
        return;
    }
    down(now);
    int mid = l+r>>1;
    if(x <= mid)chg(now*2, l, mid, x);
    else chg(now*2+1, mid+1, r, x);
    merge(f[now], f[now*2], f[now*2+1]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> id >> seed >> limx;
    PRG_state=seed;
    gen();
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pre[i] = now[a[i]];
        now[a[i]] = i;
    }
    sort(b+1, b+1+m, [&](auto x, auto y){
        return x.x < y.x;
    });
    chg(1, 0, n, 0);
    ll lastans = 0;
    int z = 1;
    for(int i = 1; i <= n; i++){
        chg(1, 0, n, pre[i], i-1, 1);
        auto res = f[1];
        for(auto &[x, y] : res)x++;
        chg(1, 0, n, i);
        while(z <= m && b[z].x == i){
            lastans ^= 1ll * b[z].c * qry(res, b[z].k);
            z++;
        }
    }
    cout << lastans << "\n";
    return 0;
}