计科余定成

用户名：dotcpp0598358

访问量：15775

签　名：

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

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

　　自我简介：

我是余定成

TA的其他文章

蓝桥杯2016年第七届真题-密码脱落（区间DP）
浏览：208

刻录光盘（c++）
浏览：66

你可能喜欢

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

区间中最大的数（分块——优雅的暴力）

　　作者: 计科余定成　　　　发表时间：2023-03-21 13:02:47 浏览：60　|　评论：0　

原题链接：区间中最大的数

###### 解题思路：
使用分块的思想，每次暴力查询两端不完整的块和区间内的整块，时间复杂度为根号级别。
###### 参考代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

inline void write(int x) {
	if (x < 0)
		x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

inline int read() {
	int x = 0, f = 1;
	char ch;
	for (; !isdigit(ch); ch = getchar())
		f = ch == '-' ? -1 : 1;
	for (; isdigit(ch); ch = getchar())
		x = x * 10 + ch - '0';
	return x * f;
}

int n, m;
int s[N];//一个块的和
int l[N];//一个块的左端点（起始点）
int r[N];//一个块的右端点（终结点）
int a[N];//原数组
int belong[N];//第i个元素属于第belong[i]个块
int block, num; //block表示块的大小，num表示块的数量。

void build() {
	block = sqrt(n);//块的大小是根号n
	num = n / block;
	if (n % block) {
		num++;
	}//有可能n不是完全平方数，这时块数需要加一
	for (int i = 1; i <= num; i++) {
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
	}//对于左端点和右端点处理
	for (int i = 1; i <= n; i++) {
		belong[i] = (i - 1) / block + 1;
	}
	r[num] = n;
	for (int i = 1; i <= num; i++) {
		for (int j = l[i]; j <= r[i]; j++) {
			s[i] = max(s[i], a[j]);
		}
	}
}

inline int query(int x, int y) {
	int ans = 0;
	//如果区间位于一个整块内，则直接暴力查询
	if (belong[x] == belong[y]) {
		for (int i = x; i <= y; i++) {
			ans = max(ans, a[i]);
		}
		return ans;
	}
	//暴力查询两端
	for (int i = x; i <= r[belong[x]]; i++) {
		ans = max(ans, a[i]);
	}
	for (int i = l[belong[y]]; i <= y; i++) {
		ans = max(ans, a[i]);
	}
	//查询整块
	for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
		ans = max(ans, s[i]);
	}
	return ans;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
	}
	build();
	m = read();
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read();
		write(query(x, y));
		putchar('\n');
	}
	return 0;
}
```

0.0分

1 人评分

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

计科余定成

TA的其他文章

你可能喜欢

拆分位数（C语言代码）

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

C语言考试练习题_一元二次方程（C语言代码）

三进制小数（C语言代码）

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

区间中最大的数（分块——优雅的暴力）

评论区

精彩推荐

C二级辅导-计负均正（C语言代码）

C二级辅导-统计字符（C语言代码）

字符串比较（C语言代码）答案错误？？？？

printf基础练习2 （C语言代码）

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

C二级辅导-求偶数和（C语言代码）

企业奖金发放（C语言代码）

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

母牛的故事（C语言代码）

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

计科余定成

TA的其他文章

你可能喜欢

拆分位数 （C语言代码）

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

C语言考试练习题_一元二次方程 （C语言代码）

三进制小数 （C语言代码）

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

区间中最大的数（分块——优雅的暴力）

评论区

精彩推荐

C二级辅导-计负均正 （C语言代码）

C二级辅导-统计字符 （C语言代码）

字符串比较 （C语言代码）答案错误？？？？

printf基础练习2 （C语言代码）

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

C二级辅导-求偶数和 （C语言代码）

企业奖金发放 （C语言代码）

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

母牛的故事 （C语言代码）

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

拆分位数（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

三进制小数（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

C二级辅导-统计字符（C语言代码）

字符串比较（C语言代码）答案错误？？？？

C二级辅导-求偶数和（C语言代码）

企业奖金发放（C语言代码）

母牛的故事（C语言代码）