fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define PhTrNghia "ONLINV"
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e5 + 5;
  9.  
  10. struct fenwick_tree{
  11.     int n;
  12.     vector <int> tree;
  13.     fenwick_tree(int _n){
  14.         n = _n;
  15.         tree.assign(n + 5, 0);
  16.     }
  17.  
  18.     void update(int pos, int val){
  19.         for (; pos <= n; pos += -pos&pos) tree[pos] += val;
  20.     }
  21.  
  22.     int get(int pos){
  23.         int res = 0;
  24.         for (; pos; pos -= -pos&pos) res += tree[pos];
  25.         return res;
  26.     }
  27.  
  28.     int get(int l, int r){
  29.         if (l > r) return 0;
  30.         return get(r) - get(l - 1);
  31.     }
  32. };
  33.  
  34. struct persistent_segtree{
  35.     struct node{
  36.         int sum;
  37.         node *l, *r;
  38.         node(){
  39.             sum = 0;
  40.             l = NULL;
  41.             r = NULL;
  42.         }
  43.  
  44.         node(node *p){
  45.             sum = p->sum;
  46.             l = p->l;
  47.             r = p->r;
  48.         }
  49.     };
  50.  
  51.     int n;
  52.     vector <node*> root;
  53.  
  54.     persistent_segtree(int _n){
  55.         n = _n;
  56.         root.assign(n + 5, NULL);
  57.         root[0] = new node();
  58.     }
  59.  
  60.     void pull(int id){
  61.         root[id] = new node(root[id - 1]);
  62.     }
  63.  
  64.     node* update(node* id, int l, int r, int pos, int val){
  65.         if(!id) id = new node();
  66.  
  67.         if (pos < l || pos > r) return id;
  68.  
  69.         node* now = new node(id); 
  70.  
  71.         if (l == r){
  72.             now->sum += val;
  73.             return now;
  74.         }
  75.  
  76.         int mid = (l + r) >> 1;
  77.  
  78.         now->l = update(id->l, l, mid, pos, val);
  79.         now->r = update(id->r, mid + 1, r, pos, val);
  80.  
  81.         int left_sum  = now->l ? now->l->sum : 0;
  82.         int right_sum = now->r ? now->r->sum : 0;
  83.  
  84.         now->sum = left_sum + right_sum;
  85.  
  86.         return now;
  87.     }
  88.  
  89.     void update(int version, int pos, int val){
  90.         root[version] = update(root[version], 1, n, pos, val);
  91.     }
  92.  
  93.     int get(node* id, int l, int r, int u, int v){
  94.         if(!id || r < u || l > v) return 0;
  95.  
  96.         if (u <= l && r <= v) return id->sum;
  97.  
  98.         int mid = (l + r) >> 1;
  99.  
  100.         return get(id->l, l, mid, u, v) + get(id->r, mid + 1, r, u, v);
  101.     }
  102.  
  103.     int get(int version, int l, int r){
  104.         return get(root[version], 1, n, l, r);
  105.     }
  106. };
  107.  
  108. fenwick_tree bit(maxn);
  109.  
  110. int n, a[maxn], inv[maxn];
  111. vector <int> pos[maxn];
  112. multiset <int> ans;
  113. set <int> st;
  114.  
  115. int calc(int l, int r){
  116.     int res = 0;
  117.     for (int i = r; i >= l; i--){
  118.         res += bit.get(a[i] - 1);
  119.         bit.update(a[i], 1);
  120.     }
  121.     for (int i = l; i <= r; i++) bit.update(a[i], -1);
  122.     return res;
  123. }
  124.  
  125. int get(int val, int l, int r){
  126.     int res = 0;
  127.     for (int i = l; i <= r; i++) if (a[i] <= val) res++;
  128.     return res;
  129. }
  130.  
  131. signed main(){
  132.     ios_base::sync_with_stdio(false);
  133.     cin.tie(0); cout.tie(0);
  134.     if (fopen(PhTrNghia".iNP", "r")){
  135.         freopen(PhTrNghia".iNP", "r", stdin);
  136.         freopen(PhTrNghia".OUT", "w", stdout);
  137.     }
  138.     cin >> n;
  139.     persistent_segtree smt(n);
  140.     for (int i = 1; i <= n; i++){ 
  141.         cin >> a[i];
  142.         pos[a[i]].push_back(i);
  143.     }
  144.  
  145.     for (int i = 1; i <= n; i++){
  146.         smt.pull(i);
  147.         for (int p: pos[i]) smt.update(i, p, 1);
  148.     }
  149.  
  150.     inv[1] = calc(1, n);
  151.     ans.insert(inv[1]);
  152.     st.insert(1);
  153.     st.insert(n + 1);
  154.     int last = 0;
  155.  
  156.     for (int i = 1; i <= n; i++){
  157.         int p;
  158.         cin >> p;
  159.         p ^= last;
  160.  
  161.         auto pos_r = st.upper_bound(p);
  162.         auto pos_l = prev(pos_r);
  163.  
  164.         int l = *pos_l;
  165.         int r = *pos_r - 1;
  166.  
  167.         int u1 = l, v1 = p - 1;
  168.         int u2 = p + 1, v2 = r;
  169.  
  170.         int i1 = inv[l];
  171.         int im = get(a[p] - 1, u2, v2) + (v1 - u1 + 1 - smt.get(a[p], u1, v1));
  172.  
  173.         int i2, i3, i23;
  174.         if (v1 - u1 < v2 - u2){
  175.             i2 = calc(u1, v1);
  176.             i23 = 0;
  177.             for (int j = u1; j <= v1; j++) i23 += smt.get(a[j] - 1, u2, v2);
  178.             i3 = i1 - i2 - i23 - im;
  179.         } else {
  180.             i3 = calc(u2, v2);
  181.             i23 = 0;
  182.             for (int j = u2; j <= v2; j++) i23 += v1 - u1 + 1 - smt.get(a[j], u1, v1);
  183.             i2 = i1 - i3 - i23 - im;
  184.         }
  185.  
  186.         ans.erase(ans.find(i1));
  187.         ans.insert(i2);
  188.         ans.insert(i3);
  189.  
  190.         inv[l] = i2;
  191.         inv[p + 1] = i3;
  192.  
  193.         st.insert(p);
  194.         st.insert(p + 1);
  195.  
  196.         last = *ans.rbegin();
  197.         cout << last << ' ';
  198.     }
  199.     return 0;
  200. }
Success #stdin #stdout 0.01s 10972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mpAjfr
language:
C++14 (gcc 8.3)
created:
1 day 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!