#P11750. 「TPOI-1D」谢谢您。

「TPOI-1D」谢谢您。

题目背景

もしも もう一度 あなたに会えるなら

如果 能够再次与您相遇

たった一言伝えたい ありがとう ありがとう

我只想告诉您一句话 谢谢您 谢谢您

—— KOKIA「ありがとう…

题目描述

Misaka Mikoto 给你一个长度为 nn 的序列 [a1,,an][a_1, \dots, a_n]mm 个区间 [l1,r1],,[lm,rm][l_1,r_1], \dots, [l_m,r_m]

Misaka Mikoto 有 qq 次询问 L,R,kL, R, k,对于每一次询问,请你求出:

maxi=LRj=liri[aj=k]\max_{i=L}^R \sum_{j=l_i}^{r_i} [a_j = k]

输入格式

第一行包含三个正整数 n,m,qn, m, q

接下来一行,nn 个正整数 a1,,ana_1, \ldots, a_n

接下来 mm 行,第 ii 行包含两个正整数 li,ril_i, r_i

接下来 qq 行,每行有三个正整数 L,R,kL, R, k,依次表示每次询问。

输出格式

输出共 qq 行。第 ii 行一个整数,表示第 ii 次询问的答案。

1 1 1
1
1 1
1 1 1

1

10 6 8
1 1 2 1 3 2 1 3 2 3
1 5
2 7
3 6
4 5
7 10
5 9
1 3 3
2 4 1
5 6 1
2 2 2
4 6 3
2 5 2
1 3 1
3 5 4

1
3
1
2
2
2
3
0

15 15 15
11 14 1 5 5 5 5 4 10 2 5 1 4 5 4
10 14
2 7
7 12
6 10
4 5
5 11
3 15
3 7
3 8
1 6
8 11
14 14
5 8
8 12
4 5
8 15 2
12 13 5
8 12 5
7 12 11
7 12 10
2 11 11
10 10 10
5 13 11
11 14 11
2 4 4
13 14 1
4 8 11
7 12 5
3 5 11
10 15 11

1
3
4
1
1
1
0
1
0
1
1
0
6
0
1

20 20 20
12 1 20 1 1 11 11 1 11 12 11 17 12 1 11 12 20 12 17 17
4 7
6 7
10 20
17 19
2 4
6 6
17 19
10 12
14 15
12 13
7 19
8 16
8 11
4 6
16 18
3 8
16 20
4 5
7 10
6 19
6 8 20
2 6 12
1 3 17
4 5 12
13 14 12
2 8 11
7 11 12
3 4 20
12 15 20
19 19 1
4 4 1
1 8 1
7 15 20
2 8 17
8 16 12
4 12 1
12 17 1
4 9 11
2 7 1
1 15 17

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

提示

本题采用捆绑测试。

  • Subtask 1(5 分):n,m,q500n,m,q\le 500
  • Subtask 2(5 分):n,m,q5000n,m,q\le 5000
  • Subtask 3(5 分):序列 aa 中至多有 100100 种元素。
  • Subtask 4(5 分):序列 aa 中每种元素至多出现 1010 次。
  • Subtask 5(20 分):n,m,q5×104n,m,q\le 5\times 10^4
  • Subtask 6(20 分):n,m,q105n,m,q\le 10^5
  • Subtask 7(40 分):无特殊限制。

对于 100%100\% 数据,1n,m,q2×1051\le n,m,q\le 2\times 10^51ai,kn1\le a_i,k\le n1lirin1\le l_i\le r_i\le n1LRm1\le L\le R\le m