用樹狀數(shù)組求逆序?qū)?shù)。。。

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #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; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU-2688 Rotate的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。