3810
myee
2021-07-15 19:15:50
### 引言
写本题解时，题解区有 $35$ 篇题解，仅俩 KDT 做法，其他人几乎都是一通 cdq 玄学（？）。
陌上花开是 KDT 求三维偏序的经典模板呀。
KDT 是个好东西，在解决高维问题时，都可以考虑；[这题](https://www.luogu.com.cn/problem/P7711)就可以用 KDT 骗分。
请先确保在学会 KDT 基操（build，find）后再阅读本题解。
### 思路
先写一个 3DT 上去。
复杂度是 $O(n^{\frac53})$ 的，毫无疑问[会 T](https://www.luogu.com.cn/record/53027731)。
咋办？
观察到各个三维点的编号不影响答案，而影响一个点 $f$ 的只有三维坐标都不比其大的点，故考虑先按第一维排序，动态插点进一个 2DT 中去（各点只有第二、三维），同期查询 $f$。
要注意的是，**第一维坐标相同时，应把之同时插入，再一并查询，以免出现像 $(1,1,1),(1,1,1),(1,1,1),\dots,(1,1,1)$ 这样的数据时挂掉**。此外，**也不应忘记在答案中删去各点自身**。
### 问题来了
动态插点咋实现？
前俩题解好像都是写了带替罪羊树式重构的 KDT，然而这又臭又长，一点不香。
我们考虑使用其他方法来搞。
由于只有插入没有删除，不用打 KDT 惰性删除标记。
但实际上插入本身也并不方便，于是采取[yk链分治](https://www.luogu.com.cn/blog/myee/yk-algorithm)技术，即二进制拆分法。
如果使用原始yk链分治算法，对每一块建一个 KDT，那么我们归并操作只能推倒重构（因为几乎没有明显单调性），在插入操作处复杂度是 $O(n\log^2n)$ 的（因为单次重构 KDT 复杂度是 $O(n\log n)$ 的），但常数太大会挂掉。
考虑：我们把原始的 $\log\operatorname{lowbit}n$ 次块归并操作，改为**推倒末 $\log\operatorname{lowbit}n$ 块并最后将删去元素与新插入元素重构一个大块**。
这样，每个点插入时只重构一次，于是就不会挂了，总插入复杂度是 $O(n\log^2n)$ 的。
查询呢？**同时维护 $O(\log n)$ 个 KDT，难道不 T**?
其实由于每块大小不会超过前一块的一半，单次查询复杂度是 $O(\sqrt n+\sqrt{\frac n2}+\sqrt{\frac n4}+\dots+\sqrt{\frac n{2^w}})=O(\sqrt n)$ 的！
因此，总时间复杂度是 $O(n\sqrt n+n\log^2n)$ 的，（好像）可以通过此题！
[不过](https://www.luogu.com.cn/record/53030941)，被卡常了QAQ，几十毫秒死活过不去。
于是加一车常数优化，待夜深人静之时，交它几发，相信你一定会A的QAQ。（来自一个第 $299$ 次才 [AC](https://www.luogu.com.cn/record/53218123) 的人）
### Code
快读快写啥的删了一车，代码更简洁，不一定保证能过，加油卡常吧（
```cpp
#include <algorithm>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
const uint k=2;
class kdpoint{public:uint D[k];uint&operator[](uint n){return D[n];}};
uint d;
bol operator<(const kdpoint&a,const kdpoint&b){return a.D[d]<b.D[d];}
class kdT
{
public:
typedef kdpoint point;
class node;
voi bzr(){if(rot!=NULL)delete rot;rot=NULL;}
voi build(point*P,uint len){rot=new node,rot->build(P,P+len);}
node*rot;
class node
{
public:
point p;node*ls,*rs;
uint Max[k],Min[k];
ullt sum;
voi bzr(){ls=rs=NULL;}
voi build(point*l,point*r,uint t=0)
{
bzr();
register point*mid=(r-l)/2+l;
d=t;
std::nth_element(l,mid,r);
p=*mid,sum=1;
for(uint i=0;i<k;i++)Max[i]=Min[i]=p[i];
if(l<mid)
{
ls=new node,ls->build(l,mid,(t+1)%k);
for(uint i=0;i<k;i++)_min(Min[i],ls->Min[i]),_max(Max[i],ls->Max[i]);
sum+=ls->sum;
}
if(mid+1<r)
{
rs=new node,rs->build(mid+1,r,(t+1)%k);
for(uint i=0;i<k;i++)_min(Min[i],rs->Min[i]),_max(Max[i],rs->Max[i]);
sum+=rs->sum;
}
}
~node(){if(ls!=NULL)delete ls;if(rs!=NULL)delete rs;}
};
};
kdT T[30];uint tp=0,siz=0;
std::pair<uint,kdpoint>P[100005];
kdpoint K[100005];
voi insert()//yk链分治 O(n\log^2n)
{
*K=P[siz++].second;
uint f=siz&-siz,u=1;
while(f>>=1)//merge过程：推倒
{
u<<=1;
for(uint i=u>>1;i<u;i++)K[i]=P[siz-i-1].second;
T[--tp].bzr();
}
T[tp].bzr(),T[tp++].build(K,u);//merge过程：重构
}
ullt find(kdT::node*p,uint&x,uint&y)
{
if(p==NULL||p->Min[0]>x||p->Min[1]>y)return 0;
if(p->Max[0]<=x&&p->Max[1]<=y)return p->sum;
ullt ans=0;
if(p->p[0]<=x&&p->p[1]<=y)ans=1;
ans+=find(p->ls,x,y)+find(p->rs,x,y);
return ans;
}
inline chr nc() //光速快读
{
static chr buf[1000010],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000010,stdin),p1==p2)?EOF:*p1++;
}
inline ullt read()
{
register ullt ans=0;register chr c;do c=nc();while(c>'9'||c<'0');
do ans=c-'0'+ans*10,c=nc();while(c>='0'&&c<='9');return ans;
}
uint Time[100005];
int main()
{
uint n=read(),m;m=read();
for(uint i=0;i<n;i++)P[i].first=read(),P[i].second[0]=read(),P[i].second[1]=read();
std::sort(P,P+n);
for(uint i=0,j=0;i<n;)
{
for(;j<n&&P[j].first==P[i].first;j++)insert();
while(i<j)
{
uint w=-1;
for(uint k=0;k<tp;k++)w+=find(T[k].rot,P[i].second[0],P[i].second[1]);
Time[w]++,i++;
}
}
for(uint i=0;i<n;i++)printf("%u\n",Time[i]);
return 0;
}
```