【bzoj4066】【简单题】【kd树】

Description

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

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x₁ y₁ x₂ y₂	1<=x₁<= x₂<=N 1<=y₁<= y₂<=N	输出x₁ y₁ x₂ y₂这个矩形内的数字和
3	无	终止程序

Input

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

接下来每行一个操作。每条命令除第一个数字之外，

均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

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

Sample Input

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

Sample Output

3
5

HINT

数据规模和约定

1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

题解：

比较裸的kd树.

每插入5000次就暴力重建一遍.

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 200010
#define ll long long
using namespace std;
int n,x1,y1,x2,y2,a,opt,rt,f,P(5000);
int lastans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct use{
  int d[2],mn[2],mx[2],v,l,r;
  int sum;
  inline int &operator[](int x){return d[x];}
  inline friend bool operator<(use a,use b){return a[f]<b[f]; } 
  inline friend bool operator==(use a,use b){return a.d[0]==b.d[0]&&a.d[1]==b.d[1];}
}p[N];
inline bool in(int x1,int y1,int x2,int y2,int a,int b,int c,int d){
  return x1<=a&&x2>=c&&y1<=b&&y2>=d;
}
inline bool out(int x1,int y1,int x2,int y2,int a,int b,int c,int d){
  return x2<a||x1>c||y1>d||y2<b;
}
struct kdtree{
  use t[N],T;
  int cnt;
  inline void update(int k){
    int l=t[k].l,r=t[k].r;
    for (int i=0;i<=1;i++){
      t[k].mn[i]=t[k].mx[i]=t[k][i];
      if (l) t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);
      if (l) t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
      if (r) t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);
      if (r) t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
    }
   t[k].sum=t[l].sum+t[r].sum+t[k].v;
  }
  int query(int k,int x1,int y1,int x2,int y2){
    if (!k) return 0;
    ll ans(0);
    if (in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))
      return t[k].sum;
    if (out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))
      return 0;
    if (in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1]))
      ans+=t[k].v;
    ans+=query(t[k].l,x1,y1,x2,y2)+query(t[k].r,x1,y1,x2,y2);
    return ans; 
  }
  void insert(int &k,bool d){
   if(!k){
     k=++cnt;
     t[k][0]=t[k].mn[0]=t[k].mx[0]=T[0];
     t[k][1]=t[k].mn[1]=t[k].mx[1]=T[1];
   }
  if(T==t[k]){
     t[k].v+=T.v,t[k].sum+=T.v;
     return;
  }
  if(T[d]<t[k][d])insert(t[k].l,d^1);
  else insert(t[k].r,d^1);
  update(k);
 }
  int rebuild(int l,int r,int d){
    if (l>r) return 0;f=d;
    int mid=(l+r)>>1;
    nth_element(p+l,p+mid,p+r+1);
    t[mid]=p[mid];
    t[mid].l=rebuild(l,mid-1,d^1);
    t[mid].r=rebuild(mid+1,r,d^1);
    update(mid);return mid;
  }
}kd;
int main(){
  n=read();
  while (1){
    opt=read();
    if (opt==3) break;
    if (opt==1){
      x1=read();y1=read();a=read();
      x1^=lastans;y1^=lastans;a^=lastans;
      kd.T[0]=x1;kd.T[1]=y1;kd.T.v=kd.T.sum=a;
      kd.insert(rt,0);
      if (kd.cnt==P){
        for (int j=1;j<=kd.cnt;j++) p[j]=kd.t[j];
        rt=kd.rebuild(1,kd.cnt,0),P+=5000;
      }
    }
   else{
      x1=read();y1=read();x2=read();y2=read();
      x1^=lastans;y1^=lastans;x2^=lastans;y2^=lastans;
      lastans=kd.query(rt,x1,y1,x2,y2);
      printf("%d\n",lastans);
   }
  } 
}

秒客网