P4169 [Violet]天使玩偶/SJY摆棋子

链接

思路

luogu以前用CDQ一直过不去。

bzoj还是卡时过去的。

今天终于用k-dtree给过了。

代码

#include 
    
     using namespace std;const int INF=0x3f3f3f3f,N=1e6+7;;const double alph(0.75);int WD,ans,rub[N],tot,top;struct Point {    int x[2];    bool operator < (const Point b) const {        return x[WD]
     
      r) return 0;    int u=newnode(),mid=(l+r)>>1;    WD=wd;    nth_element(p+l,p+mid,p+r+1);    e[u].tp=p[mid];    e[u].ls=build(l,mid-1,wd^1);    e[u].rs=build(mid+1,r,wd^1);    up(u);    return u;}void pia(int u,int num) {    if(e[u].ls) pia(e[u].ls,num);    p[num+e[e[u].ls].siz+1]=e[u].tp;    rub[++top]=u;    if(e[u].rs) pia(e[u].rs,num+e[e[u].ls].siz+1);}void check(int &u,int wd) {    if(alph*e[u].siz