`
128kj
  • 浏览: 599968 次
  • 来自: ...
社区版块
存档分类
最新评论

线段树入门学习(三)懒操作(兼解POJ1823) 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)个节点的信息就成为必要。

    以相同的方式更新某区间时,并不去真正更新其子区间,而是以某种方式把这个操作记录下来,等下一次访问到该区间并需要访问其子区间时,在访问的同时把子区间的值进行更改!这就称为懒操作。代码如下:

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
源码下载:
  • 大小: 5.4 KB
0
0
分享到:
评论

相关推荐

    线段树入门学习(二)(兼解POJ3468) JAVA

    在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...

    线段树练习POJ 3264

    线段树的基本思想是将数组或序列分成多个部分(通常是二分),每个部分对应线段树的一个节点,通过节点间的合并操作,快速获取区间信息。 线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中...

    学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)

    在本文中,我们将深入探讨“学习凸包(五):卷包裹算法——兼解POJ1113(JAVA)”这一主题。凸包是计算机图形学、算法和数据结构领域中的一个重要概念,它指的是在一组点集中,由这些点构成的最小外接多边形。在解决...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    POJ 1751 求最小生成树prim算法(JAVA)

    标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    poj2823.cpp.tar.gz_线段树

    线段树是一种数据结构,主要用于高效地处理区间(或段)上的查询与更新操作。在题目"poj2823"中,我们看到它被应用于寻找区域间的最大值和最小值。线段树通常用于解决动态规划问题,特别是在数组或序列上执行范围...

    破解poj

    破解poj

    poj1001java biginteger

    用java的biginteger实现的poj1001,比较简单的方法

    使用字典树和Hashtable两种方法解POJ 2503(JAVA)

    标题中的“使用字典树和Hashtable两种方法解POJ 2503”是指通过这两种数据结构解决一个特定的编程问题。POJ是Programming Online Judge的缩写,它是一个在线的编程竞赛平台,用户可以提交代码来解决特定的算法问题。...

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    POJ2528-Mayor's posters【区间映射压缩(离散化)+线段树】

    POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========&gt; 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573

    字典树练习 POJ 1056

    总结来说,解决“字典树练习 POJ 1056”可能需要深入理解字典树的数据结构,实现插入和查询操作,并在Java环境中编写和测试代码。对于初学者,这是一次很好的机会来提高数据结构和算法的应用能力。

    凸包练习: POJ 2187(JAVA)

    【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...

    北大poj JAVA源码

    【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...

    poj部分源码--Java

    poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176

Global site tag (gtag.js) - Google Analytics