第十二届蓝桥杯 2021年国赛真题 (Java 大学C组)
问题描述
小蓝发现了一个有趣的数列，这个数列的前几项如下：
1 , 1 , 2 , 1 , 2 , 3 , 1 , 2 , 3 , 4 , . . .
小蓝发现，这个数列前 1 项是整数 1 ，接下来 2 项是整数 1 至 2 ，接下来 3 项是整数 1 11 至 3 ，接下来 4 项是整数 1 至 4 ，依次类推。
小蓝想知道，这个数列中，连续一段的和是多少。
输入格式：
接下来的第一行输入一个整数 T ，表示询问个数。
接下来 T 行,每行包含一组询问，每行两个变量 a 与 b ，表示 查询数列中第 a 个数 到 第 b 个数的和
示例：
输入：
3
1 1
1 3
5 8
输出：
1
4
8
范围：
对于10%的评测用例 1
对于40%的评测用例 1≤T≤1000,1≤a≤b≤10**6
对于70%的评测用例 1≤T≤10000,1≤a≤b≤10**9
对于80%的评测用例 1≤T≤1000,1≤a≤b≤10**12
对于90%的评测用例 1≤T≤10000,1≤a≤b≤10**12
对于所有评测用例 1≤T≤100000,1≤a≤b≤10**12
首先考虑用前缀和，但是区间太大，数组也太大，所以可以变形为
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 ...
同时我们发现每一行的和，刚好等于它在原数列中最后的一个位置
每行和 1 1 //原数列第 1 个数是这一行最后一个 1 2 3 //原数列第 3 个数是这一行最后一个 1 2 3 6 //原数列第 6 个数是这一行最后一个 1 2 3 4 10 //原数列第 10 个数是这一行最后一个 1 2 3 4 5 15 //原数列第 15 个数是这一行最后一个 ...
对于 原数列 第 p 个数，二分查找 找到 每行和 中第 i 个数比它小，第 i+1 个数比它大。则第 p 个数必然在第 i+1 行。
同时，第 p 个数在第 i+1 行中的第 p-i 个。
例子：
每行和 行 1 1 1 1 2 3 2 1 2 3 6 3 1 2 3 4 10 4 1 2 3 4 5 15 5 ... 如果 p = 5 则 p 在 第 3 行 每行和为 6 的行 同时 p(5) 在该行的第 p-i(5-3=2) 的位置
这样只需要确定该数 在 该行的位置 + 之前所有的总和，即可求得从 开始 到该数的全部和
用大的数的全部和 - 小的数的全部和 = 所求值 (注意，小的数不包含它本身，大的数包含)
整体思路如此，下面上代码
public class App {
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long arr[][] = new long[n][2];
long max = 0;
//获取输入，存入 arr[][] 中
for(int i=0; imax){
break;
}
}
long qian[] = new long[len];//前缀和
for(int i=1;i
整体时间复杂度能够快速求出值，
但是空间复杂度有些大，不过想不出更优解决方案了。
