1 条题解

  • 0
    @ 2025-10-8 17:06:54
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #define lc t[p].l
    #define rc t[p].r
    using namespace std;
     
    const double A=0.7; //重构常数
    const int N=200010;
    int n,op,x1,x2,y1,y2,ans;
    int K,root,cur; //K维度,root根,cur当前节点
    int g[N],cnt;   //g存储节点的编号
    struct KD{       //KD树节点信息
      int l,r;       //左右孩子
      int v[2],w;    //点的坐标值,点权
      int L[2],U[2]; //子树区域的坐标范围
      int siz,sum;   //子树大小,子树和
    }t[N];
     
    void pushup(int p){ //更新p子树的信息
      t[p].siz=t[lc].siz+t[rc].siz+1;
      t[p].sum=t[lc].sum+t[rc].sum+t[p].w;
      for(int i=0;i<2;i++){
        t[p].L[i]=t[p].U[i]=t[p].v[i];
        if(lc)
          t[p].L[i]=min(t[p].L[i],t[lc].L[i]),
          t[p].U[i]=max(t[p].U[i],t[lc].U[i]);
        if(rc)
          t[p].L[i]=min(t[p].L[i],t[rc].L[i]),
          t[p].U[i]=max(t[p].U[i],t[rc].U[i]);
      }
    }
    bool cmp(int a,int b){ //按点的坐标值比较
      return t[a].v[K]<t[b].v[K];
    }
    int rebuild(int l,int r,int k){ //重构子树
      if(l>r) return 0;
      int m=(l+r)>>1;
      K=k; nth_element(g+l,g+m,g+r+1,cmp);
      t[g[m]].l=rebuild(l,m-1,k^1);
      t[g[m]].r=rebuild(m+1,r,k^1);
      pushup(g[m]);
      return g[m];
    }
    void dfs(int p){ //提取p子树的节点编号
      if(!p) return;
      g[++cnt]=p;  
      dfs(lc);
      dfs(rc);
    }
    void check(int& p,int k){ //检查
      if(A*t[p].siz<max(t[lc].siz, t[rc].siz))
        cnt=0, dfs(p), p=rebuild(1,cnt,k);
    }
    void insert(int& p, int k){ //插点
      if(!p){ p=cur; pushup(p); return;}
      insert(t[cur].v[k]<=t[p].v[k] ? lc : rc, k^1);
      pushup(p);
      check(p,k); //检查是否重构p子树
    }
    int query(int p){ //查询区域数字和
      if(!p||x2<t[p].L[0]||x1>t[p].U[0]|| //不相交
         y2<t[p].L[1]||y1>t[p].U[1]) return 0;
      if(x1<=t[p].L[0]&&t[p].U[0]<=x2&&   //完全覆盖
         y1<=t[p].L[1]&&t[p].U[1]<=y2) return t[p].sum;
      int res=0;
      if(x1<=t[p].v[0]&&t[p].v[0]<=x2&&   //部分覆盖
         y1<=t[p].v[1]&&t[p].v[1]<=y2) res+=t[p].w;
      return query(lc)+query(rc)+res;
    }
    int main(){
      scanf("%d",&n);
      while(scanf("%d",&op)){
        if(op==1){
          cur++;
          scanf("%d%d%d",&t[cur].v[0],&t[cur].v[1],&t[cur].w);
          insert(root,0);
        }
        if(op==2){
          scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
          printf("%d\n",query(root));
        }
        if(op==3) break;
      }
    }
    
    • 1

    信息

    ID
    4348
    时间
    8000ms
    内存
    20MiB
    难度
    8
    标签
    递交数
    15
    已通过
    6
    上传者