#P17622. [Ynoi2007] rvrewsus

[Ynoi2007] rvrewsus

P7721 [Ynoi2007] rvrewsus

5s 512M

题目描述

给定一个数组 a1,a2,…,ana_1,a_2,\dots,a_n 以及正整数 bb,请回答 qq 组 [l,r,L,R][l,r,L,R] 形式的询问。

∧\land 符号表示逻辑与。

在这询问里,你需要:

  1. 创建无重集合 S={ai:l≤i≤r∧L≤ai≤R}S=\{a_i:l\le i\le r\land L\le a_i\le R\};

  2. 定义函数 $r(k)=\begin{cases}\min (x:x\in S)&k=0\\\min(x:x\in S\land r(k-1)<x)&k\neq0\end{cases}$;

  3. 求以下表达式值:

∑k=0∣S∣−1r(k)bk\sum_{k=0}^{|S|-1}r(k)b^k

所有答案对 333333333333333397333333333333333397(一个质数)取模。

输入格式

第一行三个整数 n,b,qn,b,q。

接下来一行 nn 个整数 a1,a2,…,aNa_1,a_2,\dots,a_N。

接下来 qq 行每行四个正整数 l,r,L,Rl,r,L,R,表示一组询问。

输出格式

输出 qq 行,代表对应询问答案。

输入输出样例 #1

输入 #1

5 33333333333333333 5
333 33 333 33333 3
4 5 0 100000
2 4 0 100000
1 3 0 100000
1 5 0 100000
4 4 0 100000

输出 #1

99999999999776691
30000000001494126
99999999999997821
332333333323322794
33333

输入输出样例 #2

输入 #2

33 33333 33
333333333 333333333333 33333333333333 33333333333 33333 333333333333333 33 333 333 333333 3 333333333 3333333 3 333333333 33333333333333 333333333333333 33333333333333 333333 33333333333333 33333333333333 33333333 333333333333333 33333333 33333333 33333 33333333 3333333 33333333 33333333 3333333 33333333 333333333
1 33 3 333333333333333
13 15 333333 333333333333333
15 18 3333333333333 33333333333333
13 30 3 33333333333
3 27 33333 3333333333
25 28 333333 33333333333333
6 30 333 33333333333333
4 32 33333333333333 333333333333333
4 13 33333333 33333333333333
14 28 3333333 33333333333333
17 31 3 33333333333333
21 32 33333 333333333333333
1 2 333333 3333333333333
1 10 3333333 333333333
6 15 33333 333333
5 13 33333 333333333333
4 17 3333333333333 33333333333333
8 28 33333 33333333333333
14 15 3333 333333333333
15 26 333333333 333333333333333
17 25 33333333 333333333333333
13 25 333333 333333333333
8 33 333333 33333333333333
16 17 33333333333 333333333333
24 26 3333333333 333333333333333
23 24 3 333
28 29 333333333 33333333333333
17 25 33 3333
6 7 333333 33333333333
7 12 3333 33333
17 28 3333333333333 3333333333333
11 17 333333 333333
11 17 333333 333333

输出 #2

5381244831822484
11111003322222
33333333333333
187453349930639529
209467718277680736
1111103322222
38102950517542902
111033333333320121
1111100333322222
271584825962251762
259223255302742554
221819973789694611
11111000333322222
333333333
333333
312336974059655685
33333333333333
214323286321378781
333333333
74099999892219735
74099999592219735
12336407395622288
70337133069920353
0
0
0
0
0
0
0
0
0
0

说明/提示

  • Subtask 1(2 pts):n,q≤5000n,q\le5000;
  • Subtask 2(3 pts):n,q≤5×104n,q\le5\times10^4;
  • Subtask 3(3 pts):R−L≤300R-L\le 300;
  • Subtask 4(7 pts):b=1b=1;
  • Subtask 5(7 pts):所有 aia_i 互不相同;
  • Subtask 6(11 pts):L=0,R=333333333333333396L=0,R=333333333333333396;
  • Subtask 7(67 pts):无额外限制。

对于所有数据,1≤n,q≤2×1051\le n,q\le2\times10^5,1≤l≤r≤n1\le l\le r\le n,0≤b,ai,L,R<3333333333333333970\le b,a_i,L,R<333333333333333397。