fork download
copy 
  1.     #include <bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     int a[250006], n, s_size,m;
  6.     pair<long long, long long> pr;
  7.     long long sum = 0; 
  8.     vector<int> sq[506];
  9.  
  10.     inline void init() {
  11.         s_size = ceil(sqrt(n));
  12.         sq[0].push_back(a[0]);
  13.         for (int i = 1; i < n; i++) {
  14.             sq[i / s_size].push_back(a[i]);
  15.         }
  16.         for (int i = 0; i < s_size; i++) {
  17.             sort(sq[i].begin(), sq[i].end());
  18.         }
  19.     }
  20.  
  21.     inline void update(int index, int val) {
  22.         int sindex = index / s_size;
  23.         vector<int>& v = sq[sindex];
  24.         vector<int>::iterator it = lower_bound(v.begin(), v.end(), a[index]);
  25.         v.erase(it);
  26.         it = upper_bound(v.begin(), v.end(), val);
  27.         v.insert(it, val);
  28.         a[index] = val;
  29.     }
  30.  
  31.     inline int between(vector<int>& v, int s, int e) {
  32.         return upper_bound(v.begin(), v.end(), e) - lower_bound(v.begin(), v.end(), s);
  33.     }
  34.  
  35.     inline void between(int index, int s, int e) {
  36.         pr.first = 0;
  37.         pr.second = 0;
  38.         int ee = ((s_size + index) / s_size) * s_size;
  39.         int ss = (index / s_size) * s_size;
  40.         for (int i = ss; i < index; i++) {
  41.             if (a[i] > s && a[i] <= e)
  42.                 pr.first++;
  43.         }
  44.         for (int i = index + 1; i < ee; i++) {
  45.             if (a[i] >= s && a[i] < e)
  46.                 pr.second++;
  47.         }
  48.         ss = (index / s_size);
  49.         for (int i = 0; i < ss; i++) {
  50.             pr.first += between(sq[i], s + 1, e);
  51.         }
  52.         for (int i = ss + 1; i < s_size; i++) {
  53.             pr.second += between(sq[i], s, e - 1);
  54.         }
  55.     }
  56.  
  57.     struct trie_nod {
  58.         trie_nod* t[2];
  59.         long long c[2];
  60.  
  61.         trie_nod() {
  62.             t[0] = t[1] = NULL;
  63.             c[0] = c[1] = 0;
  64.         }
  65.     };
  66.  
  67.     struct trie {
  68.         trie_nod* root = new trie_nod();
  69.  
  70.         int insert(int x) {
  71.             bool index;
  72.             long long cnt = 0;
  73.             trie_nod* curr = root;
  74.             for (int i = 16; i >= 0; i--) {
  75.                 index = (((1 << i) & x) != 0);
  76.                 if(!index)
  77.                     cnt += curr->c[1];
  78.                 curr->c[index]++;
  79.                 if (curr->t[index] == NULL)
  80.                     curr->t[index] = new trie_nod();
  81.                 curr = curr->t[index];
  82.             }   
  83.             return cnt;
  84.         }
  85.     };
  86.  
  87.     int main() {
  88.         trie tr;
  89.         scanf("%d", &n);
  90.         sum = 0;
  91.         for (int i = 0; i < n; i++) {
  92.             scanf("%d", &a[i]);
  93.             sum += tr.insert(a[i]);
  94.         }
  95.         init();
  96.         scanf("%d", &m);
  97.         while (m--) {
  98.             int x, y;
  99.             scanf("%d%d", &x, &y);
  100.             x--;
  101.             if (a[x] < y) {
  102.                 between(x, a[x], y);
  103.                 sum -= pr.first;
  104.                 sum += pr.second;
  105.                 update(x, y);
  106.             } else if (a[x] > y) {
  107.                 between(x, y, a[x]);
  108.                 sum += pr.first;
  109.                 sum -= pr.second;
  110.                 update(x, y);
  111.             }
  112.             printf("%lld\n", sum);
  113.         }
  114.         return 0;
  115.     }
Success #stdin #stdout 0s 17056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AXbUjx
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!