RMQ

题目描述

给 $n$ 个数 $a_1, a_2, \dots, a_n$，$q$ 个询问。

每个询问给定两个数 $l, r$，求出 $a_l, a_{l+1}, \dots, a_r$ 中的最大值。

输入格式

第一行五个数 $n, q, A, B, C(1\leq n\leq 10^6, 1\leq q\leq 10^7, 0\leq A, B, C < 2^{32})$。

为了防止输入过大，$a_i$ 和询问用下面代码生成。

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        a[i] = rng61();
    }
    for (int i = 1; i <= q; i++) {
        unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
        if (l > r) swap(l, r);
    }
}

输出格式

为了防止输出过大，输出所有询问答案的异或和。

样例输入

5 5 1 2 3

样例输出

337927