fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6.  
  7. class PersistentSegmentTree {
  8.  
  9.     int sz;
  10.     struct Node {
  11.         int s;
  12.         Node *l, *r;
  13.         bool ownL, ownR;
  14.         Node() : s(0), l(0), r(0), ownL(0), ownR(0) {}
  15.         Node(const Node &that) : s(that.s), l(that.l), r(that.r), ownL(0), ownR(0) {}
  16.     };
  17.     vector<Node *> root;
  18.  
  19.     int query(Node *v, int vl, int vr, int l, int r) const {
  20.         if (!v || r < vl || vr < l)
  21.             return 0;
  22.         if (l <= vl && vr <= r)
  23.             return v->s;
  24.         int vm = vl + (vr - vl) / 2;
  25.         int ql = query(v->l, vl, vm, l, r);
  26.         int qr = query(v->r, vm + 1, vr, l, r);
  27.         return ql + qr;
  28.     }
  29.  
  30.     Node *modify(Node *v, int vl, int vr, int pos, int val) {
  31.         Node *nv = v ? new Node(*v) : new Node();
  32.         if (vl == vr) {
  33.             nv->s += val;
  34.             return nv;
  35.         }
  36.         int vm = vl + (vr - vl) / 2;
  37.         if (pos <= vm) {
  38.             nv->ownL = 1;
  39.             nv->l = modify(nv->l, vl, vm, pos, val);
  40.         } else {
  41.             nv->ownR = 1;
  42.             nv->r = modify(nv->r, vm + 1, vr, pos, val);
  43.         }
  44.         nv->s = (nv->l ? nv->l->s : 0) + (nv->r ? nv->r->s : 0);
  45.         return nv;
  46.     }
  47.  
  48.     void destroy(Node *v) {
  49.         if (v->ownL)
  50.             destroy(v->l);
  51.         if (v->ownR)
  52.             destroy(v->r);
  53.         delete v;
  54.     }
  55.  
  56. public:
  57.  
  58.     PersistentSegmentTree(int size) {
  59.         sz = size;
  60.         root.push_back(new Node());
  61.     }
  62.  
  63.     ~PersistentSegmentTree() {
  64.         for (int i = 0; i < root.size(); i++)
  65.             destroy(root[i]);
  66.     }
  67.  
  68.     int size() {
  69.         return sz;
  70.     }
  71.  
  72.     int query(int version, int l, int r) const {
  73.         return query(root[version], 0, sz - 1, l, r);
  74.     }
  75.  
  76.     void modify(int pos, int val) {
  77.         root.push_back(modify(root.back(), 0, sz - 1, pos, val));
  78.     }
  79.  
  80. };
  81.  
  82.  
  83. int main() {
  84.     int aSize, aMax = 0;
  85.     scanf("%d", &aSize);
  86.  
  87.     vector<int> a(aSize);
  88.     for (int i = 0; i < aSize; i++) {
  89.         scanf("%d", &a[i]);
  90.         aMax = max(aMax, a[i]);
  91.     }
  92.  
  93.     PersistentSegmentTree st(aMax + 1);
  94.     for (int i = 0; i < aSize; i++)
  95.         st.modify(a[i], 1);
  96.  
  97.     int queriesCount;
  98.     scanf("%d", &queriesCount);
  99.  
  100.     for (int i = 0; i < queriesCount; i++) {
  101.         int l, r, k;
  102.         scanf("%d%d%d", &l, &r, &k);
  103.         printf("%d\n", st.query(r, k + 1, st.size() - 1) - st.query(l - 1, k + 1, st.size() - 1));
  104.     }
  105. }
Success #stdin #stdout 0s 3512KB
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/IOxfS0
language:
C++ (gcc 8.3)
created:
8 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!