Sequence II

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 30    Accepted Submission(s): 16

Problem Description

Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.

Please calculate how many quad (a,b,c,d) satisfy:

1. 

1≤a<b<c<d≤n

2. Aa<Ab

3. Ac<Ad

 

 

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case begins with a line contains an integer n.

The next line follows n integers 

A1,A2,…,An.

[Technical Specification]

1 <= T <= 100

1 <= n <= 50000

1 <= Ai <= n

 

 

Output

For each case output one line contains a integer,the number of quad.

 

 

Sample Input

1

5

1 3 2 4 5

 

 

Sample Output

4

 

 

BC#23的一条算是简单题。

一开始看错题 ， 以为是  （ a < b < c < d ）Aa < Ac , Ab < Ad 

一直想不出来。

看清题之后 ， 变简单了很多 。

枚举（1~n）作为c位置。

求前面 a < b < c 符合 Aa < Ab 的个数再乘上前面大于Ac的数的个数（即未插入BIT数）。 

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N = 50010;const double PI = acos(-1.0);const double eps = 1e-6;typedef long long LL;typedef pair
           
             pii;#define X first#define Y secondint n , A[N] ;LL cnt[N] , c[N];void init() { memset( c , 0 ,sizeof c ); }int lowbit( int x ) { return x&-x; }void update( int pos , int key ) { while( pos < n + 10 ) { c[pos] += key ;pos += lowbit(pos);}}LL query( int pos ) { LL res = 0 ; while( pos > 0 ) {res += c[pos]; pos -= lowbit(pos); } return res ; }void Run() { init(); scanf("%d",&n); for( int i = 1 ; i <=n ; ++i ){ scanf("%d",&A[i]); } LL res = 0 ; for( int i = 1 ; i <= n ; ++i ) { LL low = query( A[i] - 1 ) , up = i - 1 - low; cnt[i] = cnt[i-1] + low ; update( A[i] , 1 ) ; res += cnt[i-1] * ( n - A[i] - up ) ; } printf("%I64d\n",res);}int main() {// freopen("in.txt","r",stdin); int _ , cas = 1 ; scanf("%d",&_); while( _-- ) { Run(); }}