[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}^q
(i\times ans_i)$ 的值。
输入输出样例
输入样例 #1
5 5
2 4 1 3 5
1 5 1145141919810输出样例 #1
24输入样例 #2
10 20000000
1 3 4 10 5 5 2 7 10 7
1 10 23333333333333333输出样例 #2
548722417说明
**样例 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<bits/stdc++.h>
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) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= 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 << 13);
seed ^= (seed >> 7);
seed ^= (seed << 17);
return seed;
}
void getlr(int &l1,int &r1,int &l2,int &r2){
//将 l1,r1,l2,r2 作为参数传入，即可得到一组询问
l1=F.reduce(rd())+p;
r1=F.reduce(rd())+p;
l2=F.reduce(rd())+p;
r2=F.reduce(rd())+p;
if(l1>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<=n;i++)scanf("%d",&a[i]);
Generator::init();
long long xorsum=0;
for(int i=1,l1,r1,l2,r2;i<=m;i++){
Generator::getlr(l1,r1,l2,r2);
long long ans=/*ans保存你的答案*/;
xorsum^=ans*i;
}
cout<<xorsum;
}
```
**数据范围**
本题有四个子任务。子任务一时间限制 $0.5$ 秒，其它子任务时间限制 $5$ 秒。
所有数据均满足：$1\le n\le 10^5$，$1\le m\le 2\times 10^7$，$1\le a_i\le 4000$，$1\le p\lt q\le 4000$，$0\le seed\lt 2^{64}$。
- 子任务 $1$（$5$ 分）：$n,m,a_i,q\le 10$。
- 子任务 $2$（$20$ 分）：$n\le 10^4$。
- 子任务 $3$（$20$ 分）：$a_i,q\le 10$。
- 子任务 $4$（$55$ 分）：无特殊限制。