#6057. 「HNOI2016」序列 数据加强版

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

给定长度为 n 的序列: a_1, a_2, \cdots , a_n ,记为 a[1 \colon n] 。类似地, a[l \colon r] 1 \leq l \leq r \leq n )是指序列: a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r 。若 1\leq l \leq s \leq t \leq r \leq n ,则称 a[s \colon t] a[l \colon r] 的子序列。

现在有 q 个询问,每个询问给定两个数 l r 1 \leq l \leq r \leq n ,求 a[l \colon r] 的不同子序列的最小值之和。例如,给定序列 5, 2, 4, 1, 3 ,询问给定的两个数为 1 3 ,那么 a[1 \colon 3] 6 个子序列 a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] ,这 6 个子序列的最小值之和为 5+2+4+2+2+2=17

输入格式

输入文件的第一行包含两个整数 n q ,分别代表序列长度和询问数。

接下来一行,包含 n 个整数,以空格隔开,第 i 个整数为 a_i ,即序列第 i 个元素的值。

接下来一行四个整数 A,B,C,P 表示询问的生成方式。

由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。

输入压缩方法是:读入 4 个整数 A,B,C,P ,每次询问调用以下函数生成 l r

int A, B, C, P;
long long lastAns;

inline int rnd() {
    return A = (A * B + (C ^ (int)(lastAns & 0x7fffffffLL)) % P) % P;
}

其中 \text{lastAns} 表示上次询问的答案,第一个询问 \text{lastAns} 0

每次询问时的调用方法为:

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

输出格式

输出共一行一个整数,表示所有询问的答案之和模 1000000007 的值。

由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。

输出压缩方法是:输出所有询问的答案之和模 1000000007 的值。

样例

样例输入 1

4 9
-216942799 -383604709 -171536855 -527908982 
2307368 41 7882044 45000701

样例输出 1

480963324

样例输入 2

5 8
-241312314 -489291255 -247844393 -39976393 -333832198 
26228886 3 3541696 45000847

样例输出 2

37657340

数据范围与提示

对于所有数据, 1 \leq n \leq 100000 ,1\leq q \leq 10^7,|a_i| \leq 10^9 ,保证 0\leq A<P,0\leq C<2^{31}-1,P(B+1)<2^{31}-1