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