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

树状数组练习:POJ 3067

阅读更多
关于树状数组,参看:http://128kj.iteye.com/blog/1743633

POJ3067题意:
东海岸与西海岸分别有N和M个城市,现在修高速公路连接东西海岸的城市,求交点个数。



  做法:记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时,满足(x1-x2)*(y1-y2) < 0。所以,将每条路按x从小到达排序,若x相同,按y从小到大排序。 然后按排序后的公路用树状数组在线更新,求y的逆序数之和即为交点个数。

详细说明如下。 记第i条边的端点分别为xi,yi。
    由于x是从小到大排序的,假设当前我们在处理第k条边,那么第1~k-1条边的x必然是小于(等于时候暂且不讨论)第k条边的x的,那么前k-1条边中,与第k条边相交的边的y值必然大于yk的,所以此时我们只需要求出在前k-1条边中有多少条边的y值在区间[yk, M]即可,也就是求yk的逆序数,M为西岸城市个数,即y的最大值。 所以就将问题转化成区间求和的问题,树状数组解决。当两条边的x相同时,我们记这两条边的y值分别为ya,yb(ya<yb),我们先处理(x,ya),再处理(x,yb),原因很明显,因为当x相同时,这两条边是认为没有交点的,若先处理(x,yb),那么下次处理(x,ya)时,(x,ya)就会给(x,yb)增加一个逆序,也就是将这两条边做相交处理了。

样例:
Sample Input

1     (一次测试)
3 4 4  (东,西岸的城市数及总的公路数)
1 4    (公路的两端点)
2 3
3 2
3 1
Sample Output

Test case 1: 5

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;   
import java.util.Arrays;
 class Node implements Comparable{//一条公路
    int x;//公路的左端点
    int y;//另一个端点

   public int compareTo(Object b) {  
       int v=((Node)b).x;
       if(this.x==v)
         return this.y-((Node)b).y; //x相同,按y升序排序
       return this.x-((Node)b).x;//x不同,按x升序排序
    }

    public String toString(){
        return ("["+x+","+y+"]");
    }
  }

public class Main{
 private long C[];  //树状数组
 private Node[] edge;//所有公路
 private int n,m,k;  //东,西岸的城市数及总的公路数

 private int lowbit(int t){//计算C[t]展开的项数   
   return t&(-t);   
  }   

  private long Sum(int k){ //求前k项的和.   
   long sum=0;    
    while(k>0){    
       sum+=C[k];    
       k=k-lowbit(k);    
    }        
    return sum;    
  }    

  private void update(int i,int x){ //增加某个元素的大小,给某个节点 i 加上 x   
      while(i<=m){    
        C[i]=C[i]+x; //更新父节点
        i=i+lowbit(i);    
     }    
    }  

  public static void main(String[] args) throws IOException{  
    Main ma=new Main();
    ma.go();
  }

   public void go() throws IOException{
      
      StreamTokenizer st = new StreamTokenizer(new BufferedReader(      
      new InputStreamReader(System.in)));      
      PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));      

    int T=0;  
    int cas;  
    st.nextToken();      
    cas= (int) st.nval;
   
    while(cas-->0){
      st.nextToken();  
      n=(int) st.nval;
      st.nextToken();  
      m=(int) st.nval;
      st.nextToken();  
      k=(int) st.nval;
  
      C=new long[m+1];
      edge=new Node[k];
      for(int i=0;i<k;i++){
       edge[i]=new Node();
        st.nextToken();  
       edge[i].x=(int) st.nval;
        st.nextToken();  
       edge[i].y=(int) st.nval;
      }  
     // for(int i=0;i<edge.length;i++)
     //   System.out.println(edge[i]);
       Arrays.sort(edge);  
       long ans=0;  
       for(int i=0;i<k;i++){  
        update(edge[i].y,1);  //加入一条公路
        ans+=(Sum(m)-Sum(edge[i].y));  //统计
     }  
     T++;  
     System.out.printf("Test case %d: %d\n",T,ans);  
    }  
   } 
}  



  • 大小: 1.1 KB
0
0
分享到:
评论

相关推荐

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

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

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    二维树状数组练习 POJ 2029

    它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...

    二维树状数组学习之二:练习POJ 1195

    在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...

    ACM 新手指南 PKU 题目分类

    - **树形DP**:针对树形结构的问题,利用子问题的解来求解原问题。 - 示例题目:POJ 2531, POJ 1416, POJ 2676, 1129 ##### 4. 几何问题 - **凸包**:构建凸包并求解相关的几何问题。 - 示例题目:POJ 1837, POJ...

    acm poj300题分层训练

    poj2528、poj2777等是线段树的题目,poj2482、poj2352等涉及平衡树,poj1195、poj3321则训练了树状数组。 5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。...

    ACM训练方案

    4. 数据结构高级应用:线段树、静态二叉检索树、树状数组、RMQ和并查集的更复杂用法。 5. 搜索优化:最优化剪枝、搜索技巧和记忆化搜索。 这些内容构成了一个全面的ACM训练框架,旨在全面提升参赛者的编程思维、...

    算法训练方案详解

    - **定义**: 一种用于存储字符串的树形结构。 - **应用场景**: 字典管理。 - **示例题目**: POJ 2513 - **注意事项**: 区分静态建树和动态建树的不同。 #### 四、简单搜索 **1. 深度优先搜索** - **定义**: ...

    acm新手刷题攻略之poj

    - 高级数据结构如线段树、树状数组等可以提高程序效率。 2. **状态压缩** - 推荐题目:[poj2482](https://vjudge.net/problem/POJ-2482)、[poj2352](https://vjudge.net/problem/POJ-2352) - 状态压缩DP用于处理...

    poj各种分类

    在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...

    poj 3342(树状dp)

    在题目描述中提到,一个公司内部的员工关系构成一棵树形结构,其中每个员工(除了最高级别的老板)都有一个直属上司。公司计划举办一场聚会,希望邀请尽可能多的员工参加。但存在一定的限制条件:如果某员工参加聚会...

    ACM北大训练

    - **定义**: 树状树组是一种用于维护动态数组的高效数据结构。 - **应用场景**: 在区间查询、动态数组等问题中有广泛应用。 - **示例题目**: - poj1195: 涉及树状树组的应用。 以上内容涵盖了ACM竞赛中涉及到的...

    北大ACM 题目分类

    树形结构 - **题目**: 如`poj2488`、`poj3083`等。 - **所需知识**: 树的定义、遍历方法、特殊树结构(如二叉查找树、红黑树等)。 #### 2. 字符串处理 - **题目**: 包括`poj3278`、`poj1426`等。 - **所需知识*...

    poj(百练)题目分类

    - 高级数据结构:平衡树(AVL树、红黑树)、线段树、树状数组、并查集等。 - 特殊的数据结构:后缀数组、LCP数组等用于文本处理的高效结构。 #### 6. 几何题 几何题通常涉及到几何图形的性质、计算等。 - **知识点*...

    POJ100题_C++_源码

    10. T062.cpp - 可能是树形结构问题,如二叉树或树的遍历,C++的递归和指针操作是基础。 通过分析和学习这些源码,开发者不仅可以提升C++编程技巧,还能加深对算法的理解,对于参加ACM/ICPC等编程竞赛或者提高软件...

    pku(poj)--2494--Acid Text--java代码

    - **技能提升**:项目涉及的数据结构(如二维数组、树形图、向量等)和算法(如字符串处理、文件读写)对于提高编程技能非常有帮助。 - **创新思维**:在解决具体问题时,鼓励学生思考不同的解决方案,培养创新思维...

    很快速的提高算法能力.docx

    - **数据结构**:掌握线段树、静态二叉检索树、树状数组等高级数据结构。 - **搜索**:进一步学习最优化剪枝和可持久化数据结构。 通过以上步骤,持续练习和分析题目,你可以逐渐提高算法能力。同时,理解每种...

    数据结构中poj题目算法分类——针对ACM竞赛

    - **最小生成树**:Prim算法和Kruskal算法用于寻找边权和最小的树形子图。 - **拓扑排序**:对于有向无环图(DAG),可以进行拓扑排序来确定事件的顺序。 3. **数据处理**: - **排序**:快速排序、归并排序、堆...

    ACM算法总结--最新总结的ACM算法

    1. **高级数据结构**(如poj2528, poj2828, poj2777, poj2886, poj2750):包括线段树、树状数组、Trie树等,用于解决复杂的数据查询和更新问题。 2. **平衡树**(如poj2482, poj2352):如AVL树、红黑树等,保持树...

Global site tag (gtag.js) - Google Analytics