fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <map>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef struct Node *pnode;
  9.  
  10. struct Node {
  11.     int key, prior, cnt; // cnt nodes in subtree with the curr root (incl. root)
  12.     pnode l, r;
  13.  
  14.     Node(int key) : key(key), prior(rand()), cnt(1), l(nullptr), r(nullptr) {}
  15. };
  16.  
  17. struct Treap {
  18. private:
  19.     pnode root;
  20.  
  21.     int cnt(pnode t) {
  22.         return t ? t->cnt : 0;
  23.     }
  24.  
  25.     void updCnt(pnode t) {
  26.         if (t) {
  27.             t->cnt = 1 + cnt(t->l) + cnt(t->r);
  28.         }
  29.     }
  30.  
  31.     void split(pnode t, int key, pnode &l, pnode &r) {
  32.         if (!t) {
  33.             l = r = nullptr;
  34.         } else if (t->key <= key) {
  35.             split(t->r, key, t->r, r), l = t;
  36.         } else {
  37.             split(t->l, key, l, t->l), r = t;
  38.         }
  39.         updCnt(t);
  40.     }
  41.  
  42.     void insert(pnode &t, pnode it) {
  43.         if (!t) {
  44.             t = it;
  45.         } else if (it->prior <= t->prior) {
  46.             insert(t->key < it->key ? t->r : t->l, it);
  47.         } else {
  48.             split(t, it->key, it->l, it->r), t = it;
  49.         }
  50.         updCnt(t);
  51.         /*
  52.         pnode l, r, res;
  53.         split(t, it->key, l, r);
  54.         merge(res, l, it);
  55.         merge(res, res, r);
  56.         */
  57.     }
  58.  
  59.     void merge(pnode &t, pnode l, pnode r) {
  60.         if (!l || !r) {
  61.             t = l ? l : r;
  62.         } else if (l->prior <= r->prior) {
  63.             merge(r->l, l, r->l), t = r;
  64.         } else {
  65.             merge(l->r, l->r, r), t = l;
  66.         }
  67.         updCnt(t);
  68.     }
  69.  
  70.     void erase(pnode &t, int key) {
  71.         if (!t) {
  72.             return;
  73.         }
  74.         if (t->key == key) {
  75.             pnode temp = t;
  76.             merge(t, t->l, t->r);
  77.             delete temp;
  78.         } else {
  79.             erase(key <= t->key ? t->l : t->r, key);
  80.         }
  81.     }
  82.  
  83.     int query(pnode t, int key) {   // key == position
  84.         pnode l(nullptr), r(nullptr);
  85.         split(t, key - 1, l, r);
  86.         int res = (l ? l->cnt : 0);
  87.         merge(t, l, r);
  88.         return res;
  89.     }
  90.  
  91. public:
  92.     Treap() : root(nullptr) {};
  93.  
  94.     void insert(int key) {
  95.         insert(this->root, new Node(key));
  96.     }
  97.  
  98.     void erase(int key) {
  99.         erase(this->root, key);
  100.     }
  101.  
  102.     int query(int key) {
  103.         return query(this->root, key);
  104.     }
  105. };
  106.  
  107. int main() {
  108.     int N, Q;
  109.     scanf("%d %d", &N, &Q);
  110.     vector<int> a(N);
  111.     map<int, Treap> vegTypeTreap;
  112.  
  113.     for (int i = 0; i < N; ++i) {
  114.         scanf("%d", &a[i]);
  115.         vegTypeTreap[a[i]].insert(i);
  116.     }
  117.  
  118.     int pos, vegType;
  119.     while (Q--) {
  120.         scanf("%d %d", &pos, &vegType);
  121.         Treap *t = &vegTypeTreap[vegType];
  122.         printf("%d\n", t->query(pos));
  123.         if (a[pos] != vegType) {
  124.             vegTypeTreap[a[pos]].erase(pos);
  125.             vegTypeTreap[vegType].insert(pos);
  126.             a[pos] = vegType;
  127.         }
  128.     }
  129.  
  130.     return 0;
  131. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/te9lsN
problem ADACROP, based on SPOJ submission 28378890 (CPP14), 2021-09-01 19:20:30
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!