首页 > 代码库 > HDU 5147 Sequence II ( 树状数组 )

HDU 5147 Sequence II ( 树状数组 )

2024-08-09 02:25:20   217人阅读

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 <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <iostream>using namespace std;const int N = 50010;const double PI = acos(-1.0);const double eps = 1e-6;typedef long long LL;typedef pair<double,double> 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();    }}
View Code

 

HDU 5147 Sequence II ( 树状数组 )


联系
我们