CFR 785 E. Anton and Permutation ( RBST on BIT )

Problem - E - Codeforces

題意：
一開始你有一個序列 P = { 1, 2, 3, .. N }。處理 Q 筆永久詢問，給 L, R，將 P[ L ] 和 P[ R ] 交換後，輸出當前 P 的逆序述對數。

資料規模：
The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000) — the length of the permutation and the number of operations that Anton does. Each of the following q lines of the input contains two integers li and ri (1 ≤ li, ri ≤ n) — the indices of elements that Anton swaps during the i-th operation. Note that indices of elements that Anton swaps during the i-th operation can coincide. Elements in the permutation are numbered starting with one.

解法：
想像線段樹，每個節點都是一個 RBST，每個描述該區間的所有數值。首先空間是沒有問題的，因為有 lg N 層，每層 N 個元素，所以空間是 O( N lg N )。麻煩的是子樹的合併，這我真的不知道怎麼做。但如果用的是 BIT，就不必處理合併。

時間 / 空間複雜度：
O( N lg^2 N ) / O( N lg N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;

int N, Q;
int P[ MAXN + 1 ]; // everything 1 base

struct RBST{
  int val;
  int size;
  RBST *lc, *rc;
  RBST( int v = 0 ){
    val = v;
    size = 1;
    lc = rc = NULL;
  }
  void pull(){
    size = 1;
    if( lc ) size += lc->size;
    if( rc ) size += rc->size;
  }
} *ftree[ MAXN + 1 ];

int get_size( RBST *t ){
  return t ? t->size : 0;
}

void split( RBST *t, int k, RBST *&a, RBST *&b ){
  if( not t ) return ( void ) ( a = b = NULL );
  if( k <= get_size( t->lc ) ){
    b = t;
    split( t->lc, k, a, b->lc );
    b->pull();
  } else{
    a = t;
    split( t->rc, k - get_size( t->lc ) - 1, a->rc, b );
    a->pull();
  }
}

RBST* merge( RBST *a, RBST *b ){
  if( not a or not b ) return a ? a : b;
  if( rand() % ( a->size + b->size ) < a->size ){
    a->rc = merge( a->rc, b );
    a->pull();
    return a;
  } else{
    b->lc = merge( a, b->lc );
    b->pull();
    return b;
  }
}

int lower_bound( RBST *t, int v ){
  if( not t ) return 0;
  if( v <= t->val ) return lower_bound( t->lc, v );
  return get_size( t->lc ) + 1 + lower_bound( t->rc, v );
}

void emplace( int x, int v ){
  for( int i = x; i <= N; i += i & -i ){
    RBST *f, *g;
    int r = lower_bound( ftree[ i ], v );
    split( ftree[ i ], r, f, g );
    ftree[ i ] = merge( f, merge( new RBST( v ), g ) );
  }
}

void remove( int x, int v ){
  for( int i = x; i <= N; i += i & -i ){
    RBST *f, *g, *h, *p;
    int r = lower_bound( ftree[ i ], v );
    split( ftree[ i ], r, f, g );
    split( g, 1, h, p );
    ftree[ i ] = merge( f, p );
  }
}

int sum( int x, int v ){
  int res = 0;
  for( int i = x; i; i -= i & -i ){
    res += lower_bound( ftree[ i ], v );
  }
  return res;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> Q;
  for( int i = 1; i <= N; ++i ){
    P[ i ] = i;
    emplace( i, P[ i ] );
  }
  long long ans = 0LL;
  for( int qi = 0; qi < Q; ++qi ){
    int L, R; cin >> L >> R;
    if( L == R ){
      cout << ans << "\n";
      continue;
    }
    if( not ( L < R ) ) swap( L, R );
    ans -= sum( R - 1, P[ L ] ) - sum( L, P[ L ] );
    ans += ( R - L - 1 ) - ( sum( R - 1, P[ L ] ) - sum( L, P[ L ] ) );
    ans -= ( R - L - 1 ) - ( sum( R - 1, P[ R ] ) - sum( L, P[ R ] ) );
    ans += sum( R - 1, P[ R ] ) - sum( L, P[ R ] );
    if( P[ L ] < P[ R ] ) ++ans;
    else --ans;
    cout << ans << "\n";
    remove( L, P[ L ] );
    remove( R, P[ R ] );
    emplace( L, P[ R ] );
    emplace( R, P[ L ] );
    swap( P[ L ], P[ R ] );
  }
  return 0;
}