Guest User

Second Minimum

a guest
Jan 21st, 2015
365
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = (int) 1e6;
  6. const int INF = (int) 1e9 + 7;
  7.  
  8. struct node {
  9.     int fmin, smin;
  10.     node(int x = 0, int y = 0) {
  11.         fmin = x;
  12.         smin = y;
  13.     }
  14. };
  15.  
  16. node t[N];
  17.  
  18. int n;
  19. int a[N];
  20.  
  21. node merge(node a, node b) {
  22.     node c;
  23.     if (a.fmin < b.fmin) {
  24.         c.fmin = a.fmin;
  25.         c.smin = min(a.smin, b.fmin);
  26.     }
  27.     else {
  28.         c.fmin = b.fmin;
  29.         c.smin = min(b.smin, a.fmin);
  30.     }
  31.     return c;
  32. }
  33.  
  34. void build(int v, int tl, int tr) {
  35.     if (tl == tr) t[v] = node(a[tl], INF);
  36.     else {
  37.         int m = (tl + tr) / 2;
  38.         build(v + v, tl, m);
  39.         build(v + v + 1, m + 1, tr);
  40.         t[v] = merge(t[v + v], t[v + v + 1]);
  41.     }
  42. }
  43.  
  44. node get(int v, int tl, int tr, int l, int r) {
  45.     if (l > tr || r < tl) return node(INF, INF);
  46.     else if (l <= tl && tr <= r) return t[v];
  47.     else {
  48.         int m = (tl + tr) / 2;
  49.         return merge(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
  50.     }
  51. }
  52.  
  53. void upd(int v, int tl, int tr, int pos, int val) {
  54.     if (tl == tr) t[v] = node(val, INF);
  55.     else {
  56.         int m = (tl + tr) / 2;
  57.         if (pos <= m) upd(v + v, tl, m, pos, val);
  58.         else upd(v + v, m + 1, tr, pos, val);
  59.         t[v] = merge(t[v + v], t[v + v + 1]);
  60.     }
  61. }
  62.  
  63. int main() {
  64.     scanf("%d", &n);
  65.     for (int i = 1; i <= n; i++)
  66.         scanf("%d", &a[i]);
  67.  
  68.     build(1, 1, n);
  69.  
  70.     int m;
  71.     scanf("%d", &m);
  72.     while (m--) {
  73.         int l, r;
  74.         scanf("%d%d", &l, &r);
  75.         node res = get(1, 1, n, l, r);
  76.         printf("%d %d\n", res.fmin, res.smin);
  77.     }
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment