HDU 4000 Fruit Ninja 树状数组 + 计数

给你N的一个排列，求满足：a[i] < a[k] < a[j] 并且i < j < k的三元组有多少个。

一步转化：

求出所有满足 a[i] < a[k] < a[j] 并且i < j < k的三元组与 a[i] < a[k] < a[j] 并且i < k < j的三元组的个数的总和，设high[i]为在 i 右侧且大于a[i] 的数的个数，上述总和即为：high[i] * (high[i] - 1) / 2。

设low[i]为在 i 左侧且小于a[i] 的数的个数, a[i] < a[k] < a[j] 并且i < k < j的三元组的个数即为：low[i]*high[i]。

答案即为：∑( high[i] * (high[i] - 1) / 2 - low[i]*high[i] );

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 #define LL long long int
 7 
 8 using namespace std;
 9 
10 const int MAXN = 100100;
11 const LL MOD = 100000007;
12 
13 int N;
14 int C[MAXN];
15 int num[MAXN];
16 int low[MAXN];
17 int high[MAXN];
18 
19 int lowbit( int x )
20 {
21     return x & ( -x );
22 }
23 
24 void Update( int x, int val )
25 {
26     while ( x <= N )
27     {
28         C[x] += val;
29         x += lowbit(x);
30     }
31     return;
32 }
33 
34 int Query( int x )
35 {
36     int res = 0;
37     while ( x > 0 )
38     {
39         res += C[x];
40         x -= lowbit(x);
41     }
42     return res;
43 }
44 
45 int main()
46 {
47     int T, cas = 0;
48     scanf( "%d", &T );
49     while ( T-- )
50     {
51         scanf( "%d", &N );
52         for ( int i = 1; i <= N; ++i )
53             scanf( "%d", &num[i] );
54 
55         memset( C, 0, sizeof(C) );
56 
57         for ( int i = 1; i <= N; ++i )
58         {
59             low[i] = Query( num[i] - 1 );
60             Update( num[i], 1 );
61         }
62 
63         memset( C, 0, sizeof(C) );
64         for ( int i = N; i > 0; --i )
65         {
66             //printf("i=%d %d %d
", i, Query( N ), Query( num[i] ) );
67             high[i] = Query( N ) - Query( num[i] );
68             Update( num[i], 1 );
69         }
70 
71         LL ans = 0;
72         for ( int i = 1; i <= N; ++i )
73         {
74             //printf( "h=%d l=%d
", high[i], low[i] );
75             ans += (LL)high[i] * ( high[i] - 1 ) / 2 - (LL)low[i] * high[i];
76             ans = ( ans + MOD ) % MOD;
77         }
78 
79         printf( "Case #%d: %I64d
", ++cas, ans % MOD );
80     }
81     return 0;
82 }