P10891 【烂题杯 Round 1】消灭劳嗝
题目描述
你需要消灭劳嗝。
给定一个长度为 $n$ 的排列 $A=a_1,a_2,\cdots,a_n$，定义 $S_i=\{x|x\ge i\land \max_{i\le k\le x}a_k\le a_x\}$，您可以把它理解为以 $i$ 开头的后缀的前缀最大值的下标集合。例如对于 $A=\{3,5,2,1,4\}$，$S_1=\{1,2\}$，$S_3=\{3,5\}$。
有 $q$ 次询问，每次询问给出 $l,r$，求：
$$
\left(\left(\sum_{l\le x\le y\le r} |S_x\cup S_y|-\sum_{\substack{{1\le x
输入格式
由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。
第一行输入两个非负整数 $n$、$X$。表示排列长度、随机种子。
初始令 $a_i=i$，接下来输入一行一个整数 $c$，表示对排列的操作次数。
接下来我们将会对排列 $A$ 进行 $c$ 次操作，对于下标从 $1$ 开始的第 $i$ 次操作，令 $l=(X\times (X\oplus i))\bmod n+1,r=(X\oplus(i\times i))\bmod n+1$，你需要交换 $a_l$ 与 $a_r$。$\oplus$ 表示按位异或。
对于 C++，代码实现如下：
```cpp
l = (1ll * X * (X ^ i)) % n + 1;
r = (X ^ (1ll * i * i)) % n + 1;
```
接下来输入一行一个整数 $q$，表示询问组数。
对于下标从 $1$ 开始的第 $i$ 次询问，我们令 $l=\min((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1,r=\max((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1$。表示询问的参数。
对于 C++，代码实现如下：
```cpp
l = min((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
r = max((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
```
输出格式
由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。
输出一行一个整数，表示 $q$ 次询问中所有答案的异或和。
说明/提示
**样例 1 解释：**
操作后 $A=\{1,5,4,2,3\}$。
对询问解密后真实询问如下：
```
4 5
2 3
1 5
3 4
3 5
```
对输出解密后真实输出如下：
```
5
998244350
33
1
11
```
对于第一个询问，$S_4=\{4,5\}$，$S_5=\{5\}$，$|S_4\cup S_4|+|S_4\cup S_5|+|S_5\cup S_5|=5$。
对于倒数第二个询问，不要忘了 $1\le x