线段树求逆序数（离散化）POJ 2299

POJ2299题意：

  给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力，会超时。


样例:(2次测试)
Sample Input

5  序列中数的个数
9
1
0
5
4
3  序列中数的个数
1
2
3
0   n=0结束

Sample Output

6
0


  其中需排序的数的范围0---999 999 999；显然数组不能开这么大,序列中数的个数N不大于500000,故先要将给出的序列离散到[1,500000]。

例: int a[] = {10000000, 10, 2000, 20, 300};
那么离散化后a[] = {5, 1, 4, 2, 3},是一个一一对应关系，而且满足原来的大小关系，离散的方法如下：

（1）定义一个类,用来表示序列中的一个数。
   class Node implements Comparable{
    int val;//值
    int no;//序号

     public int compareTo(Object o) {
      return this.val - ((Node) o).val;
  }
 }

（2）然后将所给序列用下面数组p表示，排序p并离散化.

            int data[] = new int[n];  
             Node[] p=new Node[n];
              
            for (int i = 0; i < n; i++) {   

              p[i]=new Node();
              p[i].val=in.nextInt();   
              p[i].no=i;   
            }

             Arrays.sort(p);
            for(int i=0;i<n;i++){
              data[p[i].no]=i+1;
           }//以上是使其离散化

POJ2299解题思路： 其实这题就是求这个序列的逆序数，离散化后用线段树边查询边插入即可。

下面是AC过的代码:(请参考:http://128kj.iteye.com/blog/1741183

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.io.BufferedInputStream; 
  
  
  class Seg_Tree {//线段树节点   
    int left,right;   
        int val;//区间内已插入的节点数   
    int calmid() {   
        return (left+right)/2;   
    }   
   }   
  
  class Node implements Comparable{
    int val;
    int no;

     public int compareTo(Object o) {
    return this.val - ((Node) o).val;
  }
 }
  public class Main{   
     private int LL(int x) { return x<<1;}  //两倍；   
     private int RR(int x) { return x<<1|1;} //两倍+1；   
     Seg_Tree tt[];   
    
  
    public Main(){   
      tt=new Seg_Tree[ 1048578];//用数组实现线段树   
      for(int i=0;i< 1048578;i++)   
          tt[i]=new Seg_Tree();   
    }   
  
    private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树   
    tt[idx].left = left;   
    tt[idx].right = right;   
    tt[idx].val = 0;   
    if(left == right) return ;     
    int mid = tt[idx].calmid();   
    build(left,mid,LL(idx));   
    build(mid+1,right,RR(idx));   
    }   
   
       
   private void insert(int aim,int l,int r,int k){  //将aim插入到线段树   
    if(tt[k].left==aim&&tt[k].right==aim) {   
      tt[k].val++;return ;   
    }     
     
    if(aim<=tt[k].calmid())    
       insert(aim,l,tt[k].calmid(),LL(k));     
    else        
      insert(aim,tt[k].calmid()+1,r,2*k+1);     
    tt[k].val=tt[LL(k)].val+tt[RR(k)].val;     
  }     
  
     
    //查询[left，right]中已插入的节点数   
    private int query(int left,int right,int idx){   
    if(left == tt[idx].left && right == tt[idx].right)    
           return tt[idx].val;   
       
    int mid = tt[idx].calmid();   
    if(right <= mid){   
        return query(left,right,LL(idx));   
    }    
       else if(mid < left) {   
        return query(left,right,RR(idx));   
    }    
       else {   
        return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));   
    }   
     }   
  
  public static void main(String[] args){   
   Scanner in = new Scanner(new BufferedInputStream(System.in));   
        while (in.hasNext()) {   
            int n = in.nextInt();   
            if (n == 0) {   
                break;   
            }   
          
            int data[] = new int[n];  
             Node[] p=new Node[n];
              
            for (int i = 0; i < n; i++) {   

              p[i]=new Node();
              p[i].val=in.nextInt();   
              p[i].no=i;   
            }

             Arrays.sort(p);
            for(int i=0;i<n;i++){
              data[p[i].no]=i+1;
           }//以上是使其离散化

          Main ma=new Main();   
          ma.build(1,n,1);   
          long sum = 0;     
          for(int i=0;i<n;i++){   
            sum += ma.query(data[i],n,1);//先查询   
            ma.insert(data[i],1,n,1);//后插入   
          }  
          System.out.println(sum);
        }  
    }
} 

源码:

评论

3 楼 128kj 2012-12-06  

不好意思，没写清题目意思，已改过来了。
  给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。

2 楼 mfkvfn 2012-12-06  

引用

例如将"91054"变成"01459",最小交换6次

我怎么觉得只要两次就可以了

91054   第一次交换9和0，得到01954
01954   第二次交换9和4，得到01459

1 楼 HalfSmoked 2012-12-06  

引用

例如将"91054"变成"01459",最小交换6次

我怎么感觉是交换两次就行了。9和0和4.