题目描述
给定一个长度为 n 的序列 s。
q 次询问,每个询问形如 a b c d e f
,需要你求出下面式子的值:
$$\sum_{L=a}^{b}[e\le G(F(L,c),F(L,c+1),\cdots,F(L,d))\le f]
$$
这里 F(l,r) 表示 s 序列区间 [l,r] 中不同的数的个数,G(x1,x2,⋯,xk) 表示 x1,x2,⋯,xk 中不同的数的个数。
输入格式
第一行两个整数 n,q,表示序列长度与命令次数。
第二行输入 n 个整数,第 i 个数表示 si。
下面 q 行,每行输入 6 个数 a′,b′,c′,d′,e,f。令上一次询问的答案为 lastans(特别的,若这是第一次询问,则 lastans=0),则本次询问中
a=(a′+lastans)modn+1
b=(b′+lastans)modn+1
c=(c′+lastans)modn+1
d=(d′+lastans)modn+1
注意,你需要将 a,b,c,d 重新排序使得 a≤b≤c≤d。
输出格式
对于每次询问,依次输出答案。
3 1
2020 2021 2020
3 3 2 2 1 1
1
10 3
2 2 4 3 5 3 5 4 1 2
3 5 2 4 1 2
5 7 2 9 2 4
1 3 1 8 1 3
2
4
4
提示
【样例一解释】
第一次询问中,a=1,b=1,c=3,d=3,e=1,f=1。
不难得到 G(F(1,3))=1,且 e≤G(F(1,3))≤f,所以答案为 1。
【样例二解释】
| 询问编号 | a | b | c | d | e | f |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| ① | 3 | 4 | 5 | 6 | 1 | 2 |
| ② | 2 | 5 | 8 | 10 | 2 | 4 |
| ③ | 3 | 6 | 6 | 8 | 1 | 3 |
【数据范围】
本题采用捆绑测试。
- Subtask1(10pts):n,q≤500,1≤si≤106;
- Subtask2(15pts):n,q≤3×103;
- Subtask3(20pts):b−a≤20;
- Subtask4(25pts):n,q≤105;
- Subtask5(30pts):无特殊限制。
对于 100% 的数据满足,1≤n,q≤3×105,0≤∣si∣≤109,对于所有询问,1≤a,b,c,d≤n,0≤e≤f≤n。
【提示】
-
本题中,[x≤y≤z] 表示 y 是否 ∈[x,z]。如果在该区间内,则值为 1;否则为 0。
-
输入量较大,请采用较快的读入方式。