peltorator

!Wavelet Tree

Mar 28th, 2018
154
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <unordered_set>
  12. #include <complex>
  13. #include <unordered_map>
  14. #include <bitset>
  15. #include <ctime>
  16. #include <cassert>
  17. #include <random>
  18.  
  19. #define sz(a) (int)((a).size())
  20.  
  21. using namespace std;
  22.  
  23. mt19937 rnd(239);
  24.  
  25. typedef long long ll;
  26. typedef long double ld;
  27.  
  28. const int T = (1 << 20);
  29.  
  30. vector<int> a[T], b[T], arr, le(T), ri(T), good(T, 0);
  31. int cnt;
  32. const int INF = 1e9 + 1;
  33.  
  34. void build(int v, int l, int r)
  35. {
  36.     if (l + 1 == r || a[v].size() < 2)
  37.     {
  38.         good[v] = 1;
  39.         return;
  40.     }
  41.     int mid = 1LL * (r + l) / 2LL;
  42.     b[v].assign(a[v].size() + 1, 0);
  43.     le[v] = cnt++;
  44.     ri[v] = cnt++;
  45.     for (int i = 0; i < a[v].size(); i++)
  46.     {
  47.         b[v][i + 1] = b[v][i];
  48.         if (a[v][i] < mid)
  49.         {
  50.             b[v][i + 1]++;
  51.             a[le[v]].push_back(a[v][i]);
  52.         }
  53.         else
  54.             a[ri[v]].push_back(a[v][i]);
  55.     }
  56.     build(le[v], l, mid);
  57.     build(ri[v], mid, r);
  58. }
  59.  
  60. int kth(int v, int l, int r, int k)
  61. {
  62.     //cout << v << ' ' << l << ' ' << r << ' ' << a[v].size() << endl;
  63.     //cout << good.size() << endl;
  64.    // if (v == 6)
  65.      //   exit(0);
  66.     if (good[v])
  67.         return a[v][0];
  68.     if (b[v][r] - b[v][l] >= k)
  69.         return kth(le[v], b[v][l], b[v][r], k);
  70.     return kth(ri[v], l - b[v][l], r - b[v][r], k - (b[v][r] - b[v][l]));
  71. }
  72.  
  73. int solve()
  74. {
  75.     ios::sync_with_stdio(0);
  76.     int n;
  77.     if (!(cin >> n))
  78.     {
  79.         return 1;
  80.     }
  81.     int q;
  82.     cin >> q;
  83.     a[1].assign(n, 0);
  84.     for (int &i : a[1])
  85.         cin >> i;
  86.     cnt = 2;
  87.     build(1, -INF, INF);
  88.     while (q--)
  89.     {
  90.         int l, r, k;
  91.         cin >> l >> r >> k;
  92.         l--;
  93.         cout << kth(1, l, r, k) << '\n';
  94.     }
  95.     return 0;
  96. }
  97.  
  98. int32_t main()
  99. {
  100.     #ifdef ONPC
  101.         freopen("in.txt", "r", stdin);
  102.     #endif
  103.     int T = 100;
  104.     //cin >> T;
  105.     for (int i = 1; i <= T; i++)
  106.     {
  107.         #ifdef ONPC
  108.             cerr << "Test #" << i << ":\n";
  109.         #endif
  110.         if (solve())
  111.             break;
  112.         #ifdef ONPC
  113.             cerr << "_______________________________________________" << endl;
  114.         #endif
  115.     }
  116.     #ifdef ONPC
  117.         cerr << endl << "finished in " << clock() * 1000LL / CLOCKS_PER_SEC << " ms" << endl;
  118.     #endif
  119.     return 0;
  120. }
RAW Paste Data