Public feed #721911

Mine

public text v1 · immutable
Raw Edit
·published 2007-10-01 17:08 UTC
rendered paste body
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int tree[1025][1025];
int n;

void update(int x , int y , int val){
	int y1;
	while (x <= n){
		y1 = y;
		while (y1 <= n){
			tree[x][y1] += val;
			y1 += (y1 & -y1); 
		}
		x += (x & -x); 
	}
}

int read(int idx,int indx1){
	int sum = 0;
	while (idx > 0){
		int x=indx1;
		while(x>0)
		{
		sum += tree[idx][x];
		x-=(x&-x);
		}
		idx -= (idx & -idx);
	}
	return sum;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);

		memset(tree,0,sizeof(tree));

		char cmd[100];

		int x1,x2,y1,y2,x,y,val;

		while(1)
		{
			scanf("%s",cmd);
			if(!strcmp(cmd,"END")) break;

			if(!strcmp(cmd,"SET"))
			{
				scanf("%d %d %d",&x,&y,&val);
				x++;
				y++;
				int t=read(x,y);
				update(x,y,-t);
				update(x,y,val);				
			}
			else
			{
				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
				x1++;x2++;y1++;y2++;
				int val1,val2,val3,val4;
				val1=read(x2,y2);
				val2=read(x2,y1);
				val3=read(x1,y2);
				val4=read(x1,y1);
				printf("%d\n",val1-val2-val3+val4);
			}
		}

	}

	return 0;
}