樹狀數組，inc(x,y)表示對[x-n][y-n]的區域執行一次反轉操作，這樣，getsum(x,y)將總會包含對[x][y]的操作，即為[x][y]的反轉總次數，根據奇偶性判斷當前狀態。
#?include?<stdio.h>
#?include?<string.h>
#?define?N?1005
int?n,?c[N][N];
void?clr(int?nn)
{
????????????????int?i;
????????????????for?(i?=?1;?i?<=?nn;?++i)
????????????????????????????????memset(c[i]+1,?0,?sizeof(c[0][0])*nn);
}
/******************************************************************/
void?inc(int?x,?int?y)
{
????????????????int?t;
????????????????while?(x?<=?n)
????????????????{
????????????????????????????????t?=?y;
????????????????????????????????while?(t?<=?n)?++?c[x][t],?t?+=?t&(-t);//?printf("%d\n",?t);
????????????????????????????????x?+=?x&(-x);
????????????????}
}
int?getsum(int?x,?int?y)
{
????????????????int?t,?ret?=?0;
????????????????while?(x?>?0)
????????????????{
????????????????????????????????t?=?y;
????????????????????????????????while?(t?>?0)?ret?+=?c[x][t],?t?-=?t&(-t);//?printf("%d\n",?t);
????????????????????????????????x?-=?x&(-x);
????????????????}
????????????????return?ret;
}
/******************************************************************/
int?main()
{
????????????????char?ins[3];
????????????????int?X,?T,?x0,?y0,?x1,?y1;
????????????????scanf("%d",?&X);
????????????????while?(X--)
????????????????{
????????????????????????????????scanf("%d%d",?&n,?&T),?clr(n);
????????????????????????????????while?(T--)
????????????????????????????????{
????????????????????????????????????????????????scanf("%s%d%d",?ins,?&x0,?&y0);
????????????????????????????????????????????????switch(ins[0])
????????????????????????????????????????????????{
????????????????????????????????????????????????????????????????case?'C':
????????????????????????????????????????????????????????????????{
????????????????????????????????????????????????????????????????????????????????scanf("%d%d",?&x1,?&y1);
????????????????????????????????????????????????????????????????????????????????inc(x0,?y0);
????????????????????????????????????????????????????????????????????????????????inc(x0,?y1+1);
????????????????????????????????????????????????????????????????????????????????inc(x1+1,?y0);
????????????????????????????????????????????????????????????????????????????????inc(x1+1,?y1+1);
????????????????????????????????????????????????????????????????????????????????break;
????????????????????????????????????????????????????????????????}
????????????????????????????????????????????????????????????????case?'Q':?puts((getsum(x0,?y0)&0x1)???"1":"0");?break;
????????????????????????????????????????????????}
????????????????????????????????}
????????????????????????????????if?(X)?putchar('\n');
????????????????}
????????????????return?0;
}
posted on 2012-09-02 17:29
yajunw 閱讀(154)
評論(0) 編輯 收藏 引用