Guest User

Untitled

a guest
Jan 22nd, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1. import java.lang.reflect.Constructor;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class Range_MinQueries {
  6.  
  7. public static void main(String[] args) {
  8. // TODO Auto-generated method stub
  9. Scanner in = new Scanner(System.in);
  10. int n = in.nextInt();
  11. int[] a = new int[n];
  12. for (int i = 0; i < n; i++)
  13. a[i] = in.nextInt();
  14.  
  15. int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
  16. int m = 2 * (int) Math.pow(2, x) - 1;
  17.  
  18. int[] seg = new int[m];
  19. Arrays.fill(seg, Integer.MAX_VALUE);
  20. ConstructTree(a, seg, 0, a.length - 1, 0);
  21. int qlow = in.nextInt();
  22. int qhigh = in.nextInt();
  23. System.out.println(MinRangeQuery(seg, qlow, qhigh, 0, a.length - 1, 0));
  24. }
  25.  
  26. public static void ConstructTree(int[] a, int[] seg, int low, int high, int pos) {
  27. if (low == high) {
  28. seg[pos] = a[low];
  29. return;
  30. }
  31. int mid = (low + high) / 2;
  32. ConstructTree(a, seg, low, mid, 2 * pos + 1);
  33. ConstructTree(a, seg, mid + 1, high, 2 * pos + 2);
  34. seg[pos] = Math.min(seg[2 * pos + 1], seg[2 * pos + 2]);
  35. }
  36.  
  37. public static int MinRangeQuery(int[] seg, int qlow, int qhigh, int low, int high, int pos) {
  38. if (low >= qlow && high <= qhigh) {
  39. return seg[pos];
  40. }
  41.  
  42. if (high < qlow || low > qhigh) {
  43. return Integer.MAX_VALUE;
  44. }
  45.  
  46. int mid = (low + high) / 2;
  47.  
  48. return Math.min(MinRangeQuery(seg, qlow, qhigh, low, mid, 2 * pos + 1),
  49. MinRangeQuery(seg, qlow, qhigh, mid + 1, high, 2 * pos + 2));
  50. }
  51.  
  52. }
Add Comment
Please, Sign In to add comment