fork 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.     struct Node
  50.     {
  51.         Node *left, *right;
  52.         T val;
  53.  
  54.         Node(Node *l = NULL, Node *r = NULL, T c = 0)
  55.         {
  56.             left = l, right = r, val = c;
  57.         }
  58.     };
  59.  
  60.     int n;
  61.     vector<Node *> roots;
  62.  
  63. public:
  64.     PersistentSegmentTree() {}
  65.  
  66.     Node *build(int ss, int se)
  67.     {
  68.         if (ss == se)
  69.         {
  70.             return new Node();
  71.         }
  72.         else
  73.         {
  74.             Node *root = new Node();
  75.             int mid = (ss + se) / 2;
  76.             root->left = build(ss, mid);
  77.             root->right = build(mid + 1, se);
  78.             return root;
  79.         }
  80.     }
  81.  
  82.     PersistentSegmentTree(int N)
  83.     {
  84.         n = N;
  85.         roots.push_back(build(1, n));
  86.     }
  87.  
  88.     void _update_(Node *node, Node *prev, int ss, int se, int qi, T val)
  89.     {
  90.         if (ss == se)
  91.         {
  92.             node->val += val;
  93.             return;
  94.         }
  95.  
  96.         int mid = (ss + se) / 2;
  97.  
  98.         if (qi <= mid)
  99.         {
  100.             node->right = prev->right;
  101.             node->left = new Node();
  102.             _update_(node->left, prev->left, ss, mid, qi, val);
  103.         }
  104.         else
  105.         {
  106.             node->left = prev->left;
  107.             node->right = new Node();
  108.             _update_(node->right, prev->right, mid + 1, se, qi, val);
  109.         }
  110.  
  111.         node->val = node->left->val + node->right->val;
  112.     }
  113.  
  114.     void update(int index, T val)
  115.     {
  116.         Node *r = new Node();
  117.         _update_(r, roots.back(), 1, n, index, val);
  118.         roots.push_back(r);
  119.     }
  120.  
  121.     T _query_(Node *a, Node *b, int ss, int se, int qs, int qe)
  122.     {
  123.         if (qs > se || qe < ss)
  124.             return 0;
  125.  
  126.         if (qs <= ss && qe >= se)
  127.             return a->val - b->val;
  128.  
  129.         int mid = (ss + se) / 2;
  130.  
  131.         return _query_(a->left, b->left, ss, mid, qs, qe) + _query_(a->right, b->right, mid + 1, se, qs, qe);
  132.     }
  133.  
  134.     T query(int l, int r, int qs)
  135.     {
  136.         return _query_(roots[r], roots[l - 1], 1, n, qs, timer);
  137.     }
  138. };
  139.  
  140. void solve()
  141. {
  142.     cin >> n;
  143.  
  144.     PersistentSegmentTree<ll> segTree(n);
  145.  
  146.     REP(i, 1, n)
  147.     {
  148.         cin >> arr[i];
  149.         mp[arr[i]];
  150.     }
  151.  
  152.     for (auto &e : mp)
  153.         e.second = ++timer;
  154.  
  155.     REP(i, 1, n)
  156.     {
  157.         int temp = arr[i];
  158.         arr[i] = mp[arr[i]];
  159.         rev[arr[i]] = temp;
  160.         segTree.update(arr[i], 1);
  161.     }
  162.  
  163.     cin >> q;
  164.  
  165.     REP(x, 1, q)
  166.     {
  167.         int i, j, k;
  168.         cin >> i >> j >> k;
  169.         k = bs(k);
  170.         cout << segTree.query(i, j, k + 1) << endl;
  171.     }
  172. }
  173.  
  174. int main(int argc, char const *argv[])
  175. {
  176.     ios_base::sync_with_stdio(false);
  177.     cin.tie(NULL);
  178.     cout.tie(NULL);
  179.  
  180.     // freopen("input.txt","r",stdin);
  181.     // freopen("output.txt","w",stdout);
  182.  
  183.     int t = 1;
  184.  
  185.     // cin >> t;
  186.  
  187.     REP(tc, 1, t)
  188.     {
  189.         // cout<<"Case "<<tc<<":"<<endl;
  190.         solve();
  191.     }
  192.  
  193.     return 0;
  194. }
Success #stdin #stdout 0s 5604KB
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/dHF5hf
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!