fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int a[250006], n, s_size, m;
  6. long long sum = 0;
  7.  
  8. struct trie_nod_idx {
  9.     trie_nod_idx* t[2];
  10.     int c[2];
  11.  
  12.     trie_nod_idx() {
  13.         t[0] = t[1] = NULL;
  14.         c[0] = c[1] = 0;
  15.     }
  16. };
  17.  
  18. struct trie_idx {
  19.     trie_nod_idx* root;
  20.  
  21.     trie_idx() {
  22.         root = new trie_nod_idx();
  23.     }
  24.  
  25.     inline void insert(int &x) {
  26.         bool index;
  27.         trie_nod_idx* curr = root;
  28.         for (int i = 17; i >= 0; i--) {
  29.             index = (((1 << i) & x) != 0);
  30.             curr->c[index]++;
  31.             if (curr->t[index] == NULL) {
  32.                 curr->t[index] = new trie_nod_idx();
  33.             }
  34.             curr = curr->t[index];
  35.         }
  36.     }
  37.  
  38.     inline int greater(int &x) {
  39.         int cnt = 0;
  40.         bool index;
  41.         trie_nod_idx* curr = root;
  42.         for (int i = 17; i >= 0 && curr != NULL; i--) {
  43.             index = (((1 << i) & x) != 0);
  44.  
  45.             if (!index)
  46.                 cnt += curr->c[1];
  47.             curr = curr->t[index];
  48.         }
  49.         return cnt;
  50.     }
  51.  
  52.     inline int less(int &x) {
  53.         int cnt = 0;
  54.         bool index;
  55.         trie_nod_idx* curr = root;
  56.         for (int i = 17; i >= 0 && curr != NULL; i--) {
  57.             index = (((1 << i) & x) != 0);
  58.             if (index)
  59.                 cnt += curr->c[0];
  60.             curr = curr->t[index];
  61.         }
  62.         return cnt;
  63.     }
  64. };
  65.  
  66. struct trie_nod {
  67.     trie_nod* t[2];
  68.     int c[2];
  69.     vector<int> idx;
  70.     trie_idx removed;
  71.     trie_idx added;
  72.  
  73.     trie_nod() {
  74.         t[0] = t[1] = NULL;
  75.         c[0] = c[1] = 0;
  76.     }
  77. };
  78.  
  79. struct trie {
  80.     trie_nod* root = new trie_nod();
  81.  
  82.     inline int insert_f(int x, int idx) {
  83.         bool index;
  84.         int cnt = 0;
  85.         trie_nod* curr = root;
  86.         for (int i = 15; i >= 0; i--) {
  87.             index = (((1 << i) & x) != 0);
  88.             if (!index)
  89.                 cnt += curr->c[1];
  90.             curr->c[index]++;
  91.             if (index) {
  92.                 curr->idx.push_back(idx);
  93.             }
  94.             if (curr->t[index] == NULL) {
  95.                 curr->t[index] = new trie_nod();
  96.             }
  97.             curr = curr->t[index];
  98.         }
  99.         return cnt;
  100.     }
  101.  
  102.     inline int insert(int x, int idx) {
  103.         bool index;
  104.         trie_nod* curr = root;
  105.         for (int i = 15; i >= 0; i--) {
  106.             index = (((1 << i) & x) != 0);
  107.             if (index) {
  108.                 curr->added.insert(idx);
  109.             }
  110.             if (curr->t[index] == NULL) {
  111.                 curr->t[index] = new trie_nod();
  112.             }
  113.             curr = curr->t[index];
  114.         }
  115.     }
  116.  
  117.     inline void remove(int x, int idx) {
  118.         bool index;
  119.         trie_nod* curr = root;
  120.         for (int i = 15; i >= 0; i--) {
  121.             index = (((1 << i) & x) != 0);
  122.             if (index) {
  123.                 curr->removed.insert(idx);
  124.             }
  125.             curr = curr->t[index];
  126.         }
  127.     }
  128.  
  129.     inline int greater_a(int x, int idx) {
  130.         int cnt = 0;
  131.         bool index;
  132.         trie_nod* curr = root;
  133.         for (int i = 15; i >= 0 && curr != NULL; i--) {
  134.             index = (((1 << i) & x) != 0);
  135.             if (!index) {
  136.                 cnt += curr->idx.end() - upper_bound(curr->idx.begin(), curr->idx.end(), idx);
  137.                 cnt += curr->added.greater(idx);
  138.                 cnt -= curr->removed.greater(idx);
  139.             }
  140.             curr = curr->t[index];
  141.         }
  142.         return cnt;
  143.     }
  144.  
  145.     inline int greater_b(int x, int idx) {
  146.         int cnt = 0;
  147.         bool index;
  148.         trie_nod* curr = root;
  149.         for (int i = 15; i >= 0 && curr != NULL; i--) {
  150.             index = (((1 << i) & x) != 0);
  151.             if (!index) {
  152.                 cnt += lower_bound(curr->idx.begin(), curr->idx.end(), idx) - curr->idx.begin();
  153.                 cnt += curr->added.less(idx);
  154.                 cnt -= curr->removed.less(idx);
  155.             }
  156.             curr = curr->t[index];
  157.         }
  158.         return cnt;
  159.     }
  160.  
  161.     inline int between_a(int x, int y, int idx) {
  162.         return greater_a(x - 1, idx) - greater_a(y, idx);
  163.     }
  164.  
  165.     inline int between_b(int x, int y, int idx) {
  166.         return greater_b(x - 1, idx) - greater_b(y, idx);
  167.     }
  168. };
  169.  
  170. int main() {
  171.     trie tr;
  172.     scanf("%d", &n);
  173.     sum = 0;
  174.     for (int i = 0; i < n; i++) {
  175.         scanf("%d", &a[i]);
  176.         sum += tr.insert_f(a[i], i);
  177.     }
  178.     scanf("%d", &m);
  179.     while (m--) {
  180.         int x, y;
  181.         scanf("%d%d", &x, &y);
  182.         x--;
  183.         if (a[x] < y) {
  184.             sum -= tr.between_b(a[x] + 1, y, x);
  185.             sum += tr.between_a(a[x], y - 1, x);
  186.             tr.remove(a[x], x);
  187.             tr.insert(y, x);
  188.             a[x] = y;
  189.         } else if (a[x] > y) {
  190.             sum += tr.between_b(y + 1, a[x], x);
  191.             sum -= tr.between_a(y, a[x] - 1, x);
  192.             tr.remove(a[x], x);
  193.             tr.insert(y, x);
  194.             a[x] = y;
  195.         }
  196.         printf("%lld\n", sum);
  197.     }
  198.     return 0;
  199. }
Success #stdin #stdout 0s 17040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DPNHsS
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!