Guest User

K-th Query

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