程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Hdu 5147 Sequence II(樹狀數字 or 線段樹 + 輸入外掛 前綴和+後綴和)

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

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved