蓝桥杯2022年第十三届省赛真题-推导部分和

对于一个长度为 N 的整数数列 A₁, A₂, · · · A_N，小蓝想知道下标 l 到 r 的部分和是多少？

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M 个部分和的值。其中第 i 个部分和是下标 l_i 到 r_i 的部分和，值是 S _i 。

第一行包含 3 个整数 N、M 和 Q。分别代表数组长度、已知的部分和数量和询问的部分和数量。

接下来 M 行，每行包含 3 个整数 l_i ,r_i , S _i。

接下来 Q 行，每行包含 2 个整数 l 和 r ，代表一个小蓝想知道的部分和。

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2

15
6
UNKNOWN

对于 10% 的评测用例，1 ≤ N, M, Q ≤ 10，−100 ≤ S _i ≤ 100。

对于 20% 的评测用例，1 ≤ N, M, Q ≤ 20，−1000 ≤ S _i ≤ 1000。

对于 30% 的评测用例，1 ≤ N, M, Q ≤ 50，−10000 ≤ S _i ≤ 10000。

对于 40% 的评测用例，1 ≤ N, M, Q ≤ 1000，−10⁶ ≤ S _i ≤ 10⁶。

对于 60% 的评测用例，1 ≤ N, M, Q ≤ 10000，−10⁹ ≤ S _i ≤ 10⁹。

对于所有评测用例，1 ≤ N, M, Q ≤ 10⁵，−10¹² ≤ S _i ≤ 10¹²，1 ≤ l_i ≤ r_i ≤ N， 1 ≤ l ≤ r ≤ N。数据保证没有矛盾。