fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. import static java.lang.Integer.MAX_VALUE;
  7. import static java.lang.Integer.parseInt;
  8. import static java.lang.Math.min;
  9.  
  10. class SegmentTree {
  11.  
  12.     static int t[] = new int[200005];
  13.     static int a[] = new int[200005];
  14.  
  15.     public static void main(String[] args) throws IOException {
  16.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17.         int n, l, r, q, x, y;
  18.         String s[];
  19.  
  20.         s = br.readLine().split("\\s");
  21.         n = parseInt(s[0]);
  22.         q = parseInt(s[1]);
  23.  
  24.         s = br.readLine().split("\\s");
  25.         for (int i = 0; i < n; i++) {
  26.             a[i] = parseInt(s[i]);
  27.         }
  28.  
  29.         buildTree(a, n);
  30.         for (int i = 0; i < q; i++) {
  31.             s = br.readLine().split("\\s");
  32.             if ("q".equals(s[0])) {
  33.                 l = parseInt(s[1]);
  34.                 r = parseInt(s[2]);
  35.                 System.out.println(query(--l, r, n));
  36.             } else {
  37.                 x = parseInt(s[1]);
  38.                 y = parseInt(s[2]);
  39.                 update(--x, y, n);
  40.             }
  41.         }
  42.     }
  43.  
  44.     private static void update(int x, int y, int n) {
  45.  
  46.  
  47.         x += n;
  48.         t[x] = y;
  49.         for ( ; x > 1; x >>= 1) {
  50.             t[x>>1] = min(t[x], t[(x) ^ 1]);
  51.         }
  52.     }
  53.  
  54.     private static int query(int l, int r,int n) {
  55.  
  56.         int ans = Integer.MAX_VALUE;
  57.         for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  58.             if ((l & 1) == 1) {
  59.                 ans = min(ans, t[l++]);
  60.             }
  61.             if ((r & 1) == 1) {
  62.                 ans = min(ans, t[--r]);
  63.             }
  64.         }
  65.         return ans;
  66.     }
  67.  
  68.     private static void buildTree(int[] a, int n) {
  69.         Arrays.fill(t, 0, 2 * n , Integer.MAX_VALUE);
  70.         System.arraycopy(a, 0, t, n, n);
  71.         //for (int i = 0; i < n; ++i) t[n+i]=a[i];
  72.         for (int i = n - 1; i > 0; i--) {
  73.             t[i] = min(t[i << 1], t[(i << 1) + 1]);
  74.         }
  75.     }
  76. }
Success #stdin #stdout 0.1s 29512KB
comments (?)
stdin
copy 
5 5
1 5 2 4 3
q 1 5
q 1 3
q 3 5
u 3 6
q 1 5
stdout
copy 
1
1
2
1
https://ideone.com/C6yPjE
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!