zkw式线段树解决RMQ问题,只需查询,不用更新,很简单,ps: 为什么C++比gcc快那么多啊?gcc提交3047ms,用C++
的话,只需1329ms。
#include <stdio.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)
#define inf 20000000
#define N 50001
struct tree_node
{
int min, max;
};
struct tree_node tree[131072];
int cow[N];
int n, M;
int min_h, max_h;
void build_tree()
{
int i;
for (M = 1; M < (n+2); M <<= 1);
//存储数据的叶子节点
for (i = 1; i <= n; i++) {
tree[i+M].min = tree[i+M].max = cow[i];
}
//不用的叶子节点
for (i = n+1; i%M != 1; i++) {
tree[(i%M)+M].min = inf;
tree[(i%M)+M].max = -1;
}
//分支节点
for (i = M-1; i > 0 ; i--) {
tree[i].min = MIN(tree[i<<1].min, tree[(i<<1)+1].min);
tree[i].max = MAX(tree[i<<1].max, tree[(i<<1)+1].max);
}
}
void query(int s, int t)
{
max_h = -1;
min_h = inf;
for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
if (~s&1) {
max_h = MAX(max_h, tree[s^1].max);
min_h = MIN(min_h, tree[s^1].min);
}
if (t&1) {
max_h = MAX(max_h, tree[t^1].max);
min_h = MIN(min_h, tree[t^1].min);
}
}
}
int main()
{
int i, q, s, t;
scanf("%d %d", &n, &q);
for (i = 1; i <= n; i++) {
scanf("%d", cow+i);
}
build_tree();
while (q--) {
scanf("%d %d", &s, &t);
query(s, t);
printf("%d\n", max_h-min_h);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1739064
POJ3468,线段树处理,注意longlongint
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
NULL 博文链接:https://128kj.iteye.com/blog/1705139
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论