题意：给n个点，求每一个点的满足 x y z 都小于等于它的其他点的个数。
析：三维的，第一维直接排序就好按下标来，第二维按值来，第三维用数状数组维即可。
代码如下：
cdq 分治：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#include <numeric>
#define debug() puts("++++")
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
#define sz size()
#define pu push_up
#define pd push_down
#define cl clear()
#define all 1,n,1
#define FOR(i,x,n) for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, int> P;
const int INF = 0x3f3f3f3f;
const LL LNF = 1e17;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 5;
const int mod = 1000000007;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
struct Node{
int x, y, z, id, num;
bool operator < (const Node &p) const{
return x != p.x ? x < p.x : (y != p.y ? y < p.y : z < p.z);
}
bool operator == (const Node &p) const{
return x == p.x && y == p.y && z == p.z;
}
};
Node a[maxn];
int ans[maxn];
int sum[maxn];
inline int lowbit(int x){ return -x&x; }
void add(int x, int c){
while(x < maxn){
sum[x] += c;
x += lowbit(x);
}
}
int query(int x){
int ans = 0;
while(x){
ans += sum[x];
x -= lowbit(x);
}
return ans;
}
inline bool cmp(const Node &lhs, const Node &rhs){
return lhs.y < rhs.y || lhs.y == rhs.y && lhs.z < rhs.z;
}
void dfs(int l, int r){
if(l == r){ ans[a[l].id] += a[l].num-1; return ; }
int m = l + r >> 1;
dfs(l, m); dfs(m+1, r);
sort(a+l, a+m+1, cmp);
sort(a+m+1, a+r+1, cmp);
int j = l;
for(int i = m+1; i <= r; ++i){
while(j <= m && a[j].y <= a[i].y) add(a[j].z, a[j].num), ++j;
ans[a[i].id] += query(a[i].z);
}
for(int i = l; i < j; ++i) add(a[i].z, -a[i].num);
}
int id[maxn];
int main(){
int T; cin >> T;
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
a[i].id = i;
}
sort(a, a + n); ms(ans, 0);
int cnt = 0;
for(int i = 0; i < n; ++i, ++cnt){
a[cnt] = a[i]; a[cnt].num = 1;
id[a[i].id] = cnt;
for(int j = i+1; j < n && a[i] == a[j]; i = j, id[a[j].id] = cnt, ++j)
++a[cnt].num;
a[cnt].id = cnt;
}
dfs(0, cnt-1);
for(int i = 0; i < n; ++i) printf("%d
", ans[id[i]]);
}
return 0;
}
树套树：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#include <numeric>
#define debug() puts("++++")
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
#define sz size()
#define pu push_up
#define pd push_down
#define cl clear()
#define all 1,n,1
#define FOR(i,x,n) for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, int> P;
const int INF = 0x3f3f3f3f;
const LL LNF = 1e17;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 5;
const int mod = 1000000007;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
struct Node{
Node *ch[2];
int r;
int v, num;
int s;
Node(int v, int n) : v(v), num(n) { ch[0] = ch[1] = 0; r = rand(); s = num; }
bool operator < (const Node &rhs) const{
return r < rhs.r;
}
int cmp(int x) const{
if(x == v) return -1;
return x < v ? 0 : 1;
}
void maintain(){
s = num;
if(ch[0]) s += ch[0]->s;
if(ch[1]) s += ch[1]->s;
}
};
void rotate(Node* &o, int d){
Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
}
void insert(Node* &o, int x, int num){
if(o == 0) o = new Node(x, num);
else {
int d = (x < o->v ? 0 : 1);
insert(o->ch[d], x, num);
if(o->ch[d]->r > o->r) rotate(o, d^1);
}
o->maintain();
}
void remove(Node* &o){
if(o == 0) return ;
remove(o->ch[0]);
remove(o->ch[1]);
delete o; o = 0;
}
int getrank(Node *o, int num){
if(o == 0) return 0;
if(num == o->v){
if(o->ch[0]) return o->ch[0]->s + o->num + getrank(o->ch[1], num);
return o->num + getrank(o->ch[1], num);
}
if(num < o->v) return getrank(o->ch[0], num);
if(o->ch[0]) return o->ch[0]->s + o->num + getrank(o->ch[1], num);
return o->num + getrank(o->ch[1], num);
}
Node* root[maxn];
struct node{
int x, y, z, id, num;
bool operator < (const node &p) const{
return x != p.x ? x < p.x : (y != p.y ? y < p.y : z < p.z);
}
bool operator == (const node &p) const{
return x == p.x && y == p.y && z == p.z;
}
};
node a[maxn];
int id[maxn], ans[maxn];
inline int lowbit(int x){ return -x&x; }
void add(int x, int i){
while(x < maxn){
insert(root[x], a[i].z, a[i].num);
x += lowbit(x);
}
}
int query(int x, int c){
int ans = 0;
while(x){
ans += getrank(root[x], c);
x -= lowbit(x);
}
return ans;
}
int main(){
int T; cin >> T;
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
a[i].id = i;
}
sort(a, a + n);
int cnt = 0;
for(int i = 0; i < n; ++i, ++cnt){
a[cnt] = a[i]; a[cnt].num = 1;
id[a[i].id] = cnt;
for(int j = i+1; j < n && a[i] == a[j]; ++j){
i = j; id[a[j].id] = cnt;
++a[cnt].num;
}
ans[cnt] = query(a[cnt].y, a[cnt].z) + a[cnt].num - 1;
add(a[cnt].y, cnt);
}
for(int i = 0; i < maxn; ++i) remove(root[i]);
for(int i = 0; i < n; ++i) printf("%d
", ans[id[i]]);
}
return 0;
}