三维偏序：https://www.luogu.org/problemnew/show/P3810
cdq分治即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define LL long long 7 #define RI register int 8 #define lowbit(x) (x&(-x)) 9 using namespace std; 10 const int INF = 0x7ffffff ; 11 const int N = 100000 + 10 ; 12 const int K = 200000 + 10 ; 13 14 inline int read() { 15 int k = 0 , f = 1 ; char c = getchar() ; 16 for( ; !isdigit(c) ; c = getchar()) 17 if(c == '-') f = -1 ; 18 for( ; isdigit(c) ; c = getchar()) 19 k = k*10 + c-'0' ; 20 return k*f ; 21 } 22 struct point { 23 int a, b, c, bl ; 24 }p[N], tmp[N] ; 25 int n, k ; int f[N], tr[K], ans[N], num[N] ; 26 27 inline void add(int x) { 28 while(x <= K) { 29 tr[x] ++ ; 30 x += lowbit(x) ; 31 } 32 } 33 inline void del(int x) { 34 while(x <= K) { 35 tr[x] -- ; 36 x += lowbit(x) ; 37 } 38 } 39 inline int query(int x) { 40 int res = 0 ; 41 while(x) { 42 res += tr[x] ; 43 x -= lowbit(x) ; 44 } return res ; 45 } 46 void solve(int l,int r) { 47 if(l == r) return ; 48 int ll = l, mid = (l+r)>>1, rr = mid+1 ; 49 for(int i=l;i<=r;i++) { 50 if(p[i].a <= mid) add(p[i].c) ; 51 if(p[i].a > mid) ans[p[i].bl] += query(p[i].c) ; 52 } 53 for(int i=l;i<=r;i++) if(p[i].a <= mid) del(p[i].c) ; 54 for(int i=l;i<=r;i++) { 55 if(p[i].a <= mid) tmp[ll++] = p[i] ; 56 else tmp[rr++] = p[i] ; 57 } 58 for(int i=l;i<=r;i++) p[i] = tmp[i] ; 59 solve(l,mid) ; solve(mid+1,r) ; 60 } 61 62 inline bool cmp1(point s,point t) { 63 if(s.a == t.a) { 64 if(s.b == t.b) return s.c < t.c ; 65 return s.b < t.b ; 66 } return s.a < t.a ; 67 } 68 inline bool cmp2(point s,point t) { 69 if(s.b == t.b) { 70 if(s.a == t.a) return s.c < t.c ; 71 return s.a < t.a ; 72 } return s.b < t.b ; 73 } 74 int main() { 75 n = read(), k = read() ; 76 for(int i=1;i<=n;i++) p[i].a = read(), p[i].b = read(), p[i].c = read(), p[i].bl = i ; 77 sort(p+1,p+n+1,cmp1) ; 78 for(int i=1;i<n;i++) { 79 int tot = 0, j = i ; 80 while(p[j].a == p[j+1].a && p[j].b == p[j+1].b && p[j].c == p[j+1].c) tot++, j++ ; 81 // printf("tot:%d ",tot) ; 82 ans[p[i].bl] += tot ; 83 } 84 for(int i=1;i<=n;i++) p[i].a = i ; 85 sort(p+1,p+n+1,cmp2) ; 86 87 // printf("xxx ") ; 88 // for(int i=1;i<=n;i++) { 89 // printf("%d %d %d ",p[i].a,p[i].b,p[i].c) ; 90 // } 91 solve(1,n) ; 92 // for(int i=1;i<=n;i++) printf("%d ",ans[i]) ; 93 for(int i=1;i<=n;i++) num[ans[i]] ++ ; 94 for(int i=0;i<n;i++) printf("%d ",num[i]) ; 95 return 0 ; 96 }
多维偏序：http://cogs.pro:8080/cogs/problem/problem.php?pid=2639
可用bitset水过去。（如果数据范围再大一些的话还要分块，不过这道题数据较水）
另：这道题的数据还有个性质就是每行是个全排列，代码用到了这个性质。不过即使没有这个性质其实也无所谓。
1 // 每维是全排列解法 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<bitset> 6 #define LL long long 7 #define RI register int 8 using namespace std; 9 const int INF = 0x7ffffff ; 10 const int N = 40000 + 10 ; 11 12 inline int read() { 13 int k = 0 , f = 1 ; char c = getchar() ; 14 for( ; !isdigit(c) ; c = getchar()) 15 if(c == '-') f = -1 ; 16 for( ; isdigit(c) ; c = getchar()) 17 k = k*10 + c-'0' ; 18 return k*f ; 19 } 20 int n, k ; int pos[N] ; 21 bitset<N>f[N] ; 22 23 int main() { 24 // freopen("partial_order_plus.in","r",stdin) ; 25 // freopen("partial_order_plus.out","w",stdout) ; 26 n = read(), k = read() ; 27 for(int i=1;i<=n;i++) f[i] = f[i-1], f[i][i-1] = 1 ; 28 for(int j=1;j<=k;j++) { 29 for(int i=1;i<=n;i++) { 30 int x = read() ; pos[x] = i ; 31 } 32 bitset<N>now ; 33 for(int i=1;i<=n;i++) f[pos[i]] &= now, now[pos[i]] = 1 ; 34 } 35 int ans = 0 ; 36 for(int i=1;i<=n;i++) ans += f[i].count() ; 37 printf("%d",ans) ; 38 return 0 ; 39 }
貌似偏序题还可以用kd-tree做，不过本蒟蒻不会qwq。如果日后学到了kd-tree再来更新。