题解 P4848 【崂山白花蛇草水】

· · 题解

kd-tree?不存在的。

暴力能过的题写什么k-dtree???

暴力算法：

维护一个 v 从大到小的数组，查询就暴力从大往小找，找到第k个在矩形内部的点。

维护的方法为维护大小两个数组每一次加点就把点用插入排序插进小数组，当小数组大于 \sqrt n 时把小数组归并进大数组。

这样复杂度为插入的 O(q \sqrt q) 加上查询的 (q^2) 。然后就过了，过了！！！

这个暴力极限数据也只要跑 5s+ 然而kd-tree极限数据要跑 20s+ 。

所以大家一起写暴力吧！

暴力代码（最大点只要跑 2s ）：

（代码进行了部分修改，请不要直接抄这份代码）

#include<bits/stdc++.h>
using namespace std;　
#define re register
struct qus
{
　  int x,y,v;　
}c1[100100],c2[10100];
char B[1<<26],*S=B;int r(){for(;*S<'-';S++);register int x=*S++-'0';for(;*S>='0';x=(x<<3)+(x<<1)+*S++-'0');return x;　}
int main()
{
 　 fread(B,1,1<<26,stdin）;r（）;　
    re int q=r(),tp,x1,y1,x2,y2,k,la=0,n1=0,n2=0;　
    for(　;q--;　)
    {
     　 tp=r();　
        if(tp==1)　
        {
    　　    x1=r（）^la,y1=r（）^la,k=r()^la;　
            for(x2=n2++;x2&&c2[x2].v>k;x2--)　c2[x2+1]=c2[x2];　
            c2[x2+1]=（qus){x1,y1,k};
            if(n2>=800)
 　         {
   　           for(re int i=n1,j=n2,i1=(n1+=n2);i1;i1--)
                {
           　　     if(（!j)||(i&&(c1[i].v>c2[j].v)）)c1[i1]=c1[i],i--;
                 　 else c1[i1]=c2[j],j--;
                }n2=0;
            }
        }//不要抄代码！！！
        if(tp==2）
        {
         　 x1=r()^la,y1=r()^la,x2=r()^la,y2=r()^la,k=r()^la；;　
            if(k>n1+n2){puts("NAIVE!ORZzyz.");la=0;continue;}
            for(re int i=n1,j=n2;i|j;　)
            {
          　　  if((!j)||(i&&c1[i].v>c2[j].v)){if(c1[i].x>=x1&&c1[i].y>=y1&&c1[i].x<=x2&&c1[i]　.y<=y2&&!--k){printf("%d\n",la=c1[i].v);　break;}i--;}
                else {if(c2[j].x>=x1&&c2[j].y>=y1&&c2[j].x<=x2&&c2[j].y<=y2&&!--k){printf("%d\n",la=c2[j].v);break;}j--;}
            }if(k){puts("NAIVE!ORZzyz.");la=0;}
　　    }　　　  　　
    }　
}