解题报告:线段树的入门题目,这里只需要两种操作“建树”、“查询”。
线段树解题的关键是节点存放的信息
#include <cstdio> #include<cstring> #include<algorithm> #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b #define mid(a,b) (a+b)>>1 #define L(a) a<<1 #define R(a) a<<1|1 const int MAX = 200000+10; const int INF = 0x3fffffff; int h[MAX],mini,maxn; struct node { int l,r; int min,max; }; node a[MAX]; void build(int t,int l,int r) { a[t].l=l; a[t].r=r;//当初这忘记了记录 if( l != r ) { int m=mid(l,r); build(L(t),l,m);//应该是L而不是数字1; build(R(t),m+1,r); a[t].min=min(a[L(t)].min,a[R(t)].min); a[t].max=max(a[L(t)].max,a[R(t)].max); } else { a[t].min=h[l]; a[t].max=h[l]; } } void query(int t,int l,int r) { if(a[t].min >= mini && a[t].max <= maxn) return ; int m=mid(a[t].l,a[t].r); if(a[t].l==l&&a[t].r==r) { mini=min(mini,a[t].min); maxn=max(maxn,a[t].max); } else if(l>m)//注意L表示的是什么 { query(R(t),l,r); } else if(r<=m) { query(L(t),l,r); } else { query(R(t),m+1,r); query(L(t),l,m); } } int main() { int n,q,l,r; while(scanf("%d%d",&n,&q)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&h[i]); build(1,1,n); for(int i=0;i<q;i++) { maxn=-INF; mini=INF; scanf("%d %d",&l,&r); query(1,l,r); printf("%d\n",maxn-mini); } } return 0; }
相关推荐
北大POJ3274-Gold Balanced Lineup 解题报告+AC代码
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题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1739064
poj 1989 The Cow Lineup.md
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ3468,线段树处理,注意longlongint
大量线段树题目 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 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
NULL 博文链接:https://200830740306.iteye.com/blog/603493