fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6.  
  7. class ImplicitSegmentTree {
  8.  
  9.     int sz;
  10.     struct Node {
  11.         int s;
  12.         Node *l, *r;
  13.         Node() : s(0), l(0), r(0) {}
  14.     } *root;
  15.  
  16.     int query(Node *v, int vl, int vr, int l, int r) const {
  17.         if (!v || r < vl || vr < l)
  18.             return 0;
  19.         if (l <= vl && vr <= r)
  20.             return v->s;
  21.         int vm = vl + (vr - vl) / 2;
  22.         int ql = query(v->l, vl, vm, l, r);
  23.         int qr = query(v->r, vm + 1, vr, l, r);
  24.         return ql + qr;
  25.     }
  26.  
  27.     void modify(Node *v, int vl, int vr, int pos, int val) {
  28.         if (vl == vr) {
  29.             v->s += val;
  30.             return;
  31.         }
  32.         int vm = vl + (vr - vl) / 2;
  33.         if (pos <= vm) {
  34.             if (!v->l)
  35.                 v->l = new Node();
  36.             modify(v->l, vl, vm, pos, val);
  37.         } else {
  38.             if (!v->r)
  39.                 v->r = new Node();
  40.             modify(v->r, vm + 1, vr, pos, val);
  41.         }
  42.         v->s = (v->l ? v->l->s : 0) + (v->r ? v->r->s : 0);
  43.     }
  44.  
  45.     void destroy(Node *v) {
  46.         if (v->l)
  47.             destroy(v->l);
  48.         if (v->r)
  49.             destroy(v->r);
  50.         delete v;
  51.     }
  52.  
  53. public:
  54.  
  55.     ImplicitSegmentTree(int size) {
  56.         sz = size;
  57.         root = new Node();
  58.     }
  59.  
  60.     ~ImplicitSegmentTree() {
  61.         destroy(root);
  62.     }
  63.  
  64.     int size() {
  65.         return sz;
  66.     }
  67.  
  68.     int query(int l, int r) const {
  69.         return query(root, 0, sz - 1, l, r);
  70.     }
  71.  
  72.     void modify(int pos, int val) {
  73.         modify(root, 0, sz - 1, pos, val);
  74.     }
  75.  
  76. };
  77.  
  78.  
  79. class Event {
  80.  
  81.     int type, index, x, y;
  82.  
  83. public:
  84.  
  85.     Event(int type, int index, int x, int y) : type(type), index(index), x(x), y(y) {}
  86.  
  87.     bool operator < (const Event &that) const {
  88.         return x < that.x || x == that.x && type < that.type;
  89.     }
  90.  
  91.     void process(ImplicitSegmentTree &st, vector<int> &answers) const {
  92.         int k = st.query(y + 1, st.size() - 1);
  93.         if (type == 1)
  94.             answers[index] -= st.query(y + 1, st.size() - 1);
  95.         if (type == 2)
  96.             st.modify(y, 1);
  97.         if (type == 3)
  98.             answers[index] += st.query(y + 1, st.size() - 1);
  99.     }
  100.  
  101. };
  102.  
  103.  
  104. int main() {
  105.     vector<Event> scanLine;
  106.  
  107.     int aSize, aMax = 0;
  108.     scanf("%d", &aSize);
  109.  
  110.     vector<int> a(aSize);
  111.     for (int i = 0; i < aSize; i++) {
  112.         scanf("%d", &a[i]);
  113.         aMax = max(aMax, a[i]);
  114.         scanLine.push_back(Event(2, -1, i, a[i]));
  115.     }
  116.  
  117.     ImplicitSegmentTree st(aMax + 1);
  118.  
  119.     int queriesCount;
  120.     scanf("%d", &queriesCount);
  121.  
  122.     for (int i = 0; i < queriesCount; i++) {
  123.         int l, r, k;
  124.         scanf("%d%d%d", &l, &r, &k);
  125.         scanLine.push_back(Event(1, i, l - 1, k));
  126.         scanLine.push_back(Event(3, i, r - 1, k));
  127.     }
  128.  
  129.     vector<int> answers(queriesCount);
  130.     sort(scanLine.begin(), scanLine.end());
  131.     for (int i = 0; i < scanLine.size(); i++)
  132.         scanLine[i].process(st, answers);
  133.  
  134.     for (int i = 0; i < queriesCount; i++)
  135.         printf("%d\n", answers[i]);
  136. }
Success #stdin #stdout 0s 3496KB
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/sNS0Xb
language:
C++ (gcc 8.3)
created:
7 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!