用树状数组求逆序对数。。。
#include#include #include #include #include #define MAX 3000005#define MaxN 10005using namespace std;int ans[MAX];__int64 c[MaxN];inline void updata( int s ){ while( s < MaxN ) { c[s]++; s += ( s & (-s) ); }}inline __int64 getsum( int s ){ __int64 sum = 0; while( s >= 1 ) { sum += c[s]; s -= s & -s; } return sum; }inline void getint( int &t ) { char c; while( c= getchar(), c< '0'|| c> '9' ) ; t= c- '0'; while( c= getchar(), c>= '0'&& c<= '9' ) { t= t* 10+ c- '0'; } }int main(){ int N, M; char op[5]; while( scanf( "%d", &N ) == 1 ) { __int64 sum = 0; memset( c, 0, sizeof( c ) ); for( int i = 0; i < N; ++i ) { getint( ans[i] ); updata( ans[i]+1 ); sum += getsum( ans[i] ); } scanf( "%d", &M ); while( M-- ) { scanf( "%s", op ); switch( op[0] ) { case 'Q': { printf( "%I64d\n", sum ); break; } case 'R': { int s, e, v; scanf( "%d %d", &s, &e ); v = ans[s]; for( int i = s; i < e; ++i ) { ans[i] = ans[i+1]; if( v < ans[i] ) sum--; if( v > ans[i] ) sum++; } ans[e] = v; break; } } } } return 0;}