题目描述

有 nn 个元素，第 ii 个元素有 a_iai​、b_ibi​、c_ici​ 三个属性，设 f(i)f(i) 表示满足 a_j \leq a_iaj​≤ai​ 且 b_j \leq b_ibj​≤bi​ 且 c_j \leq c_icj​≤ci​的 jj 的数量。

对于 d \in [0, n)d∈[0,n)，求 f(i) = df(i)=d 的数量

输入输出格式

输入格式：

 

第一行两个整数 nn、kk，分别表示元素数量和最大属性值。

之后 nn 行，每行三个整数 a_iai​、b_ibi​、c_ici​，分别表示三个属性值。

 

输出格式：

 

输出 nn 行，第 d + 1d+1 行表示 f(i) = df(i)=d 的 ii 的数量。

 

输入输出样例

输入样例#1： 

10 33 3 32 3 32 3 13 1 13 1 21 3 11 1 21 2 21 3 21 2 1

输出样例#1： 

3130101001

说明

1 \leq n \leq 100000, 1 \leq k \leq 2000001≤n≤100000,1≤k≤200000

---

---

---

 

 

就是一维排序，一维cdq，一维数据结构，

然后就是要把萨格属性完全相同的要去掉，并在这个属性的个数上+1. 其他的就没什么了

其实一开始看到cdq是一脸懵逼的，怎么看也看不懂，但是理解了以后就会发现这玩意也挺简单的。

---

---

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 struct point{ 6     int a,b,c,id; 7     point(){ 8         a=b=c=id=0; 9     }10 }num[100001],tem[100001];11 bool cmp(point lhs,point rhs){12     if(lhs.a!=rhs.a)return lhs.a