解法:
// 2391826 2011-01-24 14:47:58 Accepted 3018 C++ 840 17756 redsea
// 2391828 2011-01-24 14:54:21 Accepted 3018 C++ 840 17756 redsea
#include<stdio.h>
#include<string.h>
#define MAXN 500000
#define N 20002
struct seg
{
int dx, dy, ux, uy;
int ch[4];
int total;
}sgt[MAXN];
int sgtn;
int ans;
int w(int x, int y, int dx, int dy, int ux, int uy)
{
int midx = (dx+ux)/2;
int midy = (dy+uy)/2;
if(x>=dx && x<=midx){
if(y>=dy && y<=midy)
return 0;
else
return 1;
}
else
{
if(y>=dy && y<=midy)
return 2;
else
return 3;
}
}
int init(int dx, int ux, int dy, int uy)
{
sgt[sgtn].dx = dx;
sgt[sgtn].ux = ux;
sgt[sgtn].dy = dy;
sgt[sgtn].uy = uy;
sgt[sgtn].total = 0;
for(int i = 0; i < 4; i++)
sgt[sgtn].ch[i] = -1;
sgtn++;
return sgtn-1;
}
void insert(int root, int x, int y, int a)
{
if(sgt[root].dx == sgt[root].ux && sgt[root].dx == x && sgt[root].dy == sgt[root].uy && sgt[root].dy == y){
sgt[root].total += a;
return;
}
int id = w(x,y,sgt[root].dx, sgt[root].dy, sgt[root].ux, sgt[root].uy);
int midx = (sgt[root].dx+sgt[root].ux)/2;
int midy = (sgt[root].dy+sgt[root].uy)/2;
sgt[root].total += a;
if(id == 0){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(sgt[root].dx,midx,sgt[root].dy,midy);
}
insert(sgt[root].ch[id],x,y,a);
}else if(id == 1){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(sgt[root].dx,midx,midy+1,sgt[root].uy);
}
insert(sgt[root].ch[id],x,y,a);
}else if(id == 2){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(midx+1,sgt[root].ux,sgt[root].dy,midy);
}
insert(sgt[root].ch[id],x,y,a);
}else{
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(midx+1,sgt[root].ux,midy+1,sgt[root].uy);
}
insert(sgt[root].ch[id],x,y,a);
}
}
void sum(int root, int dx, int dy, int ux, int uy)
{
if(root < 0)return;
if(sgt[root].dx > ux || sgt[root].ux < dx || sgt[root].dy > uy || sgt[root].uy < dy)
return;
if(sgt[root].dx >= dx && sgt[root].ux <= ux && sgt[root].dy >= dy && sgt[root].uy <= uy)
{
ans += sgt[root].total;
return;
}else{
for(int i = 0; i < 4; i++)
{
sum(sgt[root].ch[i],dx,dy,ux,uy);
}
}
}
int main()
{
char opes[500];
char now;
int x, y, z;
int x1, x2, y1, y2;
while(scanf("%s", opes) != EOF){
now = opes[0];
getchar();
sgtn = 1;
sgt[0].total = 0;
sgt[0].dx = 1;
sgt[0].dy = 1;
sgt[0].ux = 20000;
sgt[0].uy = 20000;
for(int i = 0; i < 4; i++)
sgt[0].ch[i] = -1;
while(true){
if(now == 'E') break;
gets(opes);
if(opes[0] < '0' || opes[0] > '9'){
now = opes[0];
continue;
}
if(now == 'I'){
sscanf(opes, "%d %d %d", &x, &y, &z);
insert(0,x,y,z);
}else{
sscanf(opes, "%d %d %d %d", &x1, &x2 , &y1, &y2);
ans = 0;
sum(0,x1,y1,x2,y2);
printf("%d\n", ans);
}
}
}
return 0;
}
二維線段樹。