题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2141
很奇怪这样的裸题怎么没什么人写。。。用Bit套Bst暴力维护逆序对就可以了。
代码(Bit+Sbt 很长很丑很挫很慢)：
83025aafa40f4bfb1c97a22f014f78f0f7361801.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXV 1000100
#define MAXN 20010
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define K( t ) key[ t ]
#define S( t ) size[ t ]
#define update( t )S( t )=S(L( t ))+S(R( t ))+1
#define clear( t )memset( t ,0,sizeof( t ))
#define lowbit( t )((- t )& t )
int left[ MAXV ], right[ MAXV ], key[ MAXV ], size[ MAXV ], V =0;
void left_ratote(int&t ){
int k =R( t );
R( t )=L( k );update( t );
L( k )= t ;update( k );
t = k ;
}
void right_ratote(int&t ){
int k =L( t );
L( t )=R( k );update( t );
R( k )= t ;update( k );
t = k ;
}
void maintain(int&t ){
if(S(L(L( t )))>S(R( t ))){
right_ratote( t );maintain(R( t ));maintain( t );
return;
}
if(S(R(L( t )))>S(R( t ))){
left_ratote(L( t ));right_ratote( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
if(S(R(R( t )))>S(L( t ))){
left_ratote( t );maintain(L( t ));maintain( t );
return;
}
if(S(L(R( t )))>S(L( t ))){
right_ratote(R( t ));left_ratote( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
}
void Insert(int&t ,int k ){
if(! t ){
t =++ V ;S( t )=1,K( t )= k ;
return;
}
S( t )++;
Insert( k <K( t )?L( t ):R( t ), k );
maintain( t );
}
void Delete(int&t ,int k ){
if( k ==K( t )){
if(!L( t )){
t =R( t );return;
}else if(!R( t )){
t =L( t );return;
}else{
right_ratote( t );Delete(R( t ), k );
}
}else Delete( k <K( t )?L( t ):R( t ), k );
update( t );maintain( t );
}
int rank_inc(int t ,int k ){
if(! t )return 0;
return k <=K( t )?rank_inc(L( t ), k ):(rank_inc(R( t ), k )+S(L( t ))+1);
}
int rank_dec(int t ,int k ){
if(! t )return 0;
return k >=K( t )?rank_dec(R( t ), k ):(rank_dec(L( t ), k )+S(R( t ))+1);
}
int bit[ MAXN ], a[ MAXN ], n , m ;
void bit_add(int x ,int y ){
for(int i = x ; i <= n ; i +=lowbit( i ))Insert( bit[ i ], y );
}
void bit_erase(int x ,int y ){
for(int i = x ; i <= n ; i +=lowbit( i ))Delete( bit[ i ], y );
}
int bitsum_inc(int x ,int y ){
int rec =0;
for(int i = x ; i ; i -=lowbit( i )) rec +=rank_inc( bit[ i ], y );
return rec ;
}
int bitsum_dec(int x ,int y ){
int rec =0;
for(int i = x ; i ; i -=lowbit( i )) rec +=rank_dec( bit[ i ], y );
return rec ;
}
int main( ){
clear( left ),clear( right ),clear( size ),clear( key ),clear( bit );
scanf("%d",&n );for(int i =0; i ++< n ;)scanf("%d",&a[ i ]);
for(int i =0; i ++< n ;)bit_add( i , a[ i ]);
int ans =0;
for(int i =0; i ++< n ;){
ans +=bitsum_dec( i , a[ i ]);
}
printf("%d\n", ans );
scanf("%d",&m );
while( m --){
int x , y ;scanf("%d%d",&x ,&y );
ans -=bitsum_dec( x , a[ x ]);
ans -=(bitsum_inc( n , a[ x ])-bitsum_inc( x , a[ x ]));
bit_erase( x , a[ x ]);
ans -=bitsum_dec( y , a[ y ]);
ans -=(bitsum_inc( n , a[ y ])-bitsum_inc( y , a[ y ]));
bit_erase( y , a[ y ]);
ans +=bitsum_dec( y , a[ x ]);
ans +=(bitsum_inc( n , a[ x ])-bitsum_inc( y , a[ x ]));
bit_add( y , a[ x ]);
ans +=bitsum_dec( x , a[ y ]);
ans +=(bitsum_inc( n , a[ y ])-bitsum_inc( x , a[ y ]));
bit_add( x , a[ y ]);
swap( a[ x ], a[ y ]);
printf("%d\n", ans );
}
return 0;
}
