10162: 蓝桥杯 - 推导部分和
[Creator : ]
Description
对于一个长度为 $N$ 的整数数列 $A_1,A_2,…A_N$,小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum_{i=l}^r A_l + A_{l+1} + A_{l+2} + ... + A_r$ 是多少?
然而,小蓝并不知道数列中每个数的值是多少,他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j = l_i}^{r_i} A_{l_i} + A_{{l_i}+1} + A_{{l_i}+2} + ... + A_{r_i}$,值是 $S_i$。
然而,小蓝并不知道数列中每个数的值是多少,他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j = l_i}^{r_i} A_{l_i} + A_{{l_i}+1} + A_{{l_i}+2} + ... + A_{r_i}$,值是 $S_i$。
Input
第一行包含 3 个整数 $N,M,Q$,分别代表数组长度、已知的部分和数量和询问的部分和数量。
接下来 $M$ 行, 每行包含 3 个整数 $l_i,r_i,S_i$。
接下来 $Q$ 行,每行包括 2 个整数 $l,r$,代表一个小蓝想知道的部分和。
接下来 $M$ 行, 每行包含 3 个整数 $l_i,r_i,S_i$。
接下来 $Q$ 行,每行包括 2 个整数 $l,r$,代表一个小蓝想知道的部分和。
Output
对于每个询问, 输出一行包含一个整数表示答案。
如果答案无法确定, 输出 UNKNOWN。
如果答案无法确定, 输出 UNKNOWN。
Constraints
$1≤N,M,Q≤10^5$
$-10^{12} \leq S_{i} \leq 10^{12}$
$1 \leq l_{i} \leq r_{i} \leq N$
$≤l≤r≤N$
$-10^{12} \leq S_{i} \leq 10^{12}$
$1 \leq l_{i} \leq r_{i} \leq N$
$≤l≤r≤N$
Sample 1 Input
5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2
Sample 1 Output
15
6
UNKNOWN