题解：P10181 龙逐千灯幻

· · 题解

** 的为什么大家都省略 WQS 二分的细节，这不是最大难点吗？

dp 数组值域是 O(n) 的，且代价函数满足四边形不等式。

凸性决策单调性都是有的，设 f_{i,j} 表示前 i 个数分 j 段。则 f_i 是一个上凸壳。

你这个上凸壳只会有最多根号个拐点，因为最高点坐标只有 O(n)，但是你做不了，你不能每次都 WQS 去把拐点全部求出来吧。

显然这个斜率是减少的非常快的，具体的当 j>\sqrt{n} 时，f_{i,j}-f_{i,j-1} \le \sqrt{n}，否则 f_{i,j} > j \times \sqrt{n} \ge n，于是乎你前根号个 j 暴力做，后面的你直接枚举 WQS 二分时的斜率，每个斜率做一次就能把一个 i 的所有拐点求出来。

至于 dp 是非常典的一个优化，没什么好说的。

首先根本不用写链表，这是比较麻烦的，直接并查集维护一个连续段的左右端点暴力跳就行了。

到这里都是很朴素的，但是呢这题恶心在于代码不是很好写？在 dp 的时候单调栈必须维护不增序列，这样才能使得每一次转移所取的左端点是最靠左的，从而保证段数最小，才能 check WQS 二分。可能这个细节确实比较弱智但很容易在最开始想的时候把它维护成单调递减序列，然后瞎维护一些没有任何作用的信息，这玩意坑死人。

不知道为什么这个做法也要卡常。感觉最方便的卡常方法就是把 MAXB 的值设得更精确一点。

// ST: 2025/4/25/14:30 SC: 2025/4/26/14:50 SD: 2025/4/26/16:04
#include<bits/stdc++.h>
using ll = long long; using ull = unsigned long long; using uint = unsigned int;
#define ld std::cin
#define jyt std::cout
#define cmd std::cerr
#define REQ(i, l, r) for (int i = l; i <  r; ++i)
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
const int BUFL = 1 << 20; char buf[BUFL]; char* p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUFL, stdin), p1 == p2) ? EOF : *p1++)
inline int ldr() { 
    int x = 0, f = 0; char ch = gc();
    while (ch < '0' || '9' < ch) f = (ch == '-'), ch = gc();
    while ('0' <= ch && ch <= '9') x = x * 10 + (ch - '0'), ch = gc();
    return f ? -x : +x;
}
namespace GEN {
    uint64_t PRG_state; int limx;
    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; }
}
const int N = 1e5 + 7, M = 1e6 + 7, B = 317;
int n, m, TESTID, a[N], pre[N], pack[N];
struct Into { 
    ll v;
    Into(ll X = 0) { v = X; }
    inline Into expand(ll p, int q) { return Into(v + p); }
} Intof[N], Intog[N], Intoh[N];
struct Info {
    ll v; int L;
    Info(ll X = 0, int Y = 0) { v = X, L = Y; }
    inline Info expand(ll p, int q) { return Info(v + p, L + q); }
} Infof[N], Infoh[N];
int d_fa[N], d_sz[N], d_L[N], d_R[N]; ll d_tg[N]; // f[i] <= n
inline int gf(int x) { return d_fa[x] == x ? x : (d_fa[x] = gf(d_fa[x])); }
inline int onion(int x, int y) { 
    if ((x = gf(x)) == (y = gf(y))) return x;
    if (d_sz[x] > d_sz[y]) std::swap(x, y);
    d_fa[x] = y, d_sz[y] += d_sz[x], d_tg[y] += d_tg[x];
    return d_L[y] = std::min(d_L[y], d_L[x]), d_R[y] = std::max(d_R[y], d_R[x]), y;
}
template<typename Inko>
inline void brute(Inko* f, Inko* g, Inko *h, int spt, ll cost) {
    REP(i, spt, n) d_fa[i] = i, d_sz[i] = 1, d_L[i] = d_R[i] = i, d_tg[i] = 0;
    if (1 < spt) d_fa[1] = spt, d_L[spt] = 1; 
    int tgs = 1, top = spt; d_tg[spt] = 1, h[spt] = g[spt - 1];
    f[spt] = h[d_R[gf(1)]].expand(d_tg[gf(1)] + cost, 1);
    REP(i, spt + 1, n) {
        int x = i; h[x] = g[i - 1].expand(-tgs, 0);
        while (top && h[d_R[top]].v - d_tg[x] < h[d_R[x]].v) 
            x = onion(top, x), top = d_L[x] - 1;
        top = x, x = gf(std::max(pre[i] + 1, spt));
        int y = d_L[x] - 1; d_tg[x] += 1, tgs += 1;
        while (y && h[d_R[y]].v - d_tg[x] < h[d_R[x]].v)
            x = onion(y, x), y = d_L[x] - 1; 
        f[i] = h[d_R[gf(1)]].expand(d_tg[gf(1)] + cost, 1);
    }
}
struct Query { int x, k, c; } c[M]; int Ans[M];
std::vector<int> QRY[B + 3], YRQ[N]; int ptq[N];
signed main() { 
    std::ios::sync_with_stdio(false), ld.tie(0), jyt.tie(0);
    n = ldr(), m = ldr(), TESTID = ldr(), GEN::PRG_state = ldr(), GEN::limx = ldr();
    REP(i, 1, n) a[i] = ldr(), pre[i] = pack[a[i]], pack[a[i]] = i;
    REP(i, 1, m) {
        c[i].x = GEN::readW(GEN::limx, n), c[i].k = GEN::readW(1, c[i].x), c[i].c = GEN::readW(0, 1e7);
        if (c[i].k <= B) QRY[c[i].k].emplace_back(i); else YRQ[c[i].x].emplace_back(i);
    }
    Into *pt1 = Intof, *pt2 = Intog;
    REP(lv, 1, std::min(n, B)) {
        brute(pt1, pt2, Intoh, lv, 0);
        for (int i : QRY[lv]) Ans[i] = (pt1 + c[i].x) -> v;
        std::swap(pt1, pt2);
    }
    int MAXB = 0; REP(i, 1, n) MAXB = std::max(MAXB, (int)((pt2 + i) -> v) - (int)((pt1 + i) -> v));
    if (n > B && MAXB) { 
        REP(i, 1, n) std::sort(YRQ[i].begin(), YRQ[i].end(), [](int X, int Y) { return c[X].k < c[Y].k; });
        REP(cost, 0, MAXB) {
            REP(i, 1, n) Infof[i] = Info();
            brute(Infof, Infof, Infoh, 1, -cost);
            REP(i, 1, n) { auto& o = YRQ[i];
                while (!o.empty() && c[o.back()].k >= Infof[i].L) 
                    Ans[o.back()] = Infof[i].v + 1ll * c[o.back()].k * cost, o.pop_back(); 
            }
        } 
    } ll Res = 0;
    REP(i, 1, m) Res ^= (1ll * Ans[i] * c[i].c);// cmd << "Ans=" << Ans[i] << '\n';
    jyt << Res << '\n';
    return 0;
}