题意：有n朵花，每朵花有3个属性，若一朵花比另一朵花美丽，当且仅当这朵花的三个属性均不小于另一朵花。一朵花的美丽度等于这朵花比其他多少朵花要美丽。

求美丽度分别为0~n-1的花各有多少朵。

Sol:事实上就是三维偏序。一句话：一维排序，二维CDQ分治，三维树状数组。

How do they work?

首先根据x坐标排序，接着对y,z坐标CDQ分治。

定义Solve(l,r)为处理l~r一段的美丽度。

令mid=(l+r)/2,我们首先进行Solve(l,mid),Solve(mid+1,r).假设我们处理完之后两端的y值均从大到小有序。

我们处理前一段对后一段的影响：按照线性合并的思想，若对后一段进行合并时，则利用树状数组更新后一段的答案。否则更新树状数组。

这样我们能保证Solve(l,r)能正确的更新答案，且使得y一维从小到大有序。另外我们使用树状数组，是为了维护z这一维。

时间复杂度O(nlog^2n).

为了处理相同的影响，我事实上将x和y相同的部分当做一段整体处理。

Code:

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        inline int getc() { static const int L = 1 << 15; static char buf[L], *S = buf, *T = buf; if (S == T) { T = (S = buf) + fread(buf, 1, L, stdin); if (S == T) return EOF; } return *S++; } inline int getint() { int c; while(!isdigit(c = getc())); int tmp = c - '0'; while(isdigit(c = getc())) tmp = (tmp << 1) + (tmp << 3) + c - '0'; return tmp; } char buf[600010], *o = buf; #define _putchar(c) *o++ = c inline void output(int x) { static int stack[10]; if (!x) *o++ = 48; else { int top = 0; for(; x; stack[++top] = x % 10, x /= 10); for(int i = top; i >= 1; --i) *o++ = 48 + stack[i]; } } #define N 100010 struct Case { int x, y, z; void read() { x = getint(), y = getint(), z = getint(); } bool operator < (const Case &B) const { return x < B.x || (x == B.x && y < B.y); } }S[N], tmp[N]; int left[N], right[N], cnt, seq[N], _seq[N]; #define K 200010 int lim; int A[K], now[K], tclock; int ask(int x, int tclock) { int res = 0; for(; x; x -= x & -x) { if (now[x] != tclock) { A[x] = 0; now[x] = tclock; } res += A[x]; } return res; } void modify(int x, int add, int tclock) { for(; x <= lim; x += x & -x) { if (now[x] != tclock) { A[x] = 0; now[x] = tclock; } A[x] += add; } } int ans[N]; void Divide(int l, int r) { register int i, j, k, p; if (l == r) { ++tclock; for(i = left[seq[l]]; i <= right[seq[l]]; ++i) modify(S[i].z, 1, tclock); for(i = left[seq[l]]; i <= right[seq[l]]; ++i) ans[i] += ask(S[i].z, tclock); return; } int mid = (l + r) >> 1; Divide(l, mid); Divide(mid + 1, r); ++tclock; i = l, j = mid + 1, k = l; while(i <= mid && j <= r) { if (S[left[seq[i]]].y <= S[left[seq[j]]].y) { _seq[k++] = seq[i]; for(p = left[seq[i]]; p <= right[seq[i]]; ++p) modify(S[p].z, 1, tclock); ++i; } else { _seq[k++] = seq[j]; for(p = left[seq[j]]; p <= right[seq[j]]; ++p) ans[p] += ask(S[p].z, tclock); ++j; } } while(i <= mid) _seq[k++] = seq[i++]; while(j <= r) { for(p = left[seq[j]]; p <= right[seq[j]]; ++p) ans[p] += ask(S[p].z, tclock); _seq[k++] = seq[j++]; } memcpy(seq + l, _seq + l, sizeof(int) * (r - l + 1)); } int nums[N]; int main() { //freopen("tt.in", "r", stdin); int n = getint(); lim = getint(); register int i, j; for(i = 1; i <= n; ++i) S[i].read(); std::sort(S + 1, S + n + 1); for(i = 1; i <= n; ) { for(j = i; S[j].x == S[j + 1].x && S[j].y == S[j + 1].y; ++j); left[++cnt] = i, right[cnt] = j; i = j + 1; } for(i = 1; i <= cnt; ++i) seq[i] = i; Divide(1, cnt); for(i = 1; i <= n; ++i) ++nums[ans[i]]; for(i = 1; i <= n; ++i) { output(nums[i]); _putchar('\n'); } fwrite(buf, 1, o - buf, stdout); return 0; }