hdu - 3015 Disharmony Trees（树状数组 + 离散化）

题目连接

题意：给你n棵树的坐标和高度，分别按两个值升序排序后，得到每棵树的排名，分别为$u_i$和$v_i$，求${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}abs(u_i-u_j)\ast min(v_i,v_j)$。

题解：因为是区间求和，想到了树状数组。若想要一次性求一个区间，那么在这个区间中$min(v_i,v_j)$要是一个确定的值，所以在最终求的时候要按照高度降序排序，每次求$1-i$区间的值。我们先分别按照坐标和高度排序，得到各棵树的排名，这个过程也相当于一个不去重的离散化的处理。然后在按高度降序排序的结构体数组里遍历，用树状数组求之前有多少棵坐标比当前树小的树，和之前坐标比当前树小的树的坐标排名和，可以推出相应的公式（因为$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; }