A - Jam's problem again
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
1410 4 710 6 68 2 57 3 10
Sample Output
1100
题解
三维偏序
初始按\(x\)为意义关键字,\(y\)为第二关键字,\(z\)为第三关键字排序,一定不能省只按\(x\)排序,因为要处理相同的点
分别处理子问题,然后以\(y\)坐标为关键字, 将左右两端归并排序(这样递归左右内部\(y\)有序)
并用树状数组维护前缀的\(z\)的信息(当前左边的\(x\)一定比右边小,并且\(y\)也有序)
归并到左边的点就插入\(z\), 右边的点询问\(z\)
对于相同的点,我们初始发现排完序后,相同的点中序号较前的点不会统计到后面相同的点,只有最后的那个点才统计完全
所以可以在一开始先将相同的点加上\(p, p-1, ..., 1, 0\)就好了
#include#include #include #include #include #include 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;}/* */