1007. 小白的烦恼

题目描述

小白在望着窗外的云朵发呆，QQ的提示音打断了小白的思绪，会是谁呢，谁是他吗？QQ的提示音响起了 n 次，从 1 到 n 编号。这些消息会分别在 m 天内发出。第 i 条消息会在第 ti 天收到，如果收到了想念的人发来的消

息，心情就会增加一点，否则心情就会减少一点。具体来说，第 i 条消息会让小白在收到消息的这一天的心情值增加 ai （注意值域），每

天的心情值只受当天收到的消息的影响，每天的初始心情值为 0。小白给了你 q 次询问。每次询问小白想知道，如果他只看到了编号从 l到 r 的消息，最早哪一天他的心情值会小于等于 k。你需要告诉小白这一天的日期，如果不存在这样的一天的话，输出 −1。形式化题面：给定正整数 n, m, q，以及序列 {（ti, ai）}ni=1，其中 ti ∈

[1, m]，ai ∈ {1, −1}。

R

定义函数 f （d, L, R）= ∑ ai ⋅ [ti = d]，即仅考虑编号在 [L, R] 内

i=L

的消息时，第 d 天的总心情值。其中对于命题P，[P ] 表示：

[P ] = {

1,0,

若 P 为真若 P 为假

有 q 组询问，对于每组询问 （l, r, k），求最小的 d ∈ [1, m] 使得 f（d, l, r）≤ k。若不存在则输出 −1。

输入格式

第一行一个整数 T 表示数据组数。接下来每组：第一行三个整数 n, m, q。第二行给出 n 个整数，其中第 i 个整数表示 ti。

第三行给出 n 个整数，其中第 i 个整数表示 ai。

接下来 q 行，每行给出三个整数，l, r, k 表示一次查询。数据范围： 1 ≤ T ≤ 2000， 1 ≤ n, m, q ≤ 105，1 ≤ ti ≤ m，

∣ai ∣ = 1，1 ≤ l ≤ r ≤ n，−n ≤ k ≤ n。

数据保证所有组的 n, m, q 之和分别都小于 3 × 105。

输出格式

对于每一个询问，输出一个整数表示答案。

样例输入

2
5 3 3
2 2 3 3 2
-1 -1 -1 -1 1
1 3 -2
2 4 -2
1 5 -2
10 5 10
5 2 5 1 2 4 2 1 1 3
1 -1 -1 1 -1 1 -1 -1 1 -1
6 9 -1
8 8 -5
3 9 -1
1 1 -4
9 9 -3
2 5 -1
3 5 0
4 5 4
8 10 4
9 10 -1

样例输出

2
3
3
2
-1
2
-1
-1
2
2
1
1
3

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）