DLKKILL

DLKKILL's world

ZOJ - 3284 - Matrix Processing (暴力维护或者二维树状数组,模板)

题目链接:ZOJ – 3284

题目大意:

给出一个矩阵的初始数值,有三种操作。

At first, the matrix is:

1 2 3
4 5 6
7 8 9

The first command: add 1 from (1,2) to (2,2) in row order, that is, (1,2)->(1,3)->(2,1)->(2,2). The matrix becomes:

1 3 4
5 6 6
7 8 9

The second command: query (1,2), which is 3.

The third command: add 1 from (1,1) to (2,2) in column order ,that is, (1,1)->(2,1)->(3,1)->(1,2)->(2,2). The matrix becomes:

2 4 4
6 7 6
8 8 9

Then you can see (1,2) is 4 and (2,2) is 7.

题目分析:

有两种方法:

  1. 利用两个数组分别维护每一行,每一列需要加的值,不完整的一行直接加到矩阵上,查询是ans=num[i][j]+row[i]+cow[j]

  2. 利用二维树状数组维护区间值,更新区间不是一个完整的矩形,所以将矩形进行分割处理,一个大矩形减去两个小矩形。

给出代码:

方法1:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn=100+10;
long long int num[maxn][maxn];
int n,m;
long long int cow[maxn];
long long int row[maxn];
void init()
{
    memset(num,0,sizeof(num));
    memset(cow,0,sizeof(cow));
    memset(row,0,sizeof(row));
}
int main()
{
    int kase=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%lld",&num[i][j]);
            }
        }
        int q;
        scanf("%d",&q);
        printf("Case %d\n",++kase);
        while(q--)
        {
            int type;
            scanf("%d",&type);
            if(type==0)
            {
                int x1,y1,x2,y2;
                long long int k;
                scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&k);
                for(int f=x1+1;f<x2;f++)
                    row[f]+=k;
                if(x1!=x2)
                {
                    for(int f=y1;f<=m;f++)
                    num[x1][f]+=k;
                    for(int f=1;f<=y2;f++)
                    num[x2][f]+=k;
                }
                else
                {
                    for(int f=y1;f<=y2;f++)//注意在同一行的情况
                        num[x1][f]+=k;
                }
            }
            if(type==1)
            {
                 int x1,y1,x2,y2;
                long long int k;
                scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&k);
                for(int f=y1+1;f<y2;f++)
                    cow[f]+=k;
                if(y1!=y2)
                {
                    for(int f=x1;f<=n;f++)
                    num[f][y1]+=k;
                    for(int f=1;f<=x2;f++)
                    num[f][y2]+=k;
                }
                else
                {
                    for(int f=x1;f<=x2;f++)//注意在同一列的情况
                        num[f][y1]+=k;
                }
            }
            if(type==2)
            {
                int x1,y1;
                scanf("%d%d",&x1,&y1);
                long long int ans=num[x1][y1]+cow[y1]+row[x1];
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}

方法2:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn=100+10;
int nums[maxn][maxn];
int n,m;
int bit(int x)
{
    return (x&(-x));
}
void add(int x,int y,int k)
{
    if(x<=0||y<=0)
        return;
    while(x)
    {
        int i=y;
        while(i)
        {
            nums[x][i]+=k;
            i-=bit(i);
        }
        x-=bit(x);
    }
    return;
}
int sum(int x,int y)
{
    int ans=0;
    while(x<=n)
    {
        int i=y;
        while(i<=m)
        {
            ans+=nums[x][i];
            i+=bit(i);
        }
        x+=bit(x);
    }
    return ans;
}
void update(int x1,int y1,int x2,int y2,int k)
{
    if(x1>x2||y1>y2)
        return;
    add(x1-1,y1-1,k);
    add(x2,y2,k);
    add(x1-1,y2,-k);
    add(x2,y1-1,-k);
}
int main()
{
    int kase=0;
    //ios::sync_with_stdio(false);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(nums,0,sizeof(nums));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                int t;
                scanf("%d",&t);
                update(i,j,i,j,t);
            }
        }
        int q;
        scanf("%d",&q);
        printf("Case %d\n",++kase);
        while(q--)
        {
            int type;
            scanf("%d",&type);
            if(type==0)
            {
                int x1,y1,x2,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                int k;
                scanf("%d",&k);
                if(x1>x2)
                {
                    swap(x1,x2);
                    swap(y1,y2);
                }
                else if(x1==x2&&y1>y2)
                    swap(y1,y2);
                update(x1,1,x2,m,k);
                update(x1,1,x1,y1-1,-k);
                update(x2,y2+1,x2,m,-k);
            }
            else if(type==1)
            {
                int x1,y1,x2,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                int k;
                scanf("%d",&k);
                if(y1>y2)
                {
                    swap(x1,x2);
                    swap(y1,y2);
                }
                else if(y1==y2&&x1>x2)
                    swap(x1,x2);
                update(1,y1,n,y2,k);
                update(1,y1,x1 - 1,y1,-k);
                update(x2 + 1,y2,n,y2,-k);
            }
            else
            {
                int x,y;
                scanf("%d%d",&x,&y);
                int ans=sum(x,y);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注