HIT 2275 Number sequence

思路: 樹狀數組

分析:

1 題目要求的是總共的搭配方式，滿足Ai < Aj > Ak.並且i j k不同

2 我們開兩個樹狀數組，第一個在輸入的時候就去更新。然後我們在去枚舉Aj 同時維護第二個樹狀數組，對於AI來說就是在第二個樹狀數組裡面求和

然後在通過第一個樹狀數組就可以求出Ak的個數，把結果相乘即可

代碼:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

int n , num[MAXN];
int treeNumOne[MAXN];
int treeNumTwo[MAXN];

int lowbit(int x){
    return x&(-x);
}

int getSum(int *arr , int x){
    int sum = 0;
    while(x){
        sum += arr[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int *arr , int x , int val){
    while(x < MAXN){
         arr[x]  += val; 
         x += lowbit(x);
    }
}

long long getAns(){
    if(n < 3)
        return 0;
    long long ans = 0;
    add(treeNumTwo , num[1] , 1);
    for(int i = 2 ; i < n ; i++){
        int x = getSum(treeNumTwo , num[i]-1); 
        int y = getSum(treeNumOne , num[i]-1); 
        add(treeNumTwo , num[i] , 1);
        ans += (x)*(y-x); 
    }
    return ans;
}

int main(){
    while(scanf("%d" , &n) != EOF){
         memset(treeNumOne , 0 , sizeof(treeNumOne));
         memset(treeNumTwo , 0 , sizeof(treeNumTwo)); 
         for(int i = 1 ; i <= n ; i++){
             scanf("%d" , &num[i]);  
             num[i]++;
             add(treeNumOne , num[i] , 1);
         }
         printf("%lld\n" , getAns());
    }
    return 0;
}