程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5147 Sequence II

HDU 5147 Sequence II

編輯：C++入門知識

HDU 5147 Sequence II

題意：

n（5*10^5）個不同的數字組成的序列a 尋找滿足如下約束條件的數字組數： i1思路：

明顯考察的是nlogn的算法我們發現其實ai1和ai2可以放在一起考慮同理ai3和ai4 這兩組並沒有相互影響

我們來看答案是怎麼構成的假設枚舉i3的位置那麼我們希望知道“i3後面有幾個數大於ai3” 這個可以通過樹狀數組處理

同理假設我們知道i2也希望知道“i2前面有幾個數小於ai2” 這個也可以樹狀數組

那麼再利用i3>i2 則答案就可以表示為 sum( num(>ai3) * sum( num(

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 50000
#define lowbit(x) (x&(-x))

inline void scand(int &ret) {
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9')
        ;
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
}

int t, n;
int c[N + 10], d[N + 10], g[N + 10];
LL ans;

void add(int f[], int x, int key) {
    while (x <= N) {
        f[x] += key;
        x += lowbit(x);
    }
}

int sum(int f[], int x) {
    int res = 0;
    while (x) {
        res += f[x];
        x -= lowbit(x);
    }
    return res;
}

struct node {
    int val, id;
} nd[N + 10];

bool cmp1(node fa, node fb) {
    return fa.val < fb.val;
}

bool cmp2(node fa, node fb) {
    return fa.id < fb.id;
}

int main() {
    scand(t);
    while (t--) {
        scand(n);
        for (int i = 1; i <= n; i++) {
            scand(nd[i].val);
            nd[i].id = i;
        }
        sort(nd + 1, nd + n + 1, cmp1);
        memset(c, 0, sizeof (c));
        memset(d, 0, sizeof (d));
        for (int i = 1; i <= n; i++) {
            int tmp = sum(c, nd[i].id);
            add(c, nd[i].id, 1);
            add(d, nd[i].id, tmp);
            g[nd[i].id] = sum(c, nd[i].id - 1);
        }
        sort(nd + 1, nd + n + 1, cmp2);
        ans = 0;
        for (int i = 3; i <= n; i++) {
            int tmp = nd[i].val - 1;
            tmp = n - i - (tmp - g[i]);
            ans += (LL) (tmp) * sum(d, i - 1);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}