D
e
s
c
r
i
p
t
i
o
n
Description
Description
有
n
n
n个元素，每个元素有
a
i
,
b
i
,
c
i
a_i,b_i,c_i
ai,bi,ci三个属性，设
f
(
i
)
f(i)
f(i)表示满足
a
j
≤
a
i
,
b
j
≤
b
i
,
c
j
≤
c
i
a_j\leq a_i,b_j\leq b_i,c_j\leq c_i
aj≤ai,bj≤bi,cj≤ci的
j
j
j的数量，对于
d
∈
[
0
,
n
−
1
]
d\in[0,n-1]
d∈[0,n−1]，求满足
f
(
i
)
=
d
f(i)=d
f(i)=d的数量
S
o
l
u
t
i
o
n
Solution
Solution
经典的三维偏序问题，让我们从最基本的二维偏序开始讲起
二维偏序就是排序去掉一维，剩下一维树状数组或归并排序（
c
d
q
cdq
cdq）求逆序对的方法
现在升级到三维偏序，怎么做呢？
首先仍然是排序去掉一维，然后下一维
c
d
q
cdq
cdq分治套树状数组就解决了，当然也可以
c
d
q
cdq
cdq分治再套
c
d
q
cdq
cdq
那能不能树状数组套树状数组呢？空间太大！用
m
a
p
map
map多一个
l
o
g
log
log，不过你也可以像
c
t
s
c
2019
r
k
1
ctsc2019rk1
ctsc2019rk1的
r
q
y
rqy
rqy大爷那样打一个哈希表，不过这里不推荐
听说还有平衡树套树状数组？本蒟蒻不会呀QWQ
P
.
S
:
P.S:
P.S:由于本题是
≤
\leq
≤，所以打树状数组的同学对于
=
=
=这种情况要特殊处理哦
时间复杂度？
O
(
n
l
o
g
n
l
o
g
k
)
≈
O
(
n
l
o
g
2
n
)
O(nlognlogk)\approx O(nlog^2n)
O(nlognlogk)≈O(nlog2n)
等等！！！ 根据这个复杂度，貌似
c
d
q
cdq
cdq套树状数组的时候不用
O
(
n
)
O(n)
O(n)合并了耶，直接
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)排序就好了鸭，反正这样的复杂度也是双
l
o
g
log
log（懒人专属鸭）
C
o
d
e
Code
Code【
c
d
q
cdq
cdq套
c
d
q
cdq
cdq】
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std
;int ans
[100010],n
,k
,d
[100010];
inline long long read()
{
char c
;int d
=1;long long f
=0;
while(c
=getchar(),!isdigit(c
))if(c
==45)d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
struct node
{
int x
,y
,z
,*ans
;bool b
;
inline void rd(){x
=read();y
=read();z
=read();return;}
inline bool operator ==(const node
&a
){return x
==a
.x
&&y
==a
.y
&&z
==a
.z
;}
}a
[100010],b
[100010],c
[100010];
inline bool cmp(node x
,node y
){return x
.x
<y
.x
||x
.x
==y
.x
&&x
.y
<y
.y
||x
.x
==y
.x
&&x
.y
==y
.y
&&x
.z
<y
.z
;}
inline void cdq2(int l
,int r
)
{
if(l
==r
) return;
int mid
=l
+r
>>1;
cdq2(l
,mid
);cdq2(mid
+1,r
);
for(register int i
=l
,j
=l
,k
=mid
+1,cnt
=0;i
<=r
;i
++)
{
if((k
>r
||b
[j
].z
<=b
[k
].z
)&&j
<=mid
) c
[i
]=b
[j
++],cnt
+=c
[i
].b
;
else {c
[i
]=b
[k
++];if(!c
[i
].b
) *c
[i
].ans
+=cnt
;}
}
for(register int i
=l
;i
<=r
;i
++) b
[i
]=c
[i
];
return;
}
inline void cdq(int l
,int r
)
{
if(l
==r
) return;
int mid
=l
+r
>>1;
cdq(l
,mid
);cdq(mid
+1,r
);
for(register int i
=l
,j
=l
,k
=mid
+1;i
<=r
;i
++)
{
if((k
>r
||a
[j
].y
<=a
[k
].y
)&&j
<=mid
) b
[i
]=a
[j
++],b
[i
].b
=1;
else b
[i
]=a
[k
++],b
[i
].b
=0;
}
for(register int i
=l
;i
<=r
;i
++) a
[i
]=b
[i
];
cdq2(l
,r
);
return;
}
signed main()
{
n
=read();k
=read();
for(register int i
=1;i
<=n
;i
++) a
[i
].rd(),a
[i
].ans
=&ans
[i
];
sort(a
+1,a
+1+n
,cmp
);
for(register int i
=n
-1;i
;i
--) if(a
[i
]==a
[i
+1]) *a
[i
].ans
=*a
[i
+1].ans
+1;
cdq(1,n
);
for(register int i
=1;i
<=n
;i
++) d
[ans
[i
]]++;
for(register int i
=0;i
<n
;i
++) printf("%d\n",d
[i
]);
}
