- 浏览: 580741 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
继续上文"线段树入门学习(二)" http://128kj.iteye.com/blog/1739064
请先看题POJ1823:
旅馆有三种操作:1入住,同时给你两个数i,M,其中i表示连续房间的起始房号,M表示房间数量;2退房,同时给你两个数i,M,其中i表示连续房间的起始房号;3查询,要求输出整个旅馆中,房号相连的最大空房间数量。
样例:
Sample Input
12 10 (房间号1 -12,有10个操作)
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3
Sample Output
12
4
4
6
10
网上大家都用线段树来解这道题.
线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段,因而常用于解决数列维护问题,树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。
它基本能保证每个操作的复杂度为O(logN)。
当用户修改一个区间的值时,如果连同其子孙全部修改,则改动的节点数必定会远远超过O(log n)个。因而,如果要想把区间修改操作也控制在O(log n)的时间内,只修改O(log n)个节点的信息就成为必要。
以相同的方式更新某区间时,并不去真正更新其子区间,而是以某种方式把这个操作记录下来,等下一次访问到该区间并需要访问其子区间时,在访问的同时把子区间的值进行更改!这就称为懒操作。代码如下:
具体解答请看下面AC过的代码:
以上代码参考了:http://sbp810050504.blog.51cto.com/2799422/1023633
源码下载:
请先看题POJ1823:
旅馆有三种操作:1入住,同时给你两个数i,M,其中i表示连续房间的起始房号,M表示房间数量;2退房,同时给你两个数i,M,其中i表示连续房间的起始房号;3查询,要求输出整个旅馆中,房号相连的最大空房间数量。
样例:
Sample Input
12 10 (房间号1 -12,有10个操作)
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3
Sample Output
12
4
4
6
10
网上大家都用线段树来解这道题.
线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段,因而常用于解决数列维护问题,树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。
它基本能保证每个操作的复杂度为O(logN)。
当用户修改一个区间的值时,如果连同其子孙全部修改,则改动的节点数必定会远远超过O(log n)个。因而,如果要想把区间修改操作也控制在O(log n)的时间内,只修改O(log n)个节点的信息就成为必要。
以相同的方式更新某区间时,并不去真正更新其子区间,而是以某种方式把这个操作记录下来,等下一次访问到该区间并需要访问其子区间时,在访问的同时把子区间的值进行更改!这就称为懒操作。代码如下:
void push_down(int id,int sign){//sign=1表示入住,sign=0表示退房 tree[id].occ=-1;//更新自己和孩子的懒操作标记 tree[id<<1].occ=tree[id<<1|1].occ=sign; if(sign==1){ //更新子节点 tree[id<<1].cl=tree[id<<1|1].cl=tree[id<<1].cr=tree[id<<1|1].cr=0; tree[id<<1].max=tree[id<<1|1].max=0; }else{ int len=tree[id<<1].rr-tree[id<<1].ll+1; tree[id<<1].cl=tree[id<<1].cr=len; tree[id<<1].max=len; len=tree[id<<1|1].cr=tree[id<<1|1].rr-tree[id<<1|1].ll+1; tree[id<<1|1].cl=len; tree[id<<1|1].max=len; } }
具体解答请看下面AC过的代码:
import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStreamWriter; import java.io.IOException; class Tree{ int ll,rr,mid; /* max表示结点管理的区间最大的连续子区间有多大,cl表示区间的最左边有多少连续的区间, cr表示区间的右边有多少连续的子区间 */ int max,cl,cr; int occ;//occ==0表示空,occ=1表示全部入住,occ=-1表示有空有住 } public class Main{ Tree tree[]; public Main(){ tree=new Tree[32766]; for(int i=0;i<tree.length;i++){ tree[i]=new Tree(); } } void build(int id,int ll,int rr){ tree[id].ll=ll;tree[id].rr=rr;tree[id].mid=(ll+rr)>>1; //刚开始建树,都是空的,所以可以这样写 tree[id].max=tree[id].cl=tree[id].cr=rr-ll+1; tree[id].occ=0; if(ll==rr)return; build(id<<1,ll,tree[id].mid); build(id<<1|1,tree[id].mid+1,rr); } //懒操作 void push_down(int id,int sign){//sign=1表示入住,sign=0表示退房 tree[id].occ=-1;//更新自己和孩子的懒操作标记 tree[id<<1].occ=tree[id<<1|1].occ=sign;//表示全空或者全住 if(sign==1){ tree[id<<1].cl=tree[id<<1|1].cl=tree[id<<1].cr=tree[id<<1|1].cr=0; tree[id<<1].max=tree[id<<1|1].max=0; }else{ int len=tree[id<<1].rr-tree[id<<1].ll+1; tree[id<<1].cl=tree[id<<1].cr=len; tree[id<<1].max=len; len=tree[id<<1|1].cr=tree[id<<1|1].rr-tree[id<<1|1].ll+1; tree[id<<1|1].cl=len; tree[id<<1|1].max=len; } } //更新区间 void update(int id ,int ll,int rr,int sign){//sign=1入住,sign=0表示退房 if(tree[id].ll==ll&&tree[id].rr==rr){//找到区间 tree[id].occ=sign; int len=tree[id].rr-tree[id].ll+1; if(sign==1) len=0; tree[id].cl=tree[id].cr=len; tree[id].max=len; return; } if(tree[id].occ==1) push_down(id,1);//执行到这行代码意味着 tree[id]的子区间要更改了,所以需要执行一次push_down if(tree[id].occ==0) push_down(id,0); if(rr<=tree[id].mid){ update(id*2,ll,rr,sign); }else if(ll>tree[id].mid){ update(id*2+1,ll,rr,sign); }else{ update(id*2,ll,tree[id].mid,sign); update(id*2+1,tree[id].mid+1,rr,sign); } //子区间更新了,必须更新父区间 //需要修改的就只有3个值:max,cl,cr 分别代表最长连续个数为多少,最左边有多少个空闲,最右边有多少个空闲 if(tree[id].occ==-1){//表示有空有住 if(tree[id<<1].occ==0){ tree[id].cl=tree[id*2].cl+tree[id<<1|1].cl; }else{ tree[id].cl=tree[id<<1].cl; } if(tree[id<<1|1].occ==0){ tree[id].cr=tree[id*2].cr+tree[id<<1|1].cr; }else{ tree[id].cr=tree[id<<1|1].cr; } //求tree[id].max int len=tree[id<<1].cr+tree[id<<1|1].cl; tree[id].max=Math.max(len,Math.max(tree[id<<1].max,tree[id<<1|1].max)); }else{//表示全空或者全住 int len; if(sign==1) len=0; else len=tree[id].rr-tree[id].ll+1; tree[id].max=tree[id].cl=tree[id].cr=len; } if(tree[id*2].occ==tree[id*2+1].occ) tree[id].occ=tree[id*2].occ; } int getMax(){ return tree[1].max; } public static void main(String[] args) throws IOException{ //注:用Scanner in=new Scanner(System.in)超时!!!!!!!! StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); st.nextToken(); int n= (int) st.nval; st.nextToken(); int p=(int) st.nval; Main ma=new Main(); int sign; int ll,rr; ma.build(1,1,n); for(int i=0;i<p;i++){ st.nextToken(); sign=(int) st.nval; if(sign==3){ out.printf("%d\n",ma.getMax()); }else{ st.nextToken(); ll=(int) st.nval; st.nextToken(); rr=(int) st.nval; rr=ll+rr-1; if(sign==2) sign=0; ma.update(1,ll,rr,sign); } } out.flush(); } }
以上代码参考了:http://sbp810050504.blog.51cto.com/2799422/1023633
源码下载:
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2319北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1939import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1822POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1342接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2407当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1754关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1646关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1739关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1685一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2009POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2465设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2484继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2587先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2200一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 1996形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2773例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2052字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18542堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3973一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3259前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739064
破解poj
POJ 1328 java做!雷达问题!java版本!AC答案~
用java的biginteger实现的poj1001,比较简单的方法
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1752345
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ1048,加强版的约瑟夫问题 难度中等
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
北大poj JAVA源码
最外层(总树,设为第0层)右子树的根,内1层右子树的根,内2层右子树的根….内n层右子树的根,内n层左子树的根,内n-1层左子树的根……内1层左子树的根,最外层(总树,第0层)左子树的根。把总树的左子树作为新的...
NULL 博文链接:https://128kj.iteye.com/blog/1734586
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1749213
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助