给你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 ;
}