学步园

这个题写了很久，之前用四分树做了，只get到了WA和RE，转投二维线段树。

题目本身描述不对！明明是N X M的矩阵写了N X N。。。一直没看出来。。

然后，矩阵尺寸定义的变量名为m，平均值也定义为m，又是一直没看出来，debug了一个下午，一个字母一个字母调才找出来，sad。。。

果然我还是太弱了。。。

模板：

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 2010
#define INF (1 << 30)
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define max(a, b) (a > b ? a : b);
#define min(a, b) (a < b ? a : b);

int mm[MAXN][MAXN], maxp[MAXN][MAXN], minp[MAXN][MAXN];
int N, M, q;
int Lx, Rx, Ly, Ry, px, py, v, flag;
int maxv, minv;
char op[4];

void build1D(int rx, int x, int l, int r, int rt)
{
    if(l == r)
    {
        maxp[rx][rt] = minp[rx][rt] = mm[x][l];
        return ;
    }
    int m = (l + r) >> 1;
    build1D(rx, x, lson);
    build1D(rx, x, rson);
    maxp[rx][rt] = max(maxp[rx][rt << 1], maxp[rx][rt << 1 | 1]);
    minp[rx][rt] = min(minp[rx][rt << 1], minp[rx][rt << 1 | 1]);
}

void build2D(int l = 1, int r = N, int rt = 1)
{
    if(l == r)
    {
        build1D(rt, l, 1, M, 1);
        return ;
    }
    int m = (l + r) >> 1;
    build2D(lson);
    build2D(rson);
    for(int i = 1; i <= M * 4; i++)
    {
        maxp[rt][i] = max(maxp[rt << 1][i], maxp[rt << 1 | 1][i]);
        minp[rt][i] = min(minp[rt << 1][i], minp[rt << 1 | 1][i]);
    }
}

void update1D(int rx, int l, int r, int rt)
{
    if(l == r)
    {
        if(flag) { maxp[rx][rt] = minp[rx][rt] = v; return; }
        maxp[rx][rt] = max(maxp[rx << 1][rt], maxp[rx << 1 | 1][rt]);
        minp[rx][rt] = min(minp[rx << 1][rt], minp[rx << 1 | 1][rt]);
        return ;
    }
    int m = (l + r) >> 1;
    if(py <= m) update1D(rx, lson);
    if(py >  m) update1D(rx, rson);
    maxp[rx][rt] = max(maxp[rx][rt << 1], maxp[rx][rt << 1 | 1]);
    minp[rx][rt] = min(minp[rx][rt << 1], minp[rx][rt << 1 | 1]);
}

void update2D(int l = 1, int r = N, int rt = 1)
{
    if(l == r) { flag = 1; update1D(rt, 1, M, 1); return;}
    int m = (l + r) >> 1;
    if(px <= m) update2D(lson);
    if(px >  m) update2D(rson);
    flag = 0; update1D(rt, 1, M, 1);
}

void query1D(int rx, int l, int r, int rt)
{
    if(Ly <= l && r <= Ry)
    {
        maxv = max(maxp[rx][rt], maxv);
        minv = min(minp[rx][rt], minv);
        return ;
    }
    int m = (l + r) >> 1;
    if(Ly <= m) query1D(rx, lson);
    if(Ry >  m) query1D(rx, rson);
}

void query2D(int l = 1, int r = N, int rt = 1)
{
    if(Lx <= l && r <= Rx)
    {
        query1D(rt, 1, M, 1);
        return ;
    }
    int m = (l + r) >> 1;
    if(Lx <= m) query2D(lson);
    if(Rx >  m) query2D(rson);
}

void put1D(int rx, int x, int l, int r, int rt)
{
    if(l == r)
    {
        cout << x << ' ' << l << ": " << maxp[rx][rt] << ' ' << minp[rx][rt] << endl;
        return ;
    }
    int m = (l + r) >> 1;
    put1D(rx, x, lson);
    put1D(rx, x, rson);
}

void put2D(int l = 1, int r = N, int rt = 1)
{
    if(l == r)
    {
        put1D(rt, l, 1, M, 1);
        return ;
    }
    int m = (l + r) >> 1;
    put2D(lson);
    put2D(rson);
}

int main()
{
//    freopen("UVa_11297.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) scanf("%d", &mm[i][j]);

    build2D();
//    put2D();

    scanf("%d", &q);
    while(q--)
    {
        scanf("%s", op);
        if(op[0] == 'q')
        {
            scanf("%d%d%d%d", &Lx, &Ly, &Rx, &Ry);
            maxv = -INF; minv = INF;
            query2D();
            printf("%d %d\n", maxv, minv);
        }
        if(op[0] == 'c')
        {
            scanf("%d%d%d", &px, &py, &v);
            update2D();
        }
    }

    return 0;
}