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


Problem Description
Recently, dobby is addicted in the Fruit Ninja. As you know, dobby is a free elf, so unlike other elves, he could do whatever he wants.But the hands of the elves are somehow strange, so when he cuts the fruit, he can only make specific move of his hands. Moreover, he can only start his hand in point A, and then move to point B,then move to point C,and he must make sure that point A is the lowest, point B is the highest, and point C is in the middle. Another elf, Kreacher, is not interested in cutting fruits, but he is very interested in numbers.Now, he wonders, give you a permutation of 1 to N, how many triples that makes such a relationship can you find ? That is , how many (x,y,z) can you find such that x < z < y ?
 

 

Input
The first line contains a positive integer T(T <= 10), indicates the number of test cases.For each test case, the first line of input is a positive integer N(N <= 100,000), and the second line is a permutation of 1 to N.
 

 

Output
For each test case, ouput the number of triples as the sample below, you just need to output the result mod 100000007.
 

 

Sample Input
2
6
1 3 2 6 5 4
5
3 5 2 4 1
 

 

Sample Output
Case #1: 10
Case #2: 1
 
给一个序列 , n个数, (1~n )
问当中有多少个3元组符合 ( Ax , Ay , Az ) && ( Ax < Az < Ay ) , ( x < y < z )
 
当我们插入一个新的数 y 的时候 , 对于之前每个小于y的数 x 。
就有 y - x - 1 个数在 ( x , y ) 这个开区间内 。
我们想要知道有多少个数在( x , y ) 中并 y 的右边 。
 
做法是设2个树状数组 , 一个维护数的个数, 一个维护数的和 。
当我们插入一个数y,的时候 。
用第一个树状数组求出 cnt 为在y左边并且小于y的数的个数。
第二个树状数组求出 sum 为在y左边并且小于y的数的总和。
 
那么 ( y - 1 ) * cnt - sum 就是在 ( x , y ),( 0 <= x < y ) 区间内的数的总数
然后再减去那些在 y 左边并且在区间( x , y )中的数的总数 cnt*(cnt-1)/2 个 , 加入结果中即可 。
 
 
技术分享
#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);
    }
}
View Code

 

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。