题解:KDtree模板题 (犯了逻辑错误调了2个小时
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=4e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int rt,d,n;
typedef struct node{
int p[2],c[2],maxx[2],minn[2],sum,key;
friend bool operator<(node aa,node bb){
if(aa.p[d]!=bb.p[d])return aa.p[d]<bb.p[d];
return aa.p[d^1]<bb.p[d^1];
}
}node;
node a[MAXN];
void up(int x,int y){
for(int i=0;i<=1;i++)a[x].maxx[i]=max(a[x].maxx[i],a[y].maxx[i]),a[x].minn[i]=min(a[x].minn[i],a[y].minn[i]);
a[x].sum+=a[y].sum;
}
int built(int l,int r,int now){
int mid=(l+r)>>1;
d=now;nth_element(a+l,a+mid,a+r+1);
for(int i=0;i<=1;i++)a[mid].minn[i]=a[mid].maxx[i]=a[mid].p[i];
a[mid].sum=a[mid].key;a[mid].c[0]=a[mid].c[1]=0;
if(l<mid)a[mid].c[0]=built(l,mid-1,now^1),up(mid,a[mid].c[0]);
if(r>mid)a[mid].c[1]=built(mid+1,r,now^1),up(mid,a[mid].c[1]);
return mid;
}
inline void insert(int x)
{
int *t=&rt;
d=0;
while(*t)up(*t,x),t=&a[*t].c[a[x].p[d]>a[*t].p[d]],d=d^1;
*t=x;
}
int ans;
inline void querty(int x,int x1,int y1,int x2,int y2){
if(!x)return ;
int t=x;
if(a[t].minn[0]>=x1&&a[t].maxx[0]<=x2&&a[t].minn[1]>=y1&&a[t].maxx[1]<=y2){ans+=a[t].sum;return ;}
if(a[t].minn[0]>x2||a[t].maxx[0]<x1||a[t].minn[1]>y2||a[t].maxx[1]<y1){return ;}
if(a[x].p[0]>=x1&&a[x].p[0]<=x2&&a[x].p[1]>=y1&&a[x].p[1]<=y2)ans+=a[x].key;
querty(a[x].c[0],x1,y1,x2,y2);
querty(a[x].c[1],x1,y1,x2,y2);
}
int main(){
n=read();int op,x,y,x1,y1,t;
int tot=0;int res=0;
while(op=read()){
if(op==3)break;
if(op==1){
x=read()^res;y=read()^res;t=read()^res;
tot++;
a[tot].c[0]=a[tot].c[1]=0;a[tot].key=a[tot].sum=t;
a[tot].p[0]=a[tot].maxx[0]=a[tot].minn[0]=x;
a[tot].p[1]=a[tot].maxx[1]=a[tot].minn[1]=y;
insert(tot);
if(tot%10000==0)rt=built(1,tot,0);
}
else{
x=read()^res;y=read()^res;x1=read()^res;y1=read()^res;
ans=0;querty(rt,x,y,x1,y1);
res=ans;printf("%d
",res);
}
}
}
4066: 简单题
Time Limit: 50 Sec Memory Limit: 20 MBSubmit: 5024 Solved: 1414
[Submit][Status][Discuss]
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
|
命令 |
参数限制 |
内容 |
|
1 x y A |
1<=x,y<=N，A是正整数 |
将格子x,y里的数字加上A |
|
2 x1 y1 x2 y2 |
1<=x1<= x2<=N 1<=y1<= y2<=N |
输出x1 y1 x2 y2这个矩形内的数字和 |
|
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
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
5
HINT
数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683
新加数据一组，但未重测----2015.05.24