P8911 [RC-06] Minimum and Maximum

受洛谷限制，本题数据有所删减。评测全套数据请到 [InfOJ](http://119.27.163.117/contest/7/)。

给定长度为 $n$ 的序列 $[a_1,a_2,\dots ,a_n]$。 $m$ 次询问，每次给出四个正整数 $L_1,R_1,L_2,R_2\ (1\le L_1\le R_1\le 4000,1\le L_2\le R_2\le 4000)$，问有多少个区间 $[l,r]\ (1\le l\le r\le n)$ 满足 $a_l,a_{l+1},\dots,a_r$ 中的最大值属于 $[L_1,R_1]$、最小值属于 $[L_2,R_2]$。 询问次数很大，所以询问是在程序内生成的。请自行阅读提示说明一栏的代码。

第一行两个正整数 $n,m$。 接下来一行 $n$ 个正整数 $a_1\sim a_n$。 接下来一行三个正整数 $p,q,seed$，为数据生成器的参数。你不需要理解数据生成器具体的运行过程，你只需要知道，如果正确生成了询问的话，一定有 $L_1,R_1,L_2,R_2\in [p,q]$。

设第 $i$ 个询问的答案为 $ans_i$。输出一行一个整数，为 $\operatorname{xor}_{i=1}^m (i\times ans_i)$ 的值。

**样例 1 解释** 五次询问的 $(L_1,R_1,L_2,R_2)$ 分别为 $(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)$，答案分别为 $15,1,1,2,6$。 输出 $(1\times 15)\ \mathrm{xor}\ (2\times 1)\ \mathrm{xor}\ (3\times 1)\ \mathrm{xor}\ (4\times 2)\ \mathrm{xor}\ (5\times 6)=24$。 **样例程序** 下面是我们提供的样例程序，你可以直接以其为基础编写你的程序。 ```cpp #include using namespace std; typedef long long ll; namespace Generator{ typedef unsigned long long ull; typedef __uint128_t L; ull seed; int p,q; struct FastMod { ull b, m; FastMod(ull b) : b(b), m(ull((L(1) > 64); ull r = a - q * b; // can be proven that 0 = b ? r - b : r; } }F(2); void init(){ cin>>p>>q>>seed;//读入 p,q,seed assert(p!=q); F=FastMod(q-p+1); } unsigned long long rd () { seed ^= (seed > 7); seed ^= (seed r1)swap(l1,r1); if(l2>r2)swap(l2,r2); } } int n,m,a[100005]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i