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

  上一篇： 【轉載】上帝粒子證實存在宇宙末日來臨？（圖）

  下一篇： poj 2352 Stars 樹狀數組