【BZOJ4066】简单题（KD-Tree）

题面

题解

如果这题不卡空间，并且不强制在线的话

显然可以用\(CDQ\)分治做

但是它又卡空间又强制在线，于是我们欢快的来用\(KD-Tree\)吧。

用\(KD-Tree\)维护每一个点，每次询问的时候

判断询问的矩形和当前矩形的交

如果全部覆盖直接加上所有的和

如果没有交则直接返回

如果有部分交则递归处理。

我用了两种方案防止\(KD-Tree\)被卡

第一种：定时重构。大概就是每插入\(10000\)次后就重构一次

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 100200#define mid o#define ls (t[o].ch[0])#define rs (t[o].ch[1])#define cmin(a,b) (a
              
               b?a:a=b)inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}const double alpha=0.762333;int D;struct Node{int d[2],v;}a[MAX];bool operator<(Node a,Node b){return a.d[D]
               
                >1;D=nd; nth_element(&a[l],&a[mid],&a[r+1]); t[o].a=a[mid]; if(l
                
                 mid)rs=Build(mid+1,r,nd^1);else rs=0; pushup(o);return o;}void insert(int &o,int nd,Node a){ if(!o){o=tot;t[o].a=a;pushup(o);return;} if(t[o].a.d[nd]
                 
                  =x1&&t[o].a.d[0]<=x2&&t[o].a.d[1]>=y1&&t[o].a.d[1]<=y2) ret+=t[o].a.v; if(ls) { int d=checksame(t[ls],x1,x2,y1,y2); if(d==1)ret+=t[ls].sum; if(d==2)ret+=Query(ls,x1,x2,y1,y2); } if(rs) { int d=checksame(t[rs],x1,x2,y1,y2); if(d==1)ret+=t[rs].sum; if(d==2)ret+=Query(rs,x1,x2,y1,y2); } return ret;}int N,rt;int main(){ N=read(); int lans=0,opt,x,y,A,x1,y1,x2,y2; while(233) { opt=read(); if(opt==3)break; if(opt==1) { x=read()^lans,y=read()^lans,A=read()^lans; insert(rt,0,a[++tot]=(Node){x,y,A}); if(tot%10000==0)rt=Build(1,tot,0); } else { x1=read()^lans,y1=read()^lans,x2=read()^lans,y2=read()^lans; printf("%d\n",lans=Query(rt,x1,x2,y1,y2)); } }}

第二种：类似替罪羊树，当不满足平衡因子时，把子树拍掉重构。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 200200#define ls (t[o].ch[0])#define rs (t[o].ch[1])#define cmin(a,b) (a
              
               b?a:a=b)inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}const double alpha=0.75;int D;struct Node{int d[2],v;}a[MAX];bool operator<(Node a,Node b){return a.d[D]
               
                >1;D=nd; nth_element(&a[l],&a[mid],&a[r+1]); int o=NewNode(); t[o].a=a[mid]; if(l
                
                 mid)rs=Build(mid+1,r,nd^1);else rs=0; pushup(o);return o;}void kill(int o){if(ls)kill(ls);a[++Num]=t[o].a;Q[++top]=o;if(rs)kill(rs);}void checker(int &o,int nd){ if(alpha*t[o].size
                 
                  
                   =x1&&t[o].a.d[0]<=x2&&t[o].a.d[1]>=y1&&t[o].a.d[1]<=y2) ret+=t[o].a.v; if(ls) { int d=checksame(t[ls],x1,x2,y1,y2); if(d==1)ret+=t[ls].sum; if(d==2)ret+=Query(ls,x1,x2,y1,y2); } if(rs) { int d=checksame(t[rs],x1,x2,y1,y2); if(d==1)ret+=t[rs].sum; if(d==2)ret+=Query(rs,x1,x2,y1,y2); } return ret;}int N,rt;int main(){ N=read(); int lans=0,opt,x,y,A,x1,y1,x2,y2; while(233) { opt=read(); if(opt==3)break; if(opt==1) { x=read()^lans,y=read()^lans,A=read()^lans; insert(rt,0,(Node){x,y,A}); } else { x1=read()^lans,y1=read()^lans,x2=read()^lans,y2=read()^lans; printf("%d\n",lans=Query(rt,x1,x2,y1,y2)); } }}