hdu 1890 二维树状数组


#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int sum[1010][1010];
int mark[1010][1010];
int add(int a,int b,int c)
{
    int i,j;
    for(i=a;i<=1001;i+=(i&-i))
    for(j=b;j<=1001;j+=(j&-j))
    sum[i][j]+=c;
    return 0;    
}
int find(int a,int b)
{
    int i,j,s=0;
    for(i=a;i>0;i-=(i&-i))
    for(j=b;j>0;j-=(j&-j))
    s+=sum[i][j];
    return s;
}
int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    int i,j,T,Q;
    int a1,a2,b1,b2,n,d=1;
    char str[5];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&Q);
        printf("Case %d:\n",d++);
        memset(sum,0,sizeof(sum));
        for(i=1;i<=1001;i++)
        for(j=1;j<=1001;j++)
        {
            mark[i][j]=1;
            add(i,j,1);
        }
        while(Q--)
        {
            scanf("%s",str);
            if(str[0]==‘S‘)
            {
                scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
                a1++;a2++;b1++;b2++;
                int k1=max(a1,a2);
                int k2=min(a1,a2);
                int t1=max(b1,b2);
                int t2=min(b1,b2);
                int s1=find(k1,t1);
                int s2=find(k1,t2-1);
                int s3=find(k2-1,t1);
                int s4=find(k2-1,t2-1);
                printf("%d\n",s1-s2-s3+s4);
            }
            else if(str[0]==‘A‘)
            {
                scanf("%d%d%d",&a1,&b1,&n);
                a1++;b1++;
                add(a1,b1,n);
                mark[a1][b1]+=n;
            }
            else if(str[0]==‘D‘)
            {
                scanf("%d%d%d",&a1,&b1,&n);
                a1++;b1++;
                int step=mark[a1][b1]>n?n:mark[a1][b1];
                add(a1,b1,-step);
                mark[a1][b1]-=step;
            }
            else 
            {
                scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&n);
                a1++;a2++;b1++;b2++;
                int step=mark[a1][b1]>n?n:mark[a1][b1];
                add(a1,b1,-step);
                add(a2,b2,step);
                mark[a1][b1]-=step;
                mark[a2][b2]+=step;
            }
        }
    }
    return 0;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。