小黑

用户名：20190341315

访问量：8022

签　名：

菜！是真的菜，水题还做不全乎！菜。

等　　级
排　　名	126
经　　验	7718
参赛次数	8
文章发表	25
年　　龄	0
在职情况	学生
学　　校	郑州商学院
专　　业	计算机科学与技术

　　自我简介：

C/C++初学菜鸟

TA的其他文章

2116: 信息学奥赛一本通T1307-高精度乘法
浏览：140

2447: 信息学奥赛一本通T1541-数列区间最大值
浏览：354

题目 2366: 信息学奥赛一本通T1456-图书管理 C++/Java
浏览：352

你可能喜欢

2447: 信息学奥赛一本通T1541-数列区间最大值

　　作者: 小黑　　　　发表时间：2021-05-16 23:43:43 浏览：354　|　评论：0　

原题链接：信息学奥赛一本通T1541-数列区间最大值

## 这就是一道线段树模板题,但这一题好像卡输入输出了,scanf,printf,居然超时了;没办法只能开挂了;
## scanf,printf
![](/image_editor_upload/20210516114158_75372.jpg)
## 输入输出挂
![](/image_editor_upload/20210516114243_66995.jpg)
###  AC代码
```javascript
#include<stdio.h>
#define N 100100
#define max(x,y) x>y?x:y
#define inf ((1<<32)-1) //int最大值 
int arr[N];
int tree[4*N];//4倍空间 
int n,m;
void bulid_t(int rt ,int start ,int end)//构建线段树 
{
	if(start == end)
	{//线段树叶子结点赋值
	//叶子结点最大值就是自己 
		tree[rt]=arr[start];
	}
	else
	{	
		int mid = (start+end) >> 1;//右移1位(除2),快一些 
		int left_son  = (rt<<1) + 1;//2*rt+1
		int right_son = (rt<<1) + 2;//2*rt+2 
		bulid_t(left_son  ,start ,mid);//找左儿子,同时给之赋值 
		bulid_t(right_son ,mid+1 ,end);//找右儿子,同时给之赋值 
		//父节点等于左右儿子中的最大值 
		tree[rt] = max(tree[left_son] , tree[right_son]);
	}	
}
int query_t(int rt ,int start ,int end ,int L ,int R)//查询[L - R]最大值 
{
	if(end < L || start > R)
	{//当前区间不在查询区间内,区间和返回-inf； 
		return -inf;
	}
	else if(start >= L && end <= R)
	{//当前区间被查询区间全部包括,区间和返回当前结点值；
		return tree[rt];
	}
	else if(start == end)
	{//当前区间为一个点,区间和返回结点值 
		return tree[rt];
	}
	else//当前区间一部分属于查询区间,另一部分不属于; 
	{
		int mid = (start + end) >> 1;
		int left_son  = (rt<<1) + 1;//2*rt+1
		int right_son = (rt<<1) + 2;//2*rt+2 
		int left_val = query_t(left_son , start , mid , L , R);
		int right_val= query_t(right_son, mid+1 , end , L , R);
		return max(left_val , right_val);//返回左右子区间最大值 
	}
}
int read()//输入挂 加快输入 
{
    char ch=' ';
    int ans=0;
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch<='9' && ch>='0')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
void out(int a)//输出挂 加快输出 
{
    if(a > 9)
    {
        out(a/10);
    }
    putchar(a%10 + '0');
}
/*
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
*/
int main()
{
	n=read();//输入挂 
	m=read();//输入挂 
	for(int i=0;i<n;++i)
	arr[i]=read();
	bulid_t(0,0,n-1);//构造线段树 
	for(int i=0;i<m;++i)
	{
		int a,b,ans;
		a=read();//输入挂 
		b=read();//输入挂 
		//因为数组arr下标从0开始,所以左右边界都要-1 
		ans=query_t(0 ,0 ,n-1 ,a-1 ,b-1);
		out(ans);//输出挂 
		putchar('\n');
	}
	return 0;
}
```

0.0分

1 人评分

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

小黑

TA的其他文章

你可能喜欢

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

C二级辅导-等差数列（C++代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

【蟠桃记】（C语言代码）

WU-格式化数据输出（C++代码）

2447: 信息学奥赛一本通T1541-数列区间最大值

评论区

精彩推荐

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

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

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

1052题解（链表操作）

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

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

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

Tom数（Java代码）

WU-IP判断（C++代码）(一种有趣的实现方法）

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

小黑

TA的其他文章

你可能喜欢

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

C二级辅导-等差数列 （C++代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

【蟠桃记】 （C语言代码）

WU-格式化数据输出 （C++代码）

2447: 信息学奥赛一本通T1541-数列区间最大值

评论区

精彩推荐

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

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

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

1052题解（链表操作）

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

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

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

Tom数 （Java代码）

WU-IP判断 （C++代码）(一种有趣的实现方法）

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

C二级辅导-等差数列（C++代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

【蟠桃记】（C语言代码）

WU-格式化数据输出（C++代码）

　　评论区

Tom数（Java代码）

WU-IP判断（C++代码）(一种有趣的实现方法）