BZOJ 4066 简单题

题目大意

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

1 x y A ($1 \le x,y \le N$，A是正整数) 将格子x,y里的数字加上A 2 x1 y1 x2 y2 ($1 \le x1 \le x2 \le N,1 \le y1 \le y2 \le N$) 输出x1 y1 x2 y2这个矩形内的数字和

二维K-D Tree+Lazy标记。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300000
int n,md,ia,ib,ic,id,LA,rt,tot;
int sw;
struct node
{
    int v[2],mx[2],mn[2],ls,rs,sm,vl;
    bool operator<(const node &tg)const{return v[sw]==tg.v[sw]?v[sw^1]<tg.v[sw^1]:v[sw]<tg.v[sw];}
}p[N];
inline void pushup(int pos)
{
    p[pos].sm=p[p[pos].ls].sm+p[p[pos].rs].sm+p[pos].vl;
    p[pos].mx[0]=max(max(p[p[pos].ls].mx[0],p[p[pos].rs].mx[0]),p[pos].v[0]);
    p[pos].mx[1]=max(max(p[p[pos].ls].mx[1],p[p[pos].rs].mx[1]),p[pos].v[1]);
    p[pos].mn[0]=min(min(p[p[pos].ls].mn[0],p[p[pos].rs].mn[0]),p[pos].v[0]);
    p[pos].mn[1]=min(min(p[p[pos].ls].mn[1],p[p[pos].rs].mn[1]),p[pos].v[1]);
}
int rebuild(int l,int r,int now)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    sw=now;
    nth_element(p+l,p+mid,p+r+1);
    p[mid].ls=rebuild(l,mid-1,now^1),p[mid].rs=rebuild(mid+1,r,now^1);
    pushup(mid);
    return mid;
}
void insert(int &pos,int x,int y,int z,int now)
{
    if(!pos)
    {
        pos=++tot;
        p[pos].v[0]=x,p[pos].v[1]=y;
        p[pos].sm=p[pos].vl=z;
        pushup(pos);
        return;
    }
    if(p[pos].v[0]==x&&p[pos].v[1]==y) p[pos].vl+=z;
    else if(now==0)
    {
        if(p[pos].v[now]<x) insert(p[pos].ls,x,y,z,now^1);
        else insert(p[pos].rs,x,y,z,now^1);
    }
    else if(now==1)
    {
        if(p[pos].v[now]<y) insert(p[pos].ls,x,y,z,now^1);
        else insert(p[pos].rs,x,y,z,now^1);
    }
    pushup(pos);
}
void query(int pos,int W,int A,int S,int D)
{
    if(!pos||p[pos].mn[0]>D||p[pos].mx[0]<A||p[pos].mn[1]>W||p[pos].mx[1]<S) return;
    if(p[pos].mn[0]>=A&&p[pos].mx[0]<=D&&p[pos].mn[1]>=S&&p[pos].mx[1]<=W) {LA+=p[pos].sm;return;}
    if(p[pos].v[0]>=A&&p[pos].v[0]<=D&&p[pos].v[1]>=S&&p[pos].v[1]<=W) LA+=p[pos].vl;
    query(p[pos].ls,W,A,S,D);
    query(p[pos].rs,W,A,S,D);
}
int main()
{
    p[0].mn[0]=p[0].mn[1]=0x3f3f3f3f,p[0].mx[0]=p[0].mx[1]=-0x3f3f3f3f;
    srand(1026);
    scanf("%d",&n);
    while(scanf("%d",&md),md!=3)
    {
        if(!(rand()%4000)) rt=rebuild(1,tot,0);
        switch(md)
        {
            case 1:scanf("%d%d%d",&ia,&ib,&ic),ia^=LA,ib^=LA,ic^=LA,insert(rt,ia,ib,ic,0);break;
            case 2:scanf("%d%d%d%d",&ia,&ib,&ic,&id),ia^=LA,ib^=LA,ic^=LA,id^=LA,LA=0,query(rt,id,ia,ib,ic),printf("%d\n",LA);break;
        }
    }
    return 0;
}