HDU 4000 Fruit Ninja(树状数组)
Fruit Ninja
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1831 Accepted Submission(s): 719
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <map> #include <vector> #include <queue> using namespace std ; typedef long long LL ; typedef pair<int,int> pii; #define X first #define Y second const int N = 100010; const int mod = 100000007 ; int n , x[N]; LL c[N][2]; int lowbit( int x ){ return x&-x ;} void init(){ memset( c , 0 , sizeof c ); } void update( int pos , LL key , int b ) { if( pos == 0 ) return ; while( pos < n+10 ){ c[pos][b] = ( c[pos][b] + key ) % mod ; pos += lowbit(pos); } } LL query( int pos , int b ){ LL ans = 0 ; while( pos > 0 ) { ans = ( ans + c[pos][b] ) %mod ; pos -= lowbit(pos) ; } return ans ; } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int _ , cas =1 ; scanf("%d",&_); while( _-- ) { printf("Case #%d: ",cas++); init() ; scanf("%d",&n); for( int i = 1 ; i <= n ; ++i ) { scanf("%d",&x[i]); } LL ans = 0 ; for( int i = 1 ; i <= n ; ++i ) { update( x[i] , 1 , 0 ); update( x[i] , x[i] , 1 ); LL cnt = query( x[i] - 1 , 0 ) , sum = query( x[i]-1 , 1 ) ; LL tmp = cnt * ( cnt - 1 ) / 2 ; ans = ( ans + 1LL*( x[i] - 1 ) * cnt - sum - tmp ) % mod ; // cout << cnt << ‘ ‘ << sum << ‘ ‘ << tmp << ‘ ‘ << ans << endl ; } printf("%lld\n",ans); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。