bzoj3262/luogu3810 陌上花开

学习了k-d tree，觉得很暴力，还被卡常了。

传送门

这题是有k-d tree做法的，不过很技巧，好像还有另一篇k-d tree题解，但他建了两棵树，我也没大看懂。

三维的k-d tree是一定过不去的，得先把三维变成二维。

首先要按第三维排序，按顺序一次性加入第三维相同的点，这样就自动省去了第三维。

一开始我写的是定期重构，参数是0.7时最快，最大的点也跑了2s。

这个$n\sqrt{n}$的优美做法被卡到了60分，让我十分愤懑。于是我拿出了以前没写过的另一种插入做法，先把所有的点去重一下都加进去，先建好树，把每个点所控制的矩形也先处理好，打上被删除的标记，插入时找的树上对应的点把点权+1，其他的都不改。这样的话最大的点就是1s了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define re register
using namespace std;
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(int&x){scanf("%d",&x);}
#endif
const double fac=0.70;
struct point{
    int d[2],z;
}a[100001],b[100001];
struct kdtree{
    int ch[2],sz,x[2],d[2],y[2],lv;
}t[100001];
int f[100001],n,tot,u,root,m;
inline bool cmp1(point x,point y){return x.z<y.z;}
inline bool cmp2(point x,point y){return x.d[u]<y.d[u];}
inline bool cmp3(point x,point y){
    if (x.d[0]!=y.d[0]) return x.d[0]<y.d[0];
    return x.d[1]<y.d[1];
}
inline void pushup(int rt){
    int l=t[rt].ch[0],r=t[rt].ch[1];
    t[rt].sz=t[l].sz+t[r].sz+t[rt].lv;
    if (l){
        t[rt].x[0]=min(t[rt].x[0],t[l].x[0]);
        t[rt].y[0]=min(t[rt].y[0],t[l].y[0]);
        t[rt].x[1]=max(t[rt].x[1],t[l].x[1]);
        t[rt].y[1]=max(t[rt].y[1],t[l].y[1]);
    }
    if (r){
        t[rt].x[0]=min(t[rt].x[0],t[r].x[0]);
        t[rt].y[0]=min(t[rt].y[0],t[r].y[0]);
        t[rt].x[1]=max(t[rt].x[1],t[r].x[1]);
        t[rt].y[1]=max(t[rt].y[1],t[r].y[1]);
    }
}
inline void up(int rt){
    int l=t[rt].ch[0],r=t[rt].ch[1];
    t[rt].sz=t[l].sz+t[r].sz+t[rt].lv;
}
int build(int d,int l,int r){
    if (l>r) return 0; u=d;
    int mid=(l+r)>>1,rt=++tot;
    nth_element(b+l,b+mid,b+r+1,cmp2);
    t[rt].x[0]=t[rt].x[1]=t[rt].d[0]=b[mid].d[0];
    t[rt].y[0]=t[rt].y[1]=t[rt].d[1]=b[mid].d[1];
    t[rt].ch[0]=build(d^1,l,mid-1);
    t[rt].ch[1]=build(d^1,mid+1,r);
    pushup(rt); return rt;
}
void ins(int rt,point x){
    if (t[rt].d[0]==x.d[0]&&t[rt].d[1]==x.d[1]){
        t[rt].lv++; t[rt].sz++; return;
    }
    int l=t[rt].ch[0],r=t[rt].ch[1];
    if (t[l].x[0]<=x.d[0]&&x.d[0]<=t[l].x[1]&&
        t[l].y[0]<=x.d[1]&&x.d[1]<=t[l].y[1])
        ins(l,x);
    if (t[r].x[0]<=x.d[0]&&x.d[0]<=t[r].x[1]&&
        t[r].y[0]<=x.d[1]&&x.d[1]<=t[r].y[1])
        ins(r,x);
    up(rt);
    return;
}
int query(int rt,point x){
    if (!rt||!t[rt].sz) return 0;
    if (t[rt].x[0]>x.d[0]||t[rt].y[0]>x.d[1])
        return 0;
    if (t[rt].x[1]<=x.d[0]&&t[rt].y[1]<=x.d[1])
        return t[rt].sz;
    int num=query(t[rt].ch[0],x)+query(t[rt].ch[1],x);
    if (t[rt].d[0]<=x.d[0]&&t[rt].d[1]<=x.d[1]) num+=t[rt].lv;
    return num;
}
void debug(int rt){
    if (t[rt].ch[0]) debug(t[rt].ch[0]);
    printf("num:%d dx:%d dy:%d ch0:%d ch1:%d sz:%d lv:%d\n",
    rt,t[rt].d[0],t[rt].d[1],t[rt].ch[0],t[rt].ch[1],t[rt].sz,t[rt].lv);
    if (t[rt].ch[1]) debug(t[rt].ch[1]);
}
int main(){
//	freopen("0a.in","r",stdin);
//	freopen("0a.out","w",stdout);
    int k;
    read(n),read(k);
    for (re int i=1; i<=n; i++)
        read(a[i].d[0]),read(a[i].d[1]),read(a[i].z);
    sort(a+1,a+n+1,cmp3);
    for (int i=1; i<=n; i++)
        if (a[i].d[0]!=a[i-1].d[0]||a[i].d[1]!=a[i-1].d[1])
            b[++m]=a[i];
    root=build(0,1,m);
    sort(a+1,a+n+1,cmp1);
    for (re int p=1; p<=n; p++){
        k=p;
        while (a[k+1].z==a[k].z) k++;
        for (re int i=p; i<=k; i++) ins(root,a[i]);
        for (re int i=p; i<=k; i++) f[query(root,a[i])]++;
        p=k;
//		debug(root); puts("");
    }
    for (re int i=1; i<=n; i++) printf("%d\n",f[i]);
    return 0;
}