293
技術社區[雲棲]
poj 2155 Matrix 二維樹狀數組
經典題，把一個-=寫成=-了查了半天都沒查出來……
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int n;
int sum[1005][1005];
inline int low(int x)
{
return x&-x;
}
void update(int x,int y,int num)
{
int Y=y;
while(x<=n)
{
y=Y;
while(y<=n)
{
sum[x][y]+=num;
y+=low(y);
}
x+=low(x);
}
}
int query(int x,int y)
{
int Y=y,ans=0;
while(x>0)
{
y=Y;
while(y>0)
{
ans+=sum[x][y];
y-=low(y);
}
x-=low(x);
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
int q;
while(T--)
{
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&q);
int a,b,c,d;
while(q--)
{
getchar();
switch(getchar())
{
case 'C':
scanf("%d%d%d%d",&a,&b,&c,&d);
c++;d++;
update(a,b,1);
update(a,d,-1);
update(c,b,-1);
update(c,d,1);
break;
case 'Q':
scanf("%d%d",&a,&b);
printf("%d\n",query(a,b)&1);
break;
}
}
puts("");
}
}
最後更新：2017-04-03 16:48:46