A - Jam's problem again HDU - 5618

Problem Description

Jam like to solve the problem which on the 3D-axis,given N(1≤N≤100000) points (x,y,z)(1≤x,y,z≤100000)

If two point such as$ (x_i,y_i,z_i)$ and \((x_j,y_j,z_j)\) \(x_i≥x_j,y_i≥_j,z_i≥z_j?\), the bigger one level add 1

Ask for the each level of the point.

Input

The first line is T(1≤T≤15) means T Case

For each case

The first line is N means the number of Point and next there are N line, each line has (x,y,z)

Output

Output with N line,each line has one number means the lever of point

Sample Input

1 4 10 4 7 10 6 6 8 2 5 7 3 10

Sample Output

1 1 0 0

題解

三維偏序

初始按\(x\)為意義關(guān)鍵字,\(y\)為第二關(guān)鍵字,\(z\)為第三關(guān)鍵字排序,一定不能省只按\(x\)排序,因為要處理相同的點

分別處理子問題,然后以\(y\)坐標(biāo)為關(guān)鍵字, 將左右兩端歸并排序(這樣遞歸左右內(nèi)部\(y\)有序)

并用樹狀數(shù)組維護(hù)前綴的\(z\)的信息(當(dāng)前左邊的\(x\)一定比右邊小,并且\(y\)也有序)

歸并到左邊的點就插入\(z\), 右邊的點詢問\(z\)

對于相同的點,我們初始發(fā)現(xiàn)排完序后,相同的點中序號較前的點不會統(tǒng)計到后面相同的點,只有最后的那個點才統(tǒng)計完全

所以可以在一開始先將相同的點加上\(p, p-1, ..., 1, 0\)就好了

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <algorithm>using namespace std;typedef long long LL; const int MAXN = 1e5 + 10;inline LL in() {LL x = 0, flag = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();return x * flag; }int T;int n;struct Fenwick {int val[MAXN];void clear() { memset(val, 0, sizeof val); }void update(int x, int v){for (int i = x; i <= 100000; i += i & (-i)) val[i] += v;}int query(int x){int ret = 0;for (int i = x; i > 0; i &= (i - 1)) ret += val[i];return ret;} } FT;int an[MAXN]; struct Node {int x, y, z, id;bool operator < (const Node & b) const{return x == b.x ? (y == b.y ? z < b.z : y < b.y) : x < b.x; } } a[MAXN], b[MAXN];void merge(int l, int mid, int r) {int i = l, j = mid + 1, k = i;while (k <= r){if (j > r || (i <= mid && a[i].y <= a[j].y)){FT.update(a[i].z, 1);b[k ++] = a[i];++ i;}else{an[a[j].id] += FT.query(a[j].z);b[k ++] = a[j];++ j;}}for (int i = l; i <= mid; i ++) FT.update(a[i].z, -1);for (int i = l; i <= r; i ++) a[i] = b[i]; } void solve(int l, int r) {if (l >= r) return;int mid = (l + r) >> 1;solve(l, mid);solve(mid + 1, r);merge(l, mid, r); }int main() {T = in();while (T --){memset(a, 0, sizeof a);memset(an, 0, sizeof an);n = in(); for (int i = 1; i <= n; i ++) a[i] = (Node) { in(), in(), in(), i };sort(a + 1, a + n + 1);for (int i = n - 1; i >= 1; i --){if (a[i].x == a[i + 1].x && a[i].y == a[i + 1].y && a[i].z == a[i + 1].z) an[a[i].id] += an[a[i + 1].id] + 1;}solve(1, n);for (int i = 1; i <= n; i ++) printf("%d\n", an[i]);}return 0; }/**/

轉(zhuǎn)載于:https://www.cnblogs.com/ikihsiguoyr/p/10569484.html

總結(jié)

以上是生活随笔為你收集整理的CDQ分治 Jam's problem again [HDU - 5618]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。