K. 线性 RMQ

内存限制：256 MiB 时间限制：1500 ms 标准输入输出

题目类型：传统评测方式：文本比较

转到题库提交记录返回比赛

RMQ 问题，全称为 Range Maximum/Minimum Query，表示区间最大/最小值查询。

顾名思义，本题要求解决 RMQ 问题，具体来说，要求解决区间静态最大值查询问题。

给出一个长为的整数序列和个询问，每个询问给出一个区间，对于每个询问，你需要给出之中的最大值。

因为询问个数过多，你只需要输出所有所有询问答案的异或和。

本题采用读入生成器生成读入的数据。

输入一行共个数。

读入方法参考如下代码：

typedef unsigned uint;
uint c1, c2;
uint seed;
int cnt, _n, _q;
void _magic() {
    c1 ^= (c1 << 17);
    c1 ^= (c1 >> 5);
    c1 ^= (c1 << 19);
    c2 ^= (c2 << 13);
    c2 ^= (c2 >> 4);
    c2 ^= (c2 << 23);
    seed = (seed * seed + c1) % c2;
}
uint rnd() {
    _magic();
    return (seed << 17) ^ (seed >> 5) ^ (seed << 23);
}
#define MAXVALUE 1000000000

#define MINLEN ((_n + 1) >> 1)

int _get() {
    static int l = 1, r = _n;
    if (cnt == 0) {
        ++cnt;
        return _n;
    } else {
        if (cnt <= _n) {
            ++cnt;
            return rnd() % MAXVALUE;
        }
        if (cnt == _n + 1) {
            ++cnt;
            return _q;
        } else if (cnt <= _n + 1 + _q * 2) {
            if ((cnt - _n - 1) % 2 == 1) {
                ++cnt;
                int len = rnd() % (((MINLEN << 1 ^ (~(_n)&1)) + 1) >> 1) + MINLEN;
                l = rnd() % (_n - len + 1) + 1;
                r = l + len - 1;
                return l;
            } else {
                ++cnt;
                return r;
            }
        }
    }
    return -1;
}
void init() {
    /* Input the arguments (Do not modify!)*/
    scanf("%u%u%u%d%d", &c1, &c2, &seed, &_n, &_q);
}
int get() {
    int ret = _get();
    if (ret == -1) {
        return -1;
    }
    return ret;
}
int main() {
    int n;
    n = get();
    
    // input a[1] ~ a[n] use : a[i] = get()
    // input q
    // ......
}

输出行，表示个询问的答案的异或和。

输入

233 233 233 10 10

输出

465516052

对于的数据，。

题目描述

输入格式

输出格式

样例

输入

输出

数据范围与提示