求出区间最大值位置 x。显然 p_x 不能成为答案且 p_x 不会被删除。考虑 l \le i < x 的数中，答案 \ge p_i 需要满足的条件。可以发现充要条件是 [i, x] 中的最小值 \le [l, i] 中的最小值或 [x, r] 中的最小值。因为若两侧最小值都小于中间最小值那么这两个数无法在删 p_x 前被删，否则一定能借助中间最小值把两侧全部删光。
求出 [l, x] 中最小值的位置 y 和 [x, r] 中最小值的位置 z。那么若 [i, x] 中最小值 \le [l, i - 1] 中最小值需要满足 i \le y，若 [i, x] 中最小值 \le [x, r] 中最小值，设 L_j 为 p_j 前面第一个比 p_j 小的数，那么需要满足 i \le L_z。求出 i 的范围后求区间最大值即可。
时间复杂度 $O(n \log n + m)$ 或 $O(n + m)$。
```cpp
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
const int logn = 22;
int n, m, a[maxn], b[maxn], f[logn][maxn], g[logn][maxn], L[maxn], R[maxn], stk[maxn], top;
uint seed, A, B, C;
inline uint rnd() {
seed = A * seed * seed + B * seed + C;
seed = seed ^ (seed << 27);
seed = seed ^ (seed >> 19);
return seed;
}
inline pii gen() {
int l, r;
do {
l = rnd() % n + 1;
r = rnd() % n + 1;
} while (abs(l - r) < 2);
if (l > r) {
swap(l, r);
}
return make_pair(l, r);
}
inline int qmax(int l, int r) {
if (l > r) {
return 0;
}
int k = __lg(r - l + 1);
return max(f[k][l], f[k][r - (1 << k) + 1]);
}
inline int qmin(int l, int r) {
int k = __lg(r - l + 1);
return min(g[k][l], g[k][r - (1 << k) + 1]);
}
void solve() {
scanf("%d%d%u%u%u%u", &n, &m, &seed, &A, &B, &C);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[a[i]] = i;
f[0][i] = g[0][i] = a[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
g[j][i] = min(g[j - 1][i], g[j - 1][i + (1 << (j - 1))]);
}
}
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] > a[i]) {
--top;
}
L[i] = (top ? stk[top] : 0);
stk[++top] = i;
}
top = 0;
for (int i = n; i; --i) {
while (top && a[stk[top]] > a[i]) {
--top;
}
R[i] = (top ? stk[top] : n + 1);
stk[++top] = i;
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
pii p = gen();
int l = p.fst, r = p.scd;
int x = b[qmax(l, r)];
int y = b[qmin(l, x)], z = b[qmin(x, r)];
ans ^= (1LL * i * max(qmax(l, max(min(y, x - 1), L[z])), qmax(min(max(z, x + 1), R[y]), r)));
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
```