分数: 466 分
问题陈述
高桥在一家大型图书馆担任图书管理员。图书馆有 N 书架上排成一排,编号为书 1,书 2, \ldots,书 N 从左到右。
目前,所有书籍均已借出,书架上没有任何书籍。预定还书日期 i (1 \leq i \leq N) 是一天 D_i。预订 i 当天被退回并放回货架 D_i,并从那时起一直保留在架子上。也就是说,书 i 当天上架 T 当且仅当 D_i \leq T.
高桥收到 Q 图书馆顾客的询问。的 j- 第一个查询 (1 \leq j \leq Q) 指定一天 T_j 和一系列书号 [L_j, R_j] (包括两端)。高桥需要确定范围内的书籍数量 [L_j, R_j] 截至当日已上架 T_j。具体来说,让 c_j 为书籍数量 i 满意 L_j \leq i \leq R_j 和 D_i \leq T_j.
不过图书馆的借阅车最多可容纳 K 书籍。如果 c_j \leq K,所有书籍都可以装入购物车并借出,但如果 c_j > K,无法处理请求,因为购物车无法容纳书籍。
对于每个查询,输出 c_j if c_j \leq K,或 -1 if c_j > K.
请注意,每个查询都是独立于其他查询的。任何查询实际上都不会签出任何书籍,并且每次查询的书架上书籍的状态都是相同的。
约束
- 1 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq Q \leq 10^5
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
- 所有输入值均为整数。
输入
N K Q D_1 D_2 \ldots D_N L_1 R_1 T_1 L_2 R_2 T_2 \vdots L_Q R_Q T_Q
- 第一行包含三个空格分隔的整数: N 代表图书数量, K 代表借阅车可容纳的最大图书数量,以及 Q 代表查询数量。
- 第二行包含空格分隔的整数 D_1, D_2, \ldots, D_N 代表每本书的预定归还日期。
- 以下 Q 行包含每个查询的信息。
- 的 (2 + j)- 第行 (1 \leq j \leq Q) 包含三个空格分隔的值:左端点 L_j,右端点 R_j,以及查询日期 T_j 为 j-第一个查询。
输出
输出 Q 行。的 j- 第行 (1 \leq j \leq Q)应包含以下问题的答案 j- 第一个查询。具体来说,如果书籍数量 c_j 在范围内 [L_j, R_j] 满意 D_i \leq T_j 最多是 K,输出 c_j;如果超过 K,输出 -1.
示例输入 1
5 3 3 3 1 4 1 5 1 5 2 2 4 4 1 3 3
示例输出 1
2 3 2
示例输入 2
5 2 3 3 1 4 1 5 1 5 4 1 2 3 3 5 1
示例输出 2
-1 2 1
示例输入 3
10 3 5 5 2 8 1 3 7 4 6 9 10 1 10 5 3 7 4 1 5 2 2 8 7 6 10 10
示例输出 3
-1 3 2 -1 -1
示例输入 4
20 5 8 15 3 20 7 12 1 18 9 4 11 6 14 2 17 8 19 5 10 16 13 1 20 10 1 10 5 5 15 12 11 20 15 1 5 3 8 14 9 3 18 7 1 20 20
示例输出 4
-1 3 -1 -1 1 4 -1 -1
示例输入 5
1 1 1 1000000000 1 1 1000000000
示例输出 5
1