Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树状数组写得 帮忙看看那里做错了!!!谢谢

Posted by baolijuncool at 2012-03-10 17:05:18 on Problem 1656
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int maxn=105;

int map[maxn][maxn];
int num[maxn][maxn];
int n;
char str[10];

int lowbit(int x)
{
    return x&(-x);
}

void updata(int x,int y,int val)
{
    if(map[x][y]==val)return;
    map[x][y]=val;
    for(int i=x;i<n;i+=lowbit(i))
    {
        for(int j=y;j<n;j+=lowbit(j))
        {
            num[i][j]+=val;
        }
    }
}

int getnum(int x,int y)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=num[i][j];
        }
    }
    return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
    scanf("%d",&n);
        int x,y,l;

        memset(map,-1,sizeof(map));
        memset(num,0,sizeof(num));
        for(int s=0;s<n;s++)
        {
        scanf("%s%d%d%d",str,&x,&y,&l);
        switch(str[0])
        {

            case 'B':for(int i=x;i<x+l;i++)
            {
                for(int j=y;j<y+l;j++)
                {
                    updata(i,j,1);
                }
            }
            break;
            case 'W':for(int i=x;i<x+l;i++)
            {
                for(int j=y;j<y+l;j++)
                {
                    updata(i,j,-1);
                }
            }
            break;
            default:
            {cout<<getnum(x+l-1,y+l-1)+getnum(x-1,y-1)-getnum(x+l-1,y-1)-getnum(x-1,y+l-1)<<endl;}
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator