hdu - 3015 Disharmony Trees（樹狀陣列 + 離散化）

題目連接

題意：給你n棵樹的坐標和高度，分別按兩個值升序排序后，得到每棵樹的排名，分別為 u i u_i ui?和 v i v_i vi?，求 ∑ i = 1 n ∑ j = i + 1 n a b s ( u i ? u j ) ? m i n ( v i , v j ) \sum_{i = 1}^n \sum_{j = i + 1}^n abs(u_i - u_j) * min(v_i, v_j) ∑i=1n?∑j=i+1n?abs(ui??uj?)?min(vi?,vj?)，

題解：因為是區間求和，想到了樹狀陣列，若想要一次性求一個區間，那么在這個區間中 m i n ( v i , v j ) min(v_i, v_j) min(vi?,vj?)要是一個確定的值，所以在最終求的時候要按照高度降序排序，每次求 1 ? i 1-i 1?i區間的值，我們先分別按照坐標和高度排序，得到各棵樹的排名，這個程序也相當于一個不去重的離散化的處理，然后在按高度降序排序的結構體陣列里遍歷，用樹狀陣列求之前有多少棵坐標比當前樹小的樹，和之前坐標比當前樹小的樹的坐標排名和，可以推出相應的公式（因為 a b s abs abs的存在，所以要分開來計算），

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int maxn = 1e5 + 7;

typedef long long ll;

ll num[maxn], id[maxn], sum[maxn];
int n, cnt, tot;

struct Node{
    ll x, h;
    int id, hid;
}node[maxn];

bool cmpX(Node a, Node b) {
    return a.x < b.x;
}

bool cmpH(Node a, Node b) {
    return a.h > b.h;
}

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

void add(int i, ll c[], ll v) {
    while (i < tot) {
        c[i] += v;
        i += lowbit(i);
    }
}

ll query(int i, ll c[]) {
    ll res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

void solve() {
    for (int i = 1; i <= n; ++i) cin >> node[i].x >> node[i].h, num[i] = sum[i] = 0;
    //sum記錄和，num記錄數量
    ll ans = 0;
    tot = 1;
    cnt = 1;
    //按坐標排序，排名
    sort(node + 1, node + 1 + n, cmpX);
    for (int i = 1; i <= n; ++i) {
        node[i].id = tot++;
        while (i < n && node[i + 1].x == node[i].x) node[i + 1].id = node[i].id, tot++, i++;
    }
    //按高度排序，排名
    sort(node + 1, node + 1 + n, cmpH);
    for (int i = n; i >= 1; --i) {
        node[i].hid = cnt++;
        while (i > 1 && node[i - 1].h == node[i].h) node[i - 1].hid = node[i].hid, cnt++, i--;
    }
    //pre為坐標排名前綴和
    ll pre = node[1].id;
    add(node[1].id, num, 1);
    add(node[1].id, sum, node[1].id);
    for (int i = 2; i <= n; ++i) {
        ll s = query(node[i].id - 1, num);
        ll ss = query(node[i].id - 1, sum);
        ans += (pre - ss - node[i].id * (i - s - 1) + s * node[i].id - ss) * node[i].hid;
        pre += node[i].id;
        add(node[i].id, num, 1);
        add(node[i].id, sum, node[i].id);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    while (cin >> n) solve();
    return 0;
}