Hatena::Grouptopcoder

tsubosakaの日記

2011-05-24

pku2104

23:32

http://poj.org/problem?id=2104

昨日書いたWavelet treeを使った解法

メモリ効率考えてないのでPOJのサーバだと通んないけど、judgeデータ落としてきて手元で通ることは確認した。

package pku2104;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

class BitVector{
  int rank[];
  public BitVector(int[] arr) {
    rank = new int[arr.length];
    rank[0] = arr[0];
    for(int i = 1 ; i < arr.length ; ++i){
      rank[i] = rank[i - 1] + arr[i];
    }
  }
  int rank(int p , int b){
    if(b == 1){
      return rank[p];
    }else{
      return p + 1 - rank[p];
    }
  }
}

class Tree{
  int hbit;
  BitVector bvec;  
  Tree left;
  Tree right;
  Tree(int h , BitVector v){
    hbit = h;
    bvec = v;
  }
}

class WTree{
  Tree root;
  Tree gen(int hbit , int[] arr){
    if(hbit == 0){
      return new Tree(hbit , null);
    }
    int lsize = 0;
    int rsize = 0;
    int bv[] = new int[arr.length];
    for(int i = 0 ; i < arr.length ; ++i){
      if((arr[i] & hbit) != 0){
        bv[i] = 1;
        ++rsize;
      }else{
        bv[i] = 0;
        ++lsize;
      }
    }
    Tree ret = new Tree(hbit , new BitVector(bv));
    bv = null;
    int[] left = new int[lsize];
    int[] right = new int[rsize];
    int li = 0;
    int ri = 0;
    for(int i = 0 ; i < arr.length ; ++i){
      if((arr[i] & hbit) != 0){
        right[ri++] = arr[i];
      }else{
        left[li++] = arr[i];
      }
    }   
    if(lsize > 0){
      ret.left = gen(hbit / 2, left);
    }
    if(rsize > 0){
      ret.right = gen(hbit / 2 , right);
    }
    return ret;
  }
  public WTree(int[] arr) {
    int max = 0;
    for(int a : arr)
      max = Math.max(max, a);
    int h = Integer.highestOneBit(max);
    root = gen(h , arr);
  }
  int rank(int p , int k){
    Tree r = root;
    int ret = 0;
    while(p >= 0 && r != null){
      if(r.hbit == 0){
        ret += p + 1 ; 
        break;
      }
      int r0 = r.bvec.rank(p, 0);      
      if((k & r.hbit) != 0){
        ret += r0;
        p = p - r0;
        r = r.right;
      }else{
        p = r0 - 1;
        r = r.left;
      }
    }
    return ret;
  }
}
public class Main {
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Scanner cin = new Scanner(br);
    int n = cin.nextInt();
    int m = cin.nextInt();
    int arr[] = new int[n];
    int min = Integer.MAX_VALUE;
    for(int i = 0 ; i < n ; ++i){
      arr[i] = cin.nextInt();
      min = Math.min(min, arr[i]);
    }    
    for(int i = 0 ; i < n ; ++i){
      arr[i] = arr[i] - min;
    }
    int sarr[] = arr.clone();
    Arrays.sort(sarr);
    WTree wt = new WTree(arr);
    for(int query = 0 ; query < m ; ++query){
      int i = cin.nextInt() - 1;
      int j = cin.nextInt() - 1;
      int k = cin.nextInt();
      int low = 0;
      int high = n - 1;
      while(low < high){
        int mid = low + (high - low) / 2;
        int num = wt.rank(j, sarr[mid]);
        if(i > 0){
          num -= wt.rank(i - 1, sarr[mid]);
        }
        if(num >= k){
          high = mid;
        }else{
          low = mid + 1;
        }
      }
      System.out.println(sarr[low] + min);
    }
  }
}