Hdu 5147 Sequence II（樹狀數字 or 線段樹 + 輸入外掛 前綴和+後綴和）

Hdu 5147 Sequence II（樹狀數字 or 線段樹 + 輸入外掛 前綴和+後綴和）

題意：

給定1~n的一個排列 用A[]數組保存，問有多少下標(a,b,c,d)四元組滿足：
a

解析：

題目中n的范圍是50000，O（n^2) 復雜度肯定超時。那麼這題明顯考察的是log2(n)的算法，對於這題可以用線段樹或者樹狀數組，同時要用到輸入外掛，不然會超時。

思路（參考別人做法）

枚舉c的位置，那麼每一次枚舉中的方法數為 1~c-1 中(a,b)的個數 乘以 c~n中（c,d)的個數。累加起來即為答案。

1~c-1中(a,b)的個數相當於枚舉b的位置，然後計算出b前面有多少數比A[b]小，該值要保存下來，下一次枚舉c的時候，該值再加上c-1前面有多少比a[c-1]小的數即為當前情況下1~c-1中(a,b)的個數，也就是b=c-1的時候，因為枚舉b之前的情況已經算過了。

因為當算c時只是算出 比c小的方法數，這個只是滿足比c小的二元組的個數。而c前面的二元組也要計算在內，所以要加上c前面的比c小的個數。

用樹狀數組來做。本題n范圍50000，而且每個數都不相同很關鍵。所以我們就開辟n個位置，一開始每個位置都是0，其實每個位置不是0就是1，因為每個數只有一個。

比如 1 3 2 4 5
一開始 c數組 0 0 0 0 0
先統計，再輸入，因為計算a[i]前面有多少比它小的數，不包括它自己，而樹狀數組計算和的時候，要包括它自己。
i=1，樹狀數組求和前綴和 pre[1]=0 ,
此時0 0 0 0 0， 輸入1，變為 1 0 0 0 0
i=2，a[2]=3，要看 3前面有多少個數，也就是看c數組的3個位置前面有多少個1，1代表已經輸入，
發現1 0 0 0 0前三個數只有一個1，也就是pre[2]=1 (輸入的第二個數之前只有1個比它小的），輸入3以後，c數組變為 1 0 1 0 0
i=3, a[3]= 2, 要看2前面有多少個數，也就是看c數組前2個位置前面有多少個1，發現10100前兩個數中只有一個1，也就是pre[3]=1

前綴和可以算出來，那麼後綴和 = num2[i] = n-i-a[i]+num[i]+1;

AC代碼

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 10;
int n;
ll C[N], a[N];
inline void read(ll &x) {
    int flag = 0;
    x = 0;
    char c = getchar();
    if(c == '-')
        flag = 1;
    while(c < '0' || c > '9') {
        if(c == '-')
            flag = 1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    if(flag) x = -x;
}
inline int lowbit(int x) {
    return x & (-x);
}
int query(int x) {
    int ret = 0;
    while(x > 0) {
        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}
void add(int x, int d) {
    while(x <= n) {
        C[x] += d;
        x += lowbit(x);
    }
}
int num[N] , num2[N];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        ll ans = 0, pre = 0;
        scanf("%d", &n);
        memset(C, 0, sizeof(C));
        for(int i = 1; i <= n; i++) {
            read(a[i]);
            num[i] = query(a[i]); //計算a[i]之前比a[i]小的數字
            num2[i] = n-i-a[i]+num[i]+1; //計算a[i]之後比a[i]大的數字
            add(a[i], 1);
            ans += pre * num2[i];
            pre += num[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}