ツリー配列練習:POJ 3067

ツリー配列については、以下を参照してください.http://128kj.iteye.com/blog/1743633
POJ 3067題意:
東海岸と西海岸はそれぞれNとMの都市があって、今高速道路を修理して東西の海岸の都市をつなぎます、交点の個数を求めます.
やり方:道路ごとに(x,y)、すなわち東岸のx番目の都市と西岸のy番目の都市に道を開くことを教える.2つのパスに交点がある場合、(x 1-x 2)*(y 1-y 2)<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の最大値である.そこで問題を区間和の問題に変換し,ツリー配列で解決する.2つのエッジのx相が同時になると,この2つのエッジのy値はそれぞれya,yb(ya
サンプル:
Sample Input
1(1回のテスト)
3 4 4(東、西岸の都市数及び総道路数)
1 4(道路の両端点)
2 3
3 2
3 1
Sample Output
Test case 1: 5
ACコード:
Javaコード

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

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

//System.out.println(edge[i]);

Arrays.sort(edge);

long ans=0;

for(int i=0;i

update(edge[i].y,1)//道路

に加入

ans+=(Sum(m)-Sum(edge[i].y);//統計

}

T++;

System.out.printf("Test case %d: %d",T,ans);

}

}

}

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