- 浏览: 599968 次
- 来自: ...
文章分类
最新评论
-
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 2389北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1984import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1886POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1395接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2465当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1818关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1803关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1816关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1769一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2090POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2568设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2542继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2690先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2286一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2060形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2849例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2126字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18696堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4043一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3329前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...
线段树的基本思想是将数组或序列分成多个部分(通常是二分),每个部分对应线段树的一个节点,通过节点间的合并操作,快速获取区间信息。 线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中...
在本文中,我们将深入探讨“学习凸包(五):卷包裹算法——兼解POJ1113(JAVA)”这一主题。凸包是计算机图形学、算法和数据结构领域中的一个重要概念,它指的是在一组点集中,由这些点构成的最小外接多边形。在解决...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
线段树是一种数据结构,主要用于高效地处理区间(或段)上的查询与更新操作。在题目"poj2823"中,我们看到它被应用于寻找区域间的最大值和最小值。线段树通常用于解决动态规划问题,特别是在数组或序列上执行范围...
破解poj
用java的biginteger实现的poj1001,比较简单的方法
标题中的“使用字典树和Hashtable两种方法解POJ 2503”是指通过这两种数据结构解决一个特定的编程问题。POJ是Programming Online Judge的缩写,它是一个在线的编程竞赛平台,用户可以提交代码来解决特定的算法问题。...
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
总结来说,解决“字典树练习 POJ 1056”可能需要深入理解字典树的数据结构,实现插入和查询操作,并在Java环境中编写和测试代码。对于初学者,这是一次很好的机会来提高数据结构和算法的应用能力。
【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...
【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176