Guest User

Untitled

a guest
Oct 16th, 2013
3,158
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <iomanip>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <string>
  9. #include <stack>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <queue>
  13. #include <list>
  14. #include <map>
  15. #include <set>
  16.  
  17. #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
  18. #define FOR(i,a) For(i,1,a)
  19. #define Ford(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
  20. #define Rep(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
  21. #define REP(i,a) Rep(i,0,a)
  22. #define type(x) __typeof(x.begin())
  23. #define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )
  24.  
  25. #define compress(x) {sort(all(x));(x).resize(unique(all(x))-(x).begin());}
  26. #define fill(x,y) memset(x,y,sizeof x)
  27. #define all(x) x.begin(),x.end()
  28. #define two(x) (1LL<<(x))
  29. #define fi first
  30. #define se second
  31. #define gcd __gcd
  32. #define pb push_back
  33. #define mp make_pair
  34.  
  35. #ifdef KAZAR
  36.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  37.     #define dbg(x) cerr<<#x<<":"<<(x)<<endl
  38.     #define dg(x) cerr<<#x<<":"<<(x)<<' '
  39. #else
  40.     #define eprintf(...) 0
  41.     #define dbg(x) 0
  42.     #define dg(x) 0
  43. #endif
  44.  
  45. using namespace std;
  46.  
  47. typedef long long Lint;
  48. typedef long double ld;
  49. typedef pair<int,int> ii;
  50. typedef pair<int,ii> iii;
  51. typedef vector<int> vi;
  52. typedef vector<ii> vii;
  53.  
  54. const int inf = 1e9+5143;
  55. const Lint Linf = 1e18+5413;
  56. const double eps = 1e-10;
  57. const double pi = acos(-1);
  58.  
  59. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  60. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  61. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  62. template<class T> inline T lcm(T a,T b){
  63.     return a/gcd(a,b)*b;
  64. }
  65.  
  66. inline int read(){
  67.     int res = 0LL ;int neg ;
  68.     while(1){
  69.         char ch = getchar();
  70.         if(ch>='0' && ch<='9' || ch=='-'){
  71.             if(ch=='-') neg = -1;
  72.             else neg = 1 , res = ch-'0';
  73.             break;
  74.         }
  75.     }
  76.     while(1){
  77.         char ch = getchar();
  78.         if(ch>='0' && ch<='9') res*=10,res+=ch-'0';
  79.         else break;
  80.     }
  81.     return res*neg;
  82. }
  83.  
  84. const int N = 171717;
  85.  
  86. int kd[20][N] , a[N] , pos[N] , Real[N];
  87.  
  88. void init(int d,int b,int e){
  89.     if(b == e){
  90.         kd[d][b] = pos[b];
  91.         return;
  92.     }
  93.     int m = (b + e) >> 1;
  94.     init(d + 1,b,m);
  95.     init(d + 1,m+1,e);
  96.     int i = b , j = m + 1;
  97.     int ptr = 0;
  98.     while(i <= m && j <= e){
  99.         if(kd[d + 1][i] < kd[d + 1][j]){
  100.             kd[d][b + (ptr++)] = kd[d + 1][i++];
  101.         }else{
  102.             kd[d][b + (ptr++)] = kd[d + 1][j++];
  103.         }
  104.     }
  105.     while(i <= m) kd[d][b + (ptr++)] = kd[d + 1][i++];
  106.     while(j <= e) kd[d][b + (ptr++)] = kd[d + 1][j++];
  107. }
  108.  
  109. inline int find(int d,int b,int e,int x1,int x2){
  110.     return upper_bound(kd[d] + b,kd[d] + e + 1,x2) - lower_bound(kd[d] + b,kd[d] + e + 1,x1);
  111. }
  112.  
  113. int get(int n,int x1,int x2,int k){
  114.     int d = 0 , b = 1 , e = n;
  115.     while(b != e){
  116.         int ll = find(d + 1,b,(b+e)/2,x1,x2);
  117.         int m = (b + e) >> 1;
  118.         if(ll >= k){
  119.             e = m;
  120.         }else{
  121.             b = m + 1;
  122.             k -= ll;
  123.         }
  124.         ++d;
  125.     }
  126.     return b;
  127. }
  128.  
  129. int main(){
  130.  
  131. #ifdef KAZAR
  132.     freopen("f.i","r",stdin);
  133.     freopen("f.cik","w",stdout);
  134.     freopen("error","w",stderr);
  135. #endif
  136.  
  137.     int n = read();
  138.     int m = read();
  139.  
  140.     vi vals;
  141.  
  142.     FOR(i,n){
  143.         a[i] = read();
  144.         vals.pb(a[i]);
  145.     }
  146.  
  147.     sort(all(vals));
  148.  
  149.     FOR(i,n){
  150.         int old = a[i];
  151.         a[i] = lower_bound(all(vals),a[i]) - vals.begin() + 1;
  152.         pos[a[i]] = i;
  153.         Real[a[i]] = old;
  154.     }
  155.  
  156.     init(0,1,n);
  157.  
  158.     while(m--){
  159.         int from = read(), to = read(), k = read();
  160.         assert(to - from + 1 >= k);
  161.         printf("%d\n",Real[get(n,from,to,k)]);
  162.     }
  163.  
  164.     return 0;
  165. }
RAW Paste Data