1 条题解
-
1
同见于我的洛谷博客
引言
写本题解时,题解区有 篇题解,仅俩 KDT 做法,其他人几乎都是一通 cdq 玄学(?)。
陌上花开是 KDT 求三维偏序的经典模板呀。
KDT 是个好东西,在解决高维问题时,都可以考虑;这题就可以用 KDT 骗分。
请先确保在学会 KDT 基操(build,find)后再阅读本题解。
思路
先写一个 3DT 上去。
复杂度是 的,毫无疑问会 T。
咋办?
观察到各个三维点的编号不影响答案,而影响一个点 的只有三维坐标都不比其大的点,故考虑先按第一维排序,动态插点进一个 2DT 中去(各点只有第二、三维),同期查询 。
要注意的是,第一维坐标相同时,应把之同时插入,再一并查询,以免出现像 这样的数据时挂掉。此外,也不应忘记在答案中删去各点自身。
问题来了
动态插点咋实现?
前俩题解好像都是写了带替罪羊树式重构的 KDT,然而这又臭又长,一点不香。
我们考虑使用其他方法来搞。
由于只有插入没有删除,不用打 KDT 惰性删除标记。
但实际上插入本身也并不方便,于是采取yk链分治技术,即二进制拆分法。
如果使用原始yk链分治算法,对每一块建一个 KDT,那么我们归并操作只能推倒重构(因为几乎没有明显单调性),在插入操作处复杂度是 的(因为单次重构 KDT 复杂度是 的),但常数太大会挂掉。
考虑:我们把原始的 次块归并操作,改为推倒末 块并最后将删去元素与新插入元素重构一个大块。
这样,每个点插入时只重构一次,于是就不会挂了,总插入复杂度是 的。
查询呢?同时维护 个 KDT,难道不 T?
其实由于每块大小不会超过前一块的一半,单次查询复杂度是 $O(\sqrt n+\sqrt{\frac n2}+\sqrt{\frac n4}+\dots+\sqrt{\frac n{2^w}})=O(\sqrt n)$ 的!
因此,总时间复杂度是 的,(好像)可以通过此题!
不过,被卡常了QAQ,几十毫秒死活过不去。
于是加一车常数优化,待夜深人静之时,交它几发,相信你一定会A的QAQ。(来自一个第 次才 AC 的人)
Code
快读快写啥的删了一车,代码更简洁,不一定保证能过,加油卡常吧(
#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; }
- 1
信息
- ID
- 3262
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 52
- 已通过
- 25
- 上传者