fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int MX = 100005;
  6. int n;
  7. int a[MX], I[MX];
  8. vector<int> pos[MX];
  9.  
  10. struct Node{
  11.     int sum;
  12.     Node *l, *r;
  13.     Node() : sum(0), l(nullptr), r(nullptr) {}
  14.     Node(Node *p) : sum(p->sum), l(p->l), r(p->r) {}
  15. };
  16.  
  17. struct SMT{
  18.     int n;
  19.     vector<Node*> root;
  20.  
  21.     SMT(int n = 0) : n(n), root(n + 5, nullptr) {
  22.         root[0] = new Node;
  23.     }
  24.  
  25.     void pull(int id){
  26.         root[id] = new Node(root[id - 1]);
  27.     }
  28.  
  29.     void update(int pos, int val){
  30.         Node *cur = root[val];
  31.         for(int lo=1, hi=n; lo<hi;){
  32.             int mid = (lo + hi)>>1;
  33.             cur->sum++;
  34.             if(pos <= mid){
  35.                 cur->l = cur->l ? new Node(cur->l) : new Node;
  36.                 cur = cur->l;
  37.                 hi = mid;
  38.             }
  39.             else{
  40.                 cur->r = cur->r ? new Node(cur->r) : new Node;
  41.                 cur = cur->r;
  42.                 lo = mid + 1;
  43.             }
  44.         }
  45.         cur->sum++;
  46.     }   
  47.  
  48.     int get(Node *cur, int l, int r, const int &u, const int &v){
  49.         if(cur == nullptr || l > v || r < u) return 0;
  50.         if(l >= u && r <= v) return cur->sum;
  51.         int mid = (l + r)>>1;
  52.         return get(cur->l, l, mid, u, v) + get(cur->r, mid + 1, r, u, v);
  53.     }
  54.  
  55.     int get(int id, int l, int r){
  56.         return get(root[id], 1, n, l, r);
  57.     }
  58. } smt(MX);
  59.  
  60. struct BIT{
  61.     int n;
  62.     vector<int> tree;
  63.  
  64.     BIT(int n = 0) : n(n) ,tree(n + 5, 0) {}
  65.  
  66.     void update(int idx, int val){
  67.         for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
  68.     }
  69.  
  70.     int get(int idx){
  71.         int res = 0;
  72.         for(; idx; idx-=-idx&idx) res += tree[idx];
  73.         return res;
  74.     }
  75.  
  76.     void rupd(int idx, int val){
  77.         for(; idx; idx-=-idx&idx) tree[idx] += val;
  78.     }
  79.  
  80.     int rget(int idx){
  81.         int res = 0;
  82.         for(; idx<=n; idx+=-idx&idx) res += tree[idx];
  83.         return res;
  84.     }
  85. } bit(MX);
  86.  
  87. int calc_inversion(int l, int r){
  88.     int res = 0;
  89.     for(int i=r; i>=l; i--){
  90.         res += bit.get(a[i] - 1);
  91.         bit.update(a[i], 1);
  92.     }
  93.     for(int i=l; i<=r; i++) bit.update(a[i], -1);
  94.     return res;
  95. }
  96.  
  97. int get(int val, int l, int r){
  98.     int res = 0;
  99.     for (int i = l; i <= r; i++) if (a[i] <= val) res++;
  100.     return res;
  101. }
  102.  
  103. int32_t main(){
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(0);
  106.  
  107.     freopen("onlinv.inp","r",stdin);
  108.     freopen("onlinv.out","w",stdout);
  109.  
  110.     cin >> n;
  111.     for(int i=1; i<=n; i++) cin >> a[i];
  112.     for(int i=1; i<=n; i++) pos[a[i]].push_back(i);
  113.     for(int i=1; i<=n; i++){
  114.         smt.pull(i);
  115.         for(int p: pos[i]) smt.update(p, i);
  116.     }
  117.  
  118.     int last = 0;
  119.     set<int> st;
  120.     st.insert(1);
  121.     st.insert(n + 1);
  122.     I[1] = calc_inversion(1, n);
  123.     multiset<int> answer;
  124.     answer.insert(I[1]);
  125.  
  126.     for(int i=1; i<=n; i++){
  127.         int p;
  128.         cin >> p;
  129.         p = p ^ last;
  130.  
  131.         auto pR = st.upper_bound(p);
  132.         auto pL = prev(pR);
  133.  
  134.         int l = *pL;
  135.         int r = *pR - 1;
  136.  
  137.         int u1 = l, v1 = p - 1; // left range
  138.         int u2 = p + 1, v2 = r; // right range
  139.  
  140.         int I1 = I[l];
  141.         int Ip = get(a[p] - 1, u2, v2) + (v1 - u1 + 1 - get(a[p], u1, v1));
  142.         int I2, I23, I3;
  143.         if(v1 - u1 < v2 - u2){
  144.             I2 = calc_inversion(u1, v1);
  145.             I23 = 0;
  146.             for(int j=u1; j<=v1; j++){
  147.                 I23 += smt.get(a[j] - 1, u2, v2);
  148.             }
  149.             I3 = I1 - I2 - I23 - Ip;
  150.         }
  151.         else{
  152.             I3 = calc_inversion(u2, v2);
  153.             I23 = 0;
  154.             for(int j=u2; j<=v2; j++){
  155.                 I23 += v1 - u1 + 1 - smt.get(a[j], u1, v1);
  156.             }
  157.             I2 = I1 - I3 - I23 - Ip;
  158.         }
  159.  
  160.         // remove I1
  161.         // insert I2, I3
  162.         answer.erase(answer.find(I1));
  163.         answer.insert(I2);
  164.         answer.insert(I3);
  165.  
  166.         I[l] = I2;
  167.         I[p + 1] = I3;
  168.  
  169.         st.insert(p);
  170.         st.insert(p + 1);
  171.  
  172.         last = *answer.rbegin();
  173.         cout << last << ' ';
  174.     }
  175.  
  176.     return 0;
  177. }
  178.  
Success #stdin #stdout 0.01s 8044KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OSVtIF
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!