← 返回题目列表

AtCoder · icpc2013spring_i

I. 第 J 个数字

中文机器翻译题面 查看原题

问题陈述

你被给予 N 空数组, t_1, ..., t_n。首先,你执行 M 查询如下。

  • 添加一个值 v 到数组 t_i (a \leq i \leq b)
接下来,您处理 Q 以下输出查询。
  • 输出 j- 对所有值进行排序的序列号 t_i (x \leq i \leq y)


输入

数据集的格式如下。

N M Q
a_1 b_1 v_1
...
a_M b_M v_M
x_1 y_1 j_1
...
x_Q y_Q j_Q

第一行包含三个整数 N (1 \leq N \leq 10^9), M (1 \leq M \leq 10^5)和 Q (1 \leq Q \leq 10^5)。以下每一项 M 行由三个整数组成 a_i, b_i 和 v_i (1 \leq a_i \leq b_i \leq N, 1 \leq v_i \leq 10^9)。最后是以下内容 Q 行给出输出查询列表,每行由三个整数组成 x_i, y_i 和 j_i (1 \leq x_i \leq y_i \leq N, 1 \leq j_i \leq Σ_{x_i \leq k \leq y_i} |t_k|).

输出

对于每个输出查询,在一行中打印 j- 第一个数字。

示例输入 1

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

样本输入 1 的输出

2

之后 M执行第一个查询,每个 t_i 如下:

[1,3], [1], [1,2], [1,1,2], [1,1]
序列排序值 t_1, t_2 和 t_3 是 [1,1,1,2,3]。在数列中,第 4 个数字是 2。

示例输入 2

10 4 4
1 4 11
2 3 22
6 9 33
8 9 44
1 1 1
4 5 1
4 6 2
1 10 12

样本输入 2 的输出

11
11
33
44