BZOJ 4066: 简单题

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解

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范围内并且解码之后数据仍合法。
样例解释见OJ2683

题解

感动的不行、、终于过了这题、在我不会KDTree的时候，我用树套树！分块！把各种瞎搞的方法丢一起都过不了OwQ！
感谢@PanYuchong 神犇告诉我这题的正确姿势！
（其实我似乎还是不会写KDTree、、上网看了算法原理之后模仿着线段树瞎扮出来的代码、、跑了46S差点T了、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=50010;
struct KDTree{
    int lx,rx;
    int sum,val;
    int nm[2],nx[2],d[2];
    KDTree(){}
    KDTree(int x,int y,int v0){
        nm[0]=nx[0]=d[0]=x;
        nm[1]=nx[1]=d[1]=y;
        sum=val=v0;
        lx=rx=0;
    }
};
KDTree tree[Maxn*4];
int nume;
inline int remin(int a,int b){
    if (a<b) return a;
    return b;
}
inline int remax(int a,int b){
    if (a>b) return a;
    return b;
}
int Root;
inline void update(int x){
    for (int i=0;i<2;i++){
        if (tree[x].lx){
            KDTree ltree=tree[tree[x].lx];
            tree[x].nm[i]=remin(tree[x].nm[i],ltree.nm[i]);
            tree[x].nx[i]=remax(tree[x].nx[i],ltree.nx[i]);
        }
        if (tree[x].rx){
            KDTree rtree=tree[tree[x].rx];
            tree[x].nm[i]=remin(tree[x].nm[i],rtree.nm[i]);
            tree[x].nx[i]=remax(tree[x].nx[i],rtree.nx[i]);
        }
    }
    tree[x].sum=tree[x].val+(tree[x].lx?tree[tree[x].lx].sum:0)+(tree[x].rx?tree[tree[x].rx].sum:0);
    //printf("Merge:%d %d\n",tree[x].lx,tree[x].rx);
    //printf("Merge:%d %d\n",(tree[x].lx?tree[tree[x].lx].sum:0),(tree[x].rx?tree[tree[x].rx].sum:0));
}
void insert(KDTree T,int &x,int now){
    if (!x){
        x=++nume;
        //printf("Insert : %d\n",x);
        tree[x]=T;
    }else{
        if (T.d[0]==tree[x].d[0] && T.d[1]==tree[x].d[1]) {
            tree[x].sum+=T.val;
            tree[x].val+=T.val;
            return ;
        }
        if (T.d[now]<tree[x].d[now])
            insert(T,tree[x].lx,now^1);
        else
            insert(T,tree[x].rx,now^1);
        update(x);
    }
}
int query(int x,int dm[],int dx[],int now){
    if (!x) return 0;
    //printf("Query : Tree->%d Range->(%d,%d)-(%d,%d) Sum->%d\n",x,tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],tree[x].sum);
    if (dm[0]<=tree[x].nm[0] && dm[1]<=tree[x].nm[1] && tree[x].nx[0]<=dx[0] && tree[x].nx[1]<=dx[1]){
        return tree[x].sum;
    }else{
        int ret=0;
        if (dm[0]<=tree[x].d[0] && tree[x].d[0]<=dx[0] && dm[1]<=tree[x].d[1] && tree[x].d[1]<=dx[1]) ret+=tree[x].val;
        if (dm[now]<tree[x].d[now]) ret+=query(tree[x].lx,dm,dx,now^1);
        if (tree[x].d[now]<=dx[now]) ret+=query(tree[x].rx,dm,dx,now^1);
        return ret;
    }
}
int lastAns=0;
int n;
int op;
int x0,y0,x1,y1;
inline void turnX(int &x){x=x^lastAns;}
int main(){
    scanf("%d%d",&n,&op);
    while(op!=3){
        if (op==1){
            scanf("%d%d%d",&x0,&y0,&x1);
            turnX(x0);turnX(y0);turnX(x1);
            insert(KDTree(x0,y0,x1),Root,1);
        }else{
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            turnX(x0);turnX(y0);turnX(x1);turnX(y1);
            if (x0>x1) swap(x0,x1);
            if (y0>y1) swap(y0,y1);
            int dn[]={x0,y0},dx[]={x1,y1};
            lastAns=query(Root,dn,dx,1);
            printf("%d\n",lastAns);
        }
        scanf("%d",&op);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=50010;

struct KDTree{

int lx,rx;

int sum,val;

int nm[2],nx[2],d[2];

KDTree(){}

KDTree(int x,int y,int v0){

nm[0]=nx[0]=d[0]=x;

nm[1]=nx[1]=d[1]=y;

sum=val=v0;

lx=rx=0;

}

};

KDTree tree[Maxn*4];

int nume;

inline int remin(int a,int b){

if (a<b) return a;

return b;

}

inline int remax(int a,int b){

if (a>b) return a;

return b;

}

int Root;

inline void update(int x){

for (int i=0;i<2;i++){

if (tree[x].lx){

KDTree ltree=tree[tree[x].lx];

tree[x].nm[i]=remin(tree[x].nm[i],ltree.nm[i]);

tree[x].nx[i]=remax(tree[x].nx[i],ltree.nx[i]);

}

if (tree[x].rx){

KDTree rtree=tree[tree[x].rx];

tree[x].nm[i]=remin(tree[x].nm[i],rtree.nm[i]);

tree[x].nx[i]=remax(tree[x].nx[i],rtree.nx[i]);

}

tree[x].sum=tree[x].val+(tree[x].lx?tree[tree[x].lx].sum:0)+(tree[x].rx?tree[tree[x].rx].sum:0);

//printf("Merge:%d %d\n",tree[x].lx,tree[x].rx);

//printf("Merge:%d %d\n",(tree[x].lx?tree[tree[x].lx].sum:0),(tree[x].rx?tree[tree[x].rx].sum:0));

}

void insert(KDTree T,int &x,int now){

if (!x){

x=++nume;

//printf("Insert : %d\n",x);

tree[x]=T;

}else{

if (T.d[0]==tree[x].d[0] && T.d[1]==tree[x].d[1]) {

tree[x].sum+=T.val;

tree[x].val+=T.val;

return ;

}

if (T.d[now]<tree[x].d[now])

insert(T,tree[x].lx,now^1);

else

insert(T,tree[x].rx,now^1);

update(x);

}

int query(int x,int dm[],int dx[],int now){

if (!x) return 0;

//printf("Query : Tree->%d Range->(%d,%d)-(%d,%d) Sum->%d\n",x,tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],tree[x].sum);

if (dm[0]<=tree[x].nm[0] && dm[1]<=tree[x].nm[1] && tree[x].nx[0]<=dx[0] && tree[x].nx[1]<=dx[1]){

return tree[x].sum;

}else{

int ret=0;

if (dm[0]<=tree[x].d[0] && tree[x].d[0]<=dx[0] && dm[1]<=tree[x].d[1] && tree[x].d[1]<=dx[1]) ret+=tree[x].val;

if (dm[now]<tree[x].d[now]) ret+=query(tree[x].lx,dm,dx,now^1);

if (tree[x].d[now]<=dx[now]) ret+=query(tree[x].rx,dm,dx,now^1);

return ret;

}

int lastAns=0;

int n;

int op;

int x0,y0,x1,y1;

inline void turnX(int &x){x=x^lastAns;}

int main(){

scanf("%d%d",&n,&op);

while(op!=3){

if (op==1){

scanf("%d%d%d",&x0,&y0,&x1);

turnX(x0);turnX(y0);turnX(x1);

insert(KDTree(x0,y0,x1),Root,1);

}else{

scanf("%d%d%d%d",&x0,&y0,&x1,&y1);

turnX(x0);turnX(y0);turnX(x1);turnX(y1);

if (x0>x1) swap(x0,x1);

if (y0>y1) swap(y0,y1);

int dn[]={x0,y0},dx[]={x1,y1};

lastAns=query(Root,dn,dx,1);

printf("%d\n",lastAns);

}

scanf("%d",&op);

}

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑