POJ3264Balanced Lineup(最基础的线段树)
2024-09-05 04:04:26
採用一维数组建树。
(由于一维数组建的是全然二叉树,时间上比用孩子节点指针建树慢。只是基本能够忽略=-=)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 0xffffff0;
int minV=INF;
int maxV=-INF;
struct Node
{
int L,R;
int minV,maxV;
int Mid()
{
return (L+R)/2;
}
};
Node tree[800010]; void BuildTree(int root,int L,int R)
{
tree[root].L=L;
tree[root].R=R;
tree[root].maxV=-INF;
tree[root].minV=INF;
if(L!=R)
{
BuildTree(2*root+1,L,(L+R)/2);
BuildTree(2*root+2,1+(L+R)/2,R);
}
} void Insert(int root, int i,int v)
{
if(tree[root].L==tree[root].R)
{
tree[root].maxV=tree[root].minV=v;
return;
}
tree[root].minV=min(tree[root].minV,v);
tree[root].maxV=max(tree[root].maxV,v);
if(i<=tree[root].Mid())
{
Insert(2*root+1,i,v);
}
else
{
Insert(2*root+2,i,v);
}
} void Query(int root,int s,int e)
{
if(tree[root].minV>=minV&&tree[root].maxV<=maxV)
{
return;
}
if(tree[root].L==s&&tree[root].R==e)
{
minV=min(tree[root].minV,minV);
maxV=max(tree[root].maxV,maxV);
return;
}
if(e<=tree[root].Mid())
{
Query(1+root*2,s,e);
}
else if(s>tree[root].Mid())
{
Query(2+root*2,s,e);
}
else
{
Query(2*root+1,s,tree[root].Mid());
Query(2*root+2,tree[root].Mid()+1,e);
}
} int main()
{
int n,q,h;
int i;
//freopen("d:\\test.txt","r",stdin);
scanf("%d%d",&n,&q);
BuildTree(0,1,n);
for( i= 1; i <= n; i++ )
{
scanf("%d",&h);
Insert(0,i,h);
}
for( i= 0; i < q; i++ )
{
int s,e;
scanf("%d%d", &s,&e);
minV= INF;
maxV= -INF;
Query(0,s,e);
printf("%d\n",maxV-minV);
}
return 0;
}
最新文章
- 【转】hive导入数据出现NULL
- springmvc中RequestMapping的解析
- hive内部表、外部表
- MapReduce——计算温度最大值 (基于全新2.2.0API)
- WPF自定义控件与样式(15)-终结篇
- 宣布在 Azure 镜像库中正式推出 Windows Server 2012 R2 并降低 Windows Azure 的实例定价
- webapi 发布接口报405错误(angularjs2.0)
- Java学习之封装
- 剑指offer(javascript实现)
- apigateway-kong(二)admin-api(结合实例比官网还详细)
- Asp.Net Core微服务初体验
- postgres跨平台开发坑之空值
- unity---背景循环滚动
- CISCO交换机-SNMP配置
- opencv2\core\cuda.hpp(106): error C2059: 语法错误:“常量”
- 解决Ubuntu无法进行SSH连接的问题(以及如何使用SSH)
- python shelve模块
- python-day02-购物车
- tomcat部署和启动3
- IOS使用mkdir创建目录
热门文章
- zabbix监控流程图
- C++ new delete(一)
- 微信小程序之裁剪图片成圆形
- nginx代理yum
- 28.	TRIGGERS ,29.	USER_PRIVILEGES,30.	VIEWS
- django下的framework
- 算法导论 第十三章 红黑树(python)-1插入
- ASP.NET MVC______VS2012
- js的几个可能不清晰的问题
- Flask--init和run启动研究---xunfeng巡风实例篇