Matrix Processing ZOJ - 3284

线段树

题目描述：看题吧，题目说的很清晰。

解题分析：这个题同学用标记瞎搞的方法就过了，网上有人用二维树状数组做的，在这写一个线段树的写法。具体是定义两个线段树，一个只管行更新，一个只管列更新，每次更新的时候是一段线性的区间。查询就是两个线段树的查询和再加上矩阵元素本身。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 10000 + 10;
struct Node
{
    int l,r;
    int sum,add;
}P[maxn*4],Q[maxn*4];
int Mat[110][110];
int n,m,q;

void pushup(Node* T,int pos)
{
    T[pos].sum = T[pos << 1].sum + T[pos << 1 | 1].sum;
}

void build(Node* T, int l,int r,int pos)
{
    T[pos].l = l;
    T[pos].r = r;
    T[pos].sum = 0;
    T[pos].add = 0;
    if(l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    build(T,l,mid,pos << 1);
    build(T,mid + 1,r,pos << 1 | 1);
}

void pushdown(Node* T , int pos)
{
    if(T[pos].add != 0)
    {
        T[pos << 1].add += T[pos].add;
        T[pos << 1 | 1].add += T[pos].add;
        T[pos << 1].sum += (T[pos << 1].r - T[pos << 1].l + 1) * T[pos].add;
        T[pos << 1 | 1].sum += ( T[pos << 1 | 1].r - T[pos << 1 | 1].l + 1) * T[pos].add;
        T[pos].add = 0;
    }
}

void update(Node*T ,int L,int R,int pos,int val)
{
    if(L <= T[pos].l && T[pos].r <= R)
    {
        T[pos].sum += (T[pos].r - T[pos].l + 1) * val;
        T[pos].add += val;
        return;
    }
    int mid = (T[pos].l + T[pos].r) / 2;
    pushdown(T,pos);
    if(L <= mid) update(T,L,R,pos << 1,val);
    if(mid < R) update(T,L,R,pos << 1 | 1 , val);
    pushup(T,pos);
}

int query(Node* T,int loc,int pos)
{
    if(T[pos].l == T[pos].r)
    {
        return T[pos].sum;
    }
    int mid = (T[pos].l + T[pos].r) / 2;
    pushdown(T , pos);
    if(loc <= mid) return query(T,loc,pos << 1);
    else return  query(T,loc,pos << 1 | 1);
}

int main()
{
    int kase = 0;
    while(scanf("%d %d",&n,&m) == 2)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                scanf("%d",&Mat[i][j]);
            }
        }
        build(P, 1 , n * m, 1);
        build(Q, 1 , n * m, 1);
        printf("Case %d\n",++kase);
        scanf("%d",&q);
        while(q--)
        {
            int type,r1,c1,r2,c2,k;
            scanf("%d",&type);
            if(type == 0)
            {
                scanf("%d %d %d %d %d",&r1,&c1,&r2,&c2,&k);
                int l = (r1 - 1) * m + c1, r = (r2 - 1) * m + c2;//注意不要把n,m乘错了，之前的错误代码是int l = (r1 - 1) * n + c1, r = (r2 - 1) * n + c2;
                update(P , l, r, 1, k);
            }
            else if(type == 1)
            {
                scanf("%d %d %d %d %d",&r1,&c1,&r2,&c2,&k);
                int l = (c1 - 1) * n + r1 , r =  (c2 - 1) * n + r2;//注意不要把n,m乘错了，之前的错误代码是int l = (c1 - 1) * m + r1 , r =  (c2 - 1) * m + r2;
                update(Q, l, r, 1 , k);
            }
            else if(type == 2)
            {
                scanf("%d %d",&r1,&c1);
                int ans = query( P,(r1 - 1) * m + c1, 1) + query( Q, (c1 - 1) * n + r1, 1) + Mat[r1][c1];
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

段错误搞得我发毛，一直不知道错在哪，最后发现，原来是行和列又乘反了，多次被这个个地方坑，老是把二维数组的行和列与几何中的坐标轴的x,y弄混，对于这个地方还是得多注意啊。