bzoj 2683/4066 简单题 题解 k-d tree 简要讲解【k-d tree】

作者: wjyyy 分类: k-d tree,学习笔记,解题报告 发布时间: 2019-06-02 15:48

点击量:50

题目描述

你有一个 $N\times N$ 的棋盘,每个格子内有一个整数,初始时的时候全部为 $0$,现在需要维护两种操作:

命令 参数限制 内容
$1\ x\ y\ A$ $1\le x,y\le N$,$A$ 是正整数 将格子 $(x,y)$ 里的数字加上 $A$
$2\ x_1\ y_1\ x_2\ y_2$ $1\le x_1\le x_2\le N,\ 1\le y_1\le y_2\le N$ 输出以 $(x_1,y_1)$ 为左上角,$(x_2,y_2)$ 为右下角的矩形内的数字和
$3$ 终止程序

输入格式

输入文件第一行一个正整数 $N$。

接下来每行一个操作。每条命令除第一个数字之外,均要异或上一次输出的答案 $last\_ans$,初始时 $last\_ans=0$。

输出格式

对于每个 $2$ 操作,输出一个对应的答案。

输入样例 1

4 1
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

输出样例 1

3
5

数据规模与约定

$1\le N\le 500000$,操作数不超过 $200000$ 个,保证答案在 int 范围内并且解码之后数据仍合法。

题解

k-d tree 模板题

感觉高级数据结构这种东西,得先意会吧,严格的东西研究了论文才会懂。所以不写学习笔记了。给出一个比较好的教程链接:K-D Tree 在信息学竞赛中的应用 by $n+e$。这里只能简单描述一下原理。

对于 $20\mathrm{MB}$ 的空间限制,树套树是肯定过不去的。而在二维平面上的问题可以用 2-D tree 来解决。

K-D tree 是用来处理 $K$ 维空间中一系列问题的一种数据结构,本质是一棵替罪羊树,也就是一棵平衡树。

替罪羊树不会旋转,它只能在构建的时候维持平衡。因此我们希望让根的左右儿子大小尽可能接近。在一维数列上,我们会考虑取中位数 $mid$。但在高维平面上,它有很多个关键字,并且某一关键字可能会有重复。

这个的一个经典解决办法就是按深度轮流取某一维,比如第 $i$ 层需要以第 $i$ 维为关键字取中位数。这样对任何数据都不会被卡到暴力复杂度。

取中位数可以用 std::nth_element() 来完成,这个函数的复杂度是线性的,所以构造一棵 k-d tree 的复杂度是 $O(n\log n)$。

插入时可以在平衡树上二分。为了保持替罪羊树一定的平衡,需要维护每个节点的子树大小 $sz$。如果发现不平衡,那么需要把当前子树“拍扁重构”。

因此插入的最坏复杂度是均摊 $O(\sqrt n)$。

查矩形直接参考线段树的范围判断即可。这里和线段树不同的是,线段树当前节点维护是当前节点=左儿子+右儿子,平衡树维护的是当前节点=左儿子+当前节点+右儿子

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define ls ch[0][rt]
#define rs ch[1][rt]
char buf[2100000],*p1=buf,*p2=buf;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
using std::nth_element;
int ch[2][200100],v[200100],x[2][200100],y[2][200100],c[2][200100],pcnt=0;
int sz[200100],root=0;
long long sum[200100];
int Newnode(int X,int Y,int z)
{
    ++pcnt;
    sum[pcnt]=v[pcnt]=z;
    x[0][pcnt]=x[1][pcnt]=c[0][pcnt]=X;
    y[0][pcnt]=y[1][pcnt]=c[1][pcnt]=Y;
    return pcnt;
}
int a[200100],cnt=0;
void dfs(int rt)
{
    if(ls)
        dfs(ls);
    a[++cnt]=rt;
    if(rs)
        dfs(rs);
}
inline bool cmp0(int a,int b)
{return c[0][a]<c[0][b];}
inline bool cmp1(int a,int b)
{return c[1][a]<c[1][b];}
void maintain(int &rt)
{
    sz[rt]=sz[ls]+1+sz[rs];
    sum[rt]=sum[ls]+v[rt]+sum[rs];
    x[0][rt]=Min(c[0][rt],Min(x[0][ls],x[0][rs]));
    x[1][rt]=Max(c[0][rt],Max(x[1][ls],x[1][rs]));
    y[0][rt]=Min(c[1][rt],Min(y[0][ls],y[0][rs]));
    y[1][rt]=Max(c[1][rt],Max(y[1][ls],y[1][rs]));
}
void build(int &rt,int l,int r,int d)
{
    if(l>r)
    {
        rt=0;
        return;
    }
    int mid=(l+r)>>1;
    nth_element(a+l,a+mid,a+r+1,d?cmp1:cmp0);
    rt=a[mid];
    build(ls,l,mid-1,!d);
    build(rs,mid+1,r,!d);
    maintain(rt);
}
void Insert(int &rt,int nd,int d)
{
    if(!rt)
    {
        rt=nd;
        return;
    }
    Insert(ch[c[d][nd]>=c[d][rt]][rt],nd,!d);
    maintain(rt);
}
int Cnt=0;
void Find(int &rt,int nd,int d)
{
    if(rt==nd)
        return;
    if(Max(sz[ls],sz[rs])>sz[rt]*.85)
    {
        cnt=0;
        dfs(rt);
        build(rt,1,cnt,d);
        return;
    }
    Find(ch[c[d][nd]>=c[d][rt]][rt],nd,!d);
}
int ask(int rt,int lx,int ly,int rx,int ry)
{
    if(lx<=x[0][rt]&&rx>=x[1][rt]&&ly<=y[0][rt]&&ry>=y[1][rt])
        return sum[rt];
    if(rx<x[0][rt]||lx>x[1][rt]||ry<y[0][rt]||ly>y[1][rt])
        return 0;
    return ask(ls,lx,ly,rx,ry)+((c[0][rt]>=lx&&c[0][rt]<=rx&&c[1][rt]>=ly&&c[1][rt]<=ry)?v[rt]:0)+ask(rs,lx,ly,rx,ry);
}
int main()
{
#ifdef wjyyy
    freopen("a.in","r",stdin);
#endif
    x[0][0]=y[0][0]=0x7fffffff;
    int op,n=read(),X,Y,z,x_,y_,lstans=0;
    while(op!=3)
    {
        op=read();
        if(op==1)
        {
            X=read()^lstans;
            Y=read()^lstans;
            z=read()^lstans;
            Insert(root,Newnode(X,Y,z),0);
            Find(root,pcnt,0);
        }
        else if(op==2)
        {
            X=read()^lstans;
            Y=read()^lstans;
            x_=read()^lstans;
            y_=read()^lstans;
            lstans=ask(root,X,Y,x_,y_);
            printf("%d\n",lstans);
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */