题意：
三维坐标，对于1个点，找出有多少个点，3个坐标都比该点小！
Sample Input
1
4
10 4 7
10 6 6
8 2 5
7 3 10
Sample Output
1
1
0
0
首先是方法一：
很常见的三维偏序做法，先将所有输入点按要求排序，然后向数据结构插入的时候就可以确定先插入的x值一定比后插入的x小，这样就将三维转化为2维。
2维的话就用树状数组套线段树。根据y建树状数组，根据z建线段树，每一个树状数组的点都对应着一个线段树。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<queue> #include<iostream> using namespace std; typedef long long LL; const int maxn = 2e5 + 10; const int low(int x){ return x&-x; } int T, n; struct point { int x, y, z, id, cnt; void read(){ scanf("%d%d%d", &x, &y, &z); cnt = 0; } bool operator<(const point& a) const { if (x == a.x&&y == a.y) return z < a.z; if (x == a.x) return y < a.y; return x < a.x; } }a[maxn]; bool cmp(const point&a, const point&b) { return a.id < b.id; } struct Tree { //将y坐标用树状数组维护，z坐标用线段树维护。然后在树状数组中的每一个点都对应着一个线段树。 //查询小于(y,z)的所有点只需要在1-y这个树状数组中的所有点对应的线段树中都查询<z的个数 int tot, first[maxn], f[maxn * 50], L[maxn * 50], R[maxn * 50], lit, lim; //lim代表最大的z，lit代表最大的y void clear(int x, int y) { lit = x; lim = y; for (int i = 1; i <= lit; i++) { first[i] = i; f[i] = R[i] = L[i] = 0; } tot = lit + 1; } int newnode() { f[tot] = R[tot] = L[tot] = 0; return tot++; } void ins(int x, int l, int r, int v) { f[x] += 1; if (l == r) return; int mid = l + r >> 1; if (v <= mid) { if (!L[x]) L[x] = newnode(); ins(L[x], l, mid, v); } else { if (!R[x]) R[x] = newnode(); ins(R[x], mid + 1, r, v); } } void insert(int x, int y) { for (int i = x; i <= lit; i += low(i)) ins(first[i], 1, lim, y); } int find(int x, int l, int r, int v)//对于第x棵线段树，查询有多少权值<v的 { if (r <= v) return f[x]; int mid = l + r >> 1, ans = 0; if (v <= mid) ans = find(L[x], l, mid, v); else ans = f[L[x]] + find(R[x], mid + 1, r, v); return ans; } int get(int x, int y)//通过树状数组统计1-x这个范围内的线段树中<y的点的总数 { int res = 0; for (int i = x; i; i -= low(i)) res += find(first[i], 1, lim, y); return res; } }tree; int main() { scanf("%d", &T); while (scanf("%d", &n) != EOF, T--) { for (int i = 0; i < n; i++) a[i].read(), a[i].id = i; sort(a, a + n);//将输入的点按照题意排序 // for(int i=0;i<n;i++){ // cout<<a[i].x<<endl; // } for (int i = n - 2; i >= 0; i--) if (a[i].x == a[i + 1].x&&a[i].y == a[i + 1].y&&a[i].z == a[i + 1].z) a[i].cnt = a[i + 1].cnt + 1; int ans1 = 0, ans2 = 0; for (int i = 0; i < n; i++) ans1 = max(ans1, a[i].y), ans2 = max(ans2, a[i].z); tree.clear(ans1, ans2); for (int i = 0; i < n; i++)//将三维转为2维，以为已经排好序，所以先插入的点的x坐标<后插入点的x坐标，接下来只需要比较y和z { a[i].cnt += tree.get(a[i].y, a[i].z); tree.insert(a[i].y, a[i].z); } sort(a, a + n, cmp); for (int i = 0; i < n; i++) printf("%d ", a[i].cnt); } return 0; }
方法二：cdq分治+树状数组（从别人那学到的）
首先先拿二维的点解释一下cdq分治，对于x坐标有序的点，点i可以对点j产生贡献，当且仅当yi<=yj。
我们考虑先把x坐标排序，那么对于某个区间[l,r]，其x坐标必然有序。
我们再对[l,mid]和[mid + 1,r]进行y坐标的重新排序。
然后考虑计算[l,mid]之间所有点对于[mid + 1,r]的区间的贡献。
我们考虑是先递归下去，然后排序比较对还是先排序计算贡献，然后递归下去比较对。
嗯……显然，先递归下去之后，会产生两个y有序的区间[l,mid],[mid + 1,r]。
并且我们知道对于左区间的所有点的x值是小于右区间的。
然后我们就可以直接计算左区间对于右区间的贡献。
考虑合并两个区间，显然归并排序一下就可以做到O(n)。
然后我们就可以继续回溯上去。
如果先计算贡献，那么需要把左右区间对y进行排序，然后计算完左边对右边的贡献之后，再按照x坐标排回去。<常数大了很多2333>
三维的话把左区间的所有z坐标都插入到树状数组里。然后对于右边的区间每次询问z坐标即可。
#include <cstdio> #include <cstring> #include <algorithm> #define Rep(i,n) for(int i = 1;i <= n;i ++) #define u t[x] using namespace std; const int N = 100005; int n,ans[N],t[N]; struct Point {int x,y,z,id,sum;}p[N]; bool cx(Point a,Point b){return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x;} bool cy(Point a,Point b) { if(a.y != b.y)return a.y < b.y; return a.x == b.x ? a.z < b.z : a.x < b.x; } void add(int x,int val){for(;x <= 100000;x += x & -x)u += val;} int Qry(int x){int s = 0;for(;x;x -= x & -x)s += u;return s;} void solve(int l,int r) { if(l == r)return; int mid = l + r >> 1; solve(l,mid),solve(mid + 1,r); sort(p + l,p + mid + 1,cy); sort(p + mid + 1,p + r + 1,cy); int j = l; for(int i = mid + 1;i <= r;i ++) { for(;j <= mid && p[j].y <= p[i].y;j ++) add(p[j].z,1); p[i].sum += Qry(p[i].z); } for(j --;j >= l;j --)add(p[j].z,-1); } int main () { int _;scanf("%d",&_); while(_--) { scanf("%d",&n); Rep(i,n)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),p[i].id = i,p[i].sum = 0; sort(p + 1,p + 1 + n,cx); solve(1,n); for(int i = 1;i <= n;) { int j = i + 1; int tmp = p[i].sum; for(;j <= n && p[i].x == p[j].x && p[i].y == p[j].y && p[i].z == p[j].z ;++ j)tmp = max(tmp,p[j].sum); for(int k = i;k < j;k ++)ans[p[k].id] = tmp; i = j; } Rep(i,n) printf("%d ",ans[i]); } return 0; }