1336 : Matrix Sum (hihocoder)

二维树状数组,百度一大堆,我只是存代码的

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<string>

using namespace std;

typedef long long int LL;

const int INF=2e9+1e8;

const int MM=1010;

const LL MOD=1e9+7;

LL n,m,bitnum[MM][MM];

LL lowbit(LL x)

{

    return x&(-x);

}

void add(LL xx,LL yy,LL num)

{

    for(int x=xx;x<=n+1;x+=lowbit(x))

    {

        for(int y=yy;y<=n+1;y+=lowbit(y))

        {

            bitnum[x][y]+=num;

        }

    }

}

LL sum(LL l,LL r)

{

    LL ans=0;

    for(int x=l;x>0;x-=lowbit(x))

    {

        for(int y=r;y>0;y-=lowbit(y))

        {

            ans+=(bitnum[x][y])%MOD;

        }

    }

    return ans%MOD;

}

LL getsum(LL x1,LL y1,LL x2,LL y2)

{

    LL ans=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);

    while(ans<0) ans+=MOD;

    return ans;

}

int main()

{

    memset(bitnum,0,sizeof(bitnum));

    cin>>n>>m;

    for(int i=0;i<m;i++)

    {

        char opt[10];

        LL x1,y1,x2,y2,val;

        cin>>opt;

        if(opt[0]=='A')

        {

            cin>>x1>>y1>>val;

            add(x1+1,y1+1,val);

        }

        else

        {

            cin>>x1>>y1>>x2>>y2;

            cout<<getsum(x1+1,y1+1,x2+1,y2+1)<<endl;

        }

    }

        return 0;

}

巴特西

1336 : Matrix Sum (hihocoder)

最新文章

热门文章