fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define pii pair<int, int>
  5. #define REP(i, a, b) for (int i = a; i <= b; i++)
  6. #define RREP(i, a, b) for (int i = a; i >= b; i--)
  7. #define endl "\n"
  8. #define all(x) (x).begin(), (x).end()
  9. #define pi 3.141592653589793238
  10.  
  11. #define maxN 30001
  12. #define INF 1000000000
  13. #define mod 1000000007
  14. #define printd(x) cout << fixed << setprecision(10) << x
  15. // int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
  16. // int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
  17. // int dx[] = {-1, 0, 1, 0, 1, -1, 1, -1};
  18. // int dy[] = {0, -1, 0, 1, -1, -1, 1, 1};
  19.  
  20. int n, q;
  21. int arr[maxN];
  22. int rev[maxN];
  23. map<int, int> mp;
  24. int timer = 0;
  25.  
  26. int bs(int k)
  27. {
  28.     // index where arr[index] <= k
  29.     int start = 1, end = timer;
  30.  
  31.     while (start <= end)
  32.     {
  33.         int mid = (start + end) / 2;
  34.  
  35.         if (rev[mid] <= k && (mid == end || rev[mid + 1] > k))
  36.             return mid;
  37.         else if (rev[mid] <= k)
  38.             start = mid + 1;
  39.         else
  40.             end = mid - 1;
  41.     }
  42.  
  43.     return 0; // then answer = size of range
  44. }
  45.  
  46. template <class T>
  47. class PersistentSegmentTree
  48. {
  49.     int n;
  50.     vector<T> segTree;
  51.     vector<int> left, right;
  52.     vector<int> roots;
  53.     int index;
  54.  
  55. public:
  56.     PersistentSegmentTree() {}
  57.  
  58.     int build(int ss, int se)
  59.     {
  60.         int node = ++index;
  61.  
  62.         if (ss == se)
  63.         {
  64.             segTree[node] = 0;
  65.             return node;
  66.         }
  67.         else
  68.         {
  69.             int mid = (ss + se) / 2;
  70.             left[node] = build(ss, mid);
  71.             right[node] = build(mid + 1, se);
  72.             segTree[node] = 0;
  73.             return node;
  74.         }
  75.     }
  76.  
  77.     PersistentSegmentTree(int N)
  78.     {
  79.         n = N;
  80.         segTree.resize(N * 21);
  81.         left.resize(N * 21);
  82.         right.resize(N * 21);
  83.         index = 0;
  84.         roots.push_back(build(1, n));
  85.     }
  86.  
  87.     void resize(int N)
  88.     {
  89.         n = N;
  90.         segTree.resize(N * 21);
  91.         left.resize(N * 21);
  92.         right.resize(N * 21);
  93.         index = 0;
  94.         roots.push_back(build(1, n));
  95.     }
  96.  
  97.     int _update_(int prevNode, int ss, int se, int qi, T val)
  98.     {
  99.         int node = ++index;
  100.  
  101.         if (ss == se)
  102.         {
  103.             segTree[node] = segTree[prevNode] + val;
  104.             return node;
  105.         }
  106.  
  107.         int mid = (ss + se) / 2;
  108.  
  109.         if (qi <= mid)
  110.         {
  111.             right[node] = right[prevNode];
  112.             left[node] = _update_(left[prevNode], ss, mid, qi, val);
  113.         }
  114.         else
  115.         {
  116.             left[node] = left[prevNode];
  117.             right[node] = _update_(right[prevNode], mid + 1, se, qi, val);
  118.         }
  119.  
  120.         segTree[node] = segTree[left[node]] + segTree[right[node]];
  121.         return node;
  122.     }
  123.  
  124.     void update(int index, T val)
  125.     {
  126.         roots.push_back(_update_(roots.back(), 1, n, index, val));
  127.     }
  128.  
  129.     T _query_(int nodeA, int nodeB, int ss, int se, int qs, int qe)
  130.     {
  131.         if (qs > se || qe < ss)
  132.             return 0;
  133.         if (qs <= ss && qe >= se)
  134.             return segTree[nodeA] - segTree[nodeB];
  135.         int mid = (ss + se) / 2;
  136.         return _query_(left[nodeA], left[nodeB], ss, mid, qs, qe) + _query_(right[nodeA], right[nodeB], mid + 1, se, qs, qe);
  137.     }
  138.  
  139.     T _query_(int nodeA, int nodeB, int ss, int se, int k)
  140.     {
  141.         if (ss == se)
  142.             return ss;
  143.  
  144.         int diff = segTree[left[nodeA]] - segTree[left[nodeB]];
  145.         int mid = (ss + se) / 2;
  146.  
  147.         if (diff >= k)
  148.             return _query_(left[nodeA], left[nodeB], ss, mid, k);
  149.         else
  150.             return _query_(right[nodeA], right[nodeB], mid + 1, se, k - diff);
  151.     }
  152.  
  153.     T query(int ul, int ur, int qs, int qe = -1)
  154.     {
  155.         if (qe == -1)
  156.             return _query_(roots[ur], roots[ul - 1], 1, n, qs);
  157.         else
  158.             return _query_(roots[ur], roots[ul - 1], 1, n, qs, qe);
  159.     }
  160. };
  161.  
  162. void solve()
  163. {
  164.     cin >> n;
  165.  
  166.     PersistentSegmentTree<ll> segTree(n);
  167.  
  168.     REP(i, 1, n)
  169.     {
  170.         cin >> arr[i];
  171.         mp[arr[i]];
  172.     }
  173.  
  174.     for (auto &e : mp)
  175.         e.second = ++timer;
  176.  
  177.     REP(i, 1, n)
  178.     {
  179.         int temp = arr[i];
  180.         arr[i] = mp[arr[i]];
  181.         rev[arr[i]] = temp;
  182.         segTree.update(arr[i], 1);
  183.     }
  184.  
  185.     cin >> q;
  186.  
  187.     REP(x, 1, q)
  188.     {
  189.         int i, j, k;
  190.         cin >> i >> j >> k;
  191.         k = bs(k) + 1;
  192.         cout << segTree.query(i, j, k, n) << endl;
  193.     }
  194. }
  195.  
  196. int main(int argc, char const *argv[])
  197. {
  198.     ios_base::sync_with_stdio(false);
  199.     cin.tie(NULL);
  200.     cout.tie(NULL);
  201.  
  202.     // freopen("input.txt","r",stdin);
  203.     // freopen("output.txt","w",stdout);
  204.  
  205.     int t = 1;
  206.  
  207.     // cin >> t;
  208.  
  209.     REP(tc, 1, t)
  210.     {
  211.         // cout<<"Case "<<tc<<":"<<endl;
  212.         solve();
  213.     }
  214.  
  215.     return 0;
  216. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/QNaPS3
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!