Guest User

Untitled

a guest
Oct 17th, 2013
651
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <map>
  4. #include <vector>
  5.  
  6. #define RIGHT 131072
  7. #define SIZE 262144
  8.  
  9. using namespace std;
  10.  
  11. struct T
  12. {
  13.     int am, l, r;
  14.     T(int a, int b, int c) : am(a), l(b), r(c) {};
  15. };
  16.  
  17. int N, Q, Last;
  18. int A[100005], Orig[100005], S[100005], Root[100005];
  19. map<int,int> M;
  20. vector<T> V(2100000, T(0, 0, 0));
  21.  
  22. int newNode(int n)
  23. {
  24.     V[++Last].am = V[n].am;
  25.     V[Last].l = V[n].l;
  26.     V[Last].r = V[n].r;
  27.     return Last;
  28. }
  29.  
  30. int insert(int idx, int v, int n, int a, int b)
  31. {
  32.     if(a > v || b < v)
  33.         return idx;
  34.  
  35.     idx = newNode(idx);
  36.  
  37.     if(a == v && b == v)
  38.     {
  39.         V[idx].am++;
  40.         return idx;
  41.     }
  42.  
  43.     int mid = (a+b) / 2;
  44.     V[idx].l = insert(V[idx].l, v, 2*n, a, mid);
  45.     V[idx].r = insert(V[idx].r, v, 2*n + 1, mid + 1, b);
  46.  
  47.     V[idx].am = V[V[idx].l].am + V[V[idx].r].am;
  48.     return idx;
  49. }
  50.  
  51. int query(int idx_l, int idx_r, int k, int n, int a, int b)
  52. {
  53.     if(k == 1 && a == b && V[idx_r].am - V[idx_l].am == 1)
  54.         return a;
  55.  
  56.     int mid = (a+b) / 2;
  57.     int on_left = V[V[idx_r].l].am - V[V[idx_l].l].am;
  58.  
  59.     if(on_left < k)
  60.         return query(V[idx_l].r, V[idx_r].r, k - on_left, 2*n + 1, mid + 1, b);
  61.     else
  62.         return query(V[idx_l].l, V[idx_r].l, k, 2*n, a, mid);
  63. }
  64.  
  65. int main()
  66. {
  67.     scanf("%d %d", &N, &Q);
  68.  
  69.     for(int i = 0; i < N; i++)
  70.     {
  71.         int x;
  72.         scanf("%d", &A[i]);
  73.         S[i] = A[i];
  74.     }
  75.  
  76.     sort(S, S+N);
  77.  
  78.     for(int i = 0; i < N; i++)
  79.         M[S[i]] = i+1, Orig[i+1] = S[i];
  80.  
  81.     for(int i = 0; i < N; i++)
  82.         Root[i+1] = insert(Root[i], M[A[i]], 1, 1, RIGHT);
  83.  
  84.     while(Q--)
  85.     {
  86.         int l, r, k;
  87.         scanf("%d %d %d", &l, &r, &k);
  88.         printf("%d\n", Orig[query(Root[l-1], Root[r], k, 1, 1, RIGHT)]);
  89.     }
  90. }
RAW Paste Data