计科余定成

用户名：dotcpp0598358

访问量：15777

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

魔板（BFS+map去重）
浏览：83

家庭问题(并查集+哈希表计数)
浏览：96

围成面积（搜索）
浏览：144

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2021年第十二届国赛真题-123（二分+前缀和）

　　作者: 计科余定成　　　　发表时间：2023-03-18 18:56:17 浏览：398　|　评论：0　

原题链接：蓝桥杯2021年第十二届国赛真题-123

#### 解题思路
对于1，2，3，4，5，6，..., n
我们用数组$$s_n$$表示前$$n$$项和，使用数组$$sum_n$$表示数组$$s$$前$$n$$项和;
初始化：
```cpp
void init() {
	for (int i = 1; i < N; i++) {
		s[i] = s[i - 1] + i;
		sum[i] = sum[i - 1] + s[i];
	}
}
```
每次查询 l 和 r 时，使用二分查找大于$$s_i$$的最小下标fl和fr;
二分查找：
```cpp
ll find(ll x) {
	ll l = 1, r = N - 5;
	ll mid;
	while (l <= r) {
		mid = l + ((r - l) >> 1);
		if (s[mid] >= x) r = mid - 1;
		else l = mid + 1;
	}
	return l;
}
```

![](/image_editor_upload/20230318/20230318064324_25174.png)

如上图所示：那么区间l到r的值即为：
$$sum[fr] - sum[fl - 1] - s[l - 1 - s[fl - 1]] - s[fr] + s[r - s[fr - 1]]$$

完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 15e5 + 5;
ll s[N];
ll sum[N];
void init() {
	for (int i = 1; i < N; i++) {
		s[i] = s[i - 1] + i;
		sum[i] = sum[i - 1] + s[i];
	}
}
ll find(ll x) {
	ll l = 1, r = N - 5;
	ll mid;
	while (l <= r) {
		mid = l + ((r - l) >> 1);
		if (s[mid] >= x) r = mid - 1;
		else l = mid + 1;
	}
	return l;
}
ll t, l, r;
int main() {
	init();
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld%lld", &l, &r);
		int fl = find(l);
		int fr = find(r);
		ll ans = sum[fr] - sum[fl - 1] - s[l - 1 - s[fl - 1]] - s[fr] + s[r - s[fr - 1]];
		printf("%lld\n", ans);
	}
	return 0;
}
```

0.0分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

The 3n + 1 problem （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2021年第十二届国赛真题-123（二分+前缀和）

评论区

精彩推荐

人见人爱A+B （C语言代码）

Pascal三角（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-数字母（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

循环入门练习5 （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

The 3n + 1 problem （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2021年第十二届国赛真题-123（二分+前缀和）

评论区

精彩推荐

人见人爱A+B （C语言代码）

Pascal三角 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-数字母 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

循环入门练习5 （C语言代码）

　　评论区

Pascal三角（C语言代码）

C语言训练-数字母（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）