不知道从哪里下的 PDF，感觉写的很好。
处理偏序问题时，如果偏序条件都带等号，则需要考虑两个元素完全相同的情况，这时需要该元素 $a$ 的统计个数 $\textit{cnt}$，然后统计满足偏序条件元素个数 $x$，则 $a$ 的答案为 $x-1$，同时直接做 $\textit{cnt}$ 的贡献。
一维偏序
排序即可。
二维偏序
排序之后树状数组统计即可。
比如逆序对。
三维偏序
有 $n$ 个元素，第 $ i $ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i$ 且 $ b_j \leq b_i$ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。
对于所有 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。
设 $a_i,b_i,c_i$ 最大值为 $k$，$1\leq n\leq10^5,1\leq a_i,b_i,c_i\leq k\leq2\times10^5$。
考虑先按照 $a$ 排序，之后就是要求满足 $b_j\leq b_i,c_j\leq c_i$，这就是一个二维限制问题。
考虑树套树解决，树状数组套线段树即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
但是需要稍微卡一下空间。 ```cpp //#include<bits/stdc++.h> #include<algorithm> #include<iostream> #include<cstring> #include<iomanip> #include<cstdio> #include<string> #include<vector> #include<cmath> #include<ctime> #include<deque> #include<queue> #include<stack> #include<list> using namespace std; constexpr const int N=1e5,V=2e5; struct element{
int a,b,c; }a[N+1]; int n,k,ans[N+1]; int size; struct node{
int l,r;
int lChild,rChild;
int value; }t[V*80+1]; struct bit{
struct segTree{
int root;
int create(node x){
t[++size]=x;
return size;
}
void up(int p){
t[p].value=t[t[p].lChild].value+t[t[p].rChild].value;
}
void down(int p){
int mid=t[p].l+t[p].r>>1;
if(!t[p].lChild){
t[p].lChild=create({t[p].l,mid});
}
if(!t[p].rChild){
t[p].rChild=create({mid+1,t[p].r});
}
}
void add(int p,int x,int k){
if(t[p].l==t[p].r){
t[p].value+=k;
return;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid){
if(!t[p].lChild){
t[p].lChild=create({t[p].l,mid});
}
add(t[p].lChild,x,k);
}else{
if(!t[p].rChild){
t[p].rChild=create({mid+1,t[p].r});
}
add(t[p].rChild,x,k);
}
up(p);
}
void add(int x,int k){
add(root,x,k);
}
int query(int p,int x){
if(t[p].r<=x){
return t[p].value;
} // down(p);
int ans=0;
if(t[p].lChild){
ans=query(t[p].lChild,x);
}
if(t[p].rChild){
if(t[t[p].rChild].l<=x){
ans+=query(t[p].rChild,x);
}
}
return ans;
}
int query(int x){
return query(root,x);
}
}T[V+1];
int lowbit(int x){
return x&-x;
}
void insert(int b,int c,int x){
while(b<=k){
T[b].add(c,x);
b+=lowbit(b);
}
}
int query(int b,int c){
int ans=0;
while(b){
ans+=T[b].query(c);
b-=lowbit(b);
}
return ans;
}
void build(){
for(int i=1;i<=k;i++){
T[i].root=T[i].create({1,k});
}
} }T; int main(){ // freopen("test.in","r",stdin); // freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
T.build();
for(int i=1;i<=n;i++){
cin>>a[i].a>>a[i].b>>a[i].c;
}
sort(a+1,a+n+1,[](element a,element b){
if(a.a!=b.a){
return a.a<b.a;
}else if(a.b!=b.b){
return a.b<b.b;
}else{
return a.c<b.c;
}
});
for(int i=1;i<=n;i++){
int cnt=1;
while(i<n&&a[i+1].a==a[i].a&&a[i+1].b==a[i].b&&a[i+1].c==a[i].c){
i++;
cnt++;
}
T.insert(a[i].b,a[i].c,cnt);
ans[T.query(a[i].b,a[i].c)-1]+=cnt;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0; } ```
