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

Problem - E - Codeforces

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.

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;
}
```