4393. [HNOI2016] 序列

【题目背景】

简单数据结构。

【题目描述】

给定一个长度为 $n$ 的序列，$m$ 次询问，每次询问给出 $[L_i,R_i]$，求出所有满足 $L_i\le l\le r\le R_i$ 的所有子区间 $[l,r]$ 最小值之和。大样例

【输入格式】

第一行三个整数 $n,m,type$，其中 $type$ 的作用在于询问的给出形式。

第二行 $n$ 个整数，表示数列 $a_i$。

若 $type=0$，则接下来 $m$ 行，每行两个数 $L_i,R_i$，表示询问的区间 $L_i,R_i$。

若 $type=1$，则数据按照如下代码生成：

namespace gen{
	typedef unsigned long long ull;
	ull s,a,b,c,lastans=0;
	ull rand(){
		return s^=(a+b*lastans)%c;
	}
};

其中，$s,a,b,c$ 的初始值在第三行给出，满足 $s,a,b$ 均在 $[0,10^9]$ 之间，$c$ 在 $[1,10^9]$ 之间。lastans 表示上次询问的答案转化为 unsigned long long 类型后的值，第一次询问时值为 $0$。

每次询问时，你可以通过下面的方式生成 $l$ 和 $r$：

l=gen::rand()%n+1;
r=gen::rand()%n+1;
if(l>r) std::swap(l,r);

【输出格式】

一行一个整数，表示每次询问的答案转成 unsigned long long 类型后的异或和。

【样例输入1】

5 5 0
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

【样例输出1】

28

【样例输入2】

6 5 1
1 1 4 5 1 4
19 19 8 10

【样例输出2】

6

【数据规模与约定】

【来源】

HNOI2016。