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] );

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #define LL long long int

 using namespace std;

 const int MAXN = ;

 const LL MOD = ;

 int N;

 int C[MAXN];

 int num[MAXN];

 int low[MAXN];

 int high[MAXN];

 int lowbit( int x )

 {

     return x & ( -x );

 }

 void Update( int x, int val )

 {

     while ( x <= N )

     {

         C[x] += val;

         x += lowbit(x);

     }

     return;

 }

 int Query( int x )

 {

     int res = ;

     while ( x >  )

     {

         res += C[x];

         x -= lowbit(x);

     }

     return res;

 }

 int main()

 {

     int T, cas = ;

     scanf( "%d", &T );

     while ( T-- )

     {

         scanf( "%d", &N );

         for ( int i = ; i <= N; ++i )

             scanf( "%d", &num[i] );

         memset( C, , sizeof(C) );

         for ( int i = ; i <= N; ++i )

         {

             low[i] = Query( num[i] -  );

             Update( num[i],  );

         }

         memset( C, , sizeof(C) );

         for ( int i = N; i > ; --i )

         {

             //printf("i=%d %d %d\n", i, Query( N ), Query( num[i] ) );

             high[i] = Query( N ) - Query( num[i] );

             Update( num[i],  );

         }

         LL ans = ;

         for ( int i = ; i <= N; ++i )

         {

             //printf( "h=%d l=%d\n", high[i], low[i] );

             ans += (LL)high[i] * ( high[i] -  ) /  - (LL)low[i] * high[i];

             ans = ( ans + MOD ) % MOD;

         }

         printf( "Case #%d: %I64d\n", ++cas, ans % MOD );

     }

     return ;

 }

巴特西

HDU 4000 Fruit Ninja 树状数组 + 计数

最新文章

热门文章