P2030 - [蓝桥杯2022初赛] 推导部分和

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：555 通过：153

对于一个长度为N 的整数数列A[1], A[2], ... , A[N]，小蓝想知道下标 l 到 r 的部分和 A[l] + A[l+1] + ... + A[r] 是多少？
然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M 个部分和的值。
其中第i 个部分和是下标 li 到 ri 的部分和：A[li] + A[li+1] + ... + A[ri]，值是Si。

第一行包含3个整数N、M和Q，分别代表数组长度、已知的部分和数量和询问的部分和数量。
接下来M行，每行包含3个整数 li, ri, Si。
接下来Q行，每行包含2个整数 l 和 r，代表小蓝想知道的部分和。
10%的测试数据：1≤N,M,Q≤10, -100≤Si≤100;
20%的测试数据：1≤N,M,Q≤20, -1000≤Si≤1000;
30%的测试数据：1≤N,M,Q≤50, -10000≤Si≤10000;
40%的测试数据：1≤N,M,Q≤1000, -10^6≤Si≤10^6;
60%的测试数据：1≤N,M,Q≤10000, -10^9≤Si≤10^9;
100%的测试数据：1≤N,M,Q≤10^5, -10^12≤Si≤10^12, 1≤li≤ri≤N，1≤l≤r≤N。
数据保证没有矛盾。

对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输出UNKNOWN。

15
6
UNKNOWN

进阶题并查集搜索

2030: [蓝桥杯2022初赛] 推导部分和

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签