[BZOJ4066/Luogu4148]简单题(KDT)

发布于 2018-05-14  106 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4066/Luogu4148]简单题(KDT)

Description

你有一个 N×NN \times NN×N 的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:
1 x y A 1≤x,y≤N1\le x,y\le N1≤x,y≤N$$ ,A是正整数。将格子x,y里的数字加上 AAA
2 x1 y1 x2 y2 1≤x1≤x2≤N1 \le x_1 \le x_2 \le N1≤x1​≤x2​≤N , 1≤y1≤y2≤N1 \le y_1\le y_2 \le N1≤y1​≤y2​≤N 。输出 x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​ 这个矩形内的数字和
3 无 终止程序

Tag

KDT

解决思路

用KDT维护暴力查找点是否在矩形内部。具体来说,若当前KDT结点维护的矩形与查询矩形没有交,则直接退出。若当前矩形整个完全包含于查询矩形中,则直接返回整个矩形的和。
至于插入操作,按照KDT的排序方式插入,每10000重构一次。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define InRange(x,y,x1,y1,x2,y2) ((x>=x1)&&(x<=x2)&&(y>=y1)&&(y<=y2))

const int maxN=201000*2;
const int inf=2147483647;

class KDT
{
public:
    int ls,rs;
    int sum,key;
    int P[2],Mn[2],Mx[2];
};

int n;
KDT T[maxN];
int root,nowD;

bool operator < (KDT A,KDT B);
int Build(int l,int r,int D);
void Update(int now);
void Insert(int now,int D);
int Query(int now,int x1,int y1,int x2,int y2);
void Outp(int now);

int main()
{
    int N;scanf("%d",&N);N=0;
    int opt,lastans=0;
    while (scanf("%d",&opt)!=EOF)
    {
        if (opt==3) break;
        if (opt==1)
        {
            n++;scanf("%d%d%d",&T[n].P[0],&T[n].P[1],&T[n].key);
            T[n].P[0]^=lastans;T[n].P[1]^=lastans;T[n].key^=lastans;
            T[n].Mn[0]=T[n].Mx[0]=T[n].P[0];
            T[n].Mn[1]=T[n].Mx[1]=T[n].P[1];
            T[n].sum=T[n].key;
            if (n==1) root=1;
            else Insert(root,0);
            if (n%10000==0) root=Build(1,n,0);
        }
        if (opt==2)
        {
            int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1^=lastans;y1^=lastans;x2^=lastans;y2^=lastans;
            printf("%d\n",lastans=Query(root,x1,y1,x2,y2));
        }
    }
    return 0;
}

bool operator < (KDT A,KDT B){
    return A.P[nowD]<B.P[nowD];
}

int Build(int l,int r,int D)
{
    if (l>r) return 0;
    int mid=(l+r)>>1;
    nowD=D;
    nth_element(&T[l],&T[mid],&T[r+1]);
    T[mid].Mn[0]=T[mid].Mx[0]=T[mid].P[0];
    T[mid].Mn[1]=T[mid].Mx[1]=T[mid].P[1];
    T[mid].sum=T[mid].key;
    T[mid].ls=Build(l,mid-1,D^1);
    T[mid].rs=Build(mid+1,r,D^1);
    Update(mid);return mid;
}

void Update(int now)
{
    int ls=T[now].ls,rs=T[now].rs;
    T[now].sum=T[now].key;
    if (ls) T[now].sum+=T[ls].sum;
    if (rs) T[now].sum+=T[rs].sum;
    if (ls) T[now].Mn[0]=min(T[now].Mn[0],T[ls].Mn[0]),T[now].Mn[1]=min(T[now].Mn[1],T[ls].Mn[1]),T[now].Mx[0]=max(T[now].Mx[0],T[ls].Mx[0]),T[now].Mx[1]=max(T[now].Mx[1],T[ls].Mx[1]);
    if (rs) T[now].Mn[0]=min(T[now].Mn[0],T[rs].Mn[0]),T[now].Mn[1]=min(T[now].Mn[1],T[rs].Mn[1]),T[now].Mx[0]=max(T[now].Mx[0],T[rs].Mx[0]),T[now].Mx[1]=max(T[now].Mx[1],T[rs].Mx[1]);
    return;
}

void Insert(int now,int D)
{
    if (T[now].P[D]>T[n].P[D])
    {
        if (T[now].ls==0) T[now].ls=n;
        else Insert(T[now].ls,D^1);
    }
    else
    {
        if (T[now].rs==0) T[now].rs=n;
        else Insert(T[now].rs,D^1);
    }
    Update(n);
    Update(now);return;
}

int Query(int now,int x1,int y1,int x2,int y2)
{
    if ((T[now].Mn[0]>=x1)&&(T[now].Mn[0]<=x2)&&(T[now].Mn[1]>=y1)&&(T[now].Mn[1]<=y2)&&(T[now].Mx[0]>=x1)&&(T[now].Mx[0]<=x2)&&(T[now].Mx[1]>=y1)&&(T[now].Mx[1]<=y2)) return T[now].sum;
    if ((x2<T[now].Mn[0])||(x1>T[now].Mx[0])||(y1>T[now].Mx[1])||(y2<T[now].Mn[1])) return 0;
    int Ret=0;
    if ((T[now].P[0]>=x1)&&(T[now].P[0]<=x2)&&(T[now].P[1]>=y1)&&(T[now].P[1]<=y2)) Ret+=T[now].key;
    if (T[now].ls) Ret+=Query(T[now].ls,x1,y1,x2,y2);
    if (T[now].rs) Ret+=Query(T[now].rs,x1,y1,x2,y2);
    return Ret;
}

void Outp(int now)
{
    cout<<now<<":("<<T[now].P[0]<<","<<T[now].P[1]<<") ("<<T[now].Mn[0]<<","<<T[now].Mn[1]<<") ("<<T[now].Mx[0]<<","<<T[now].Mx[1]<<") "<<T[now].ls<<" "<<T[now].rs<<endl;
    if (T[now].ls) Outp(T[now].ls);
    if (T[now].rs) Outp(T[now].rs);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4066/Luogu4148]简单题(KDT)


HNCJ OIer