Mosaic

#include <bits/stdc++.h>
using namespace std;
const int N = 810;
struct SNode {
    int l;
    int r;
    int max;
    int min;
    int getmid() {
        return l + r >> 1;
    }
};

struct tree {
    int l;
    int r;
    SNode t[N << 2];
    int getmid() {
        return l + r >> 1;
    }
}t[N << 2];
int n, m, a[N][N];

void buildY(int l, int r, int p2, int p, int flag)//flag = 1作区间更新，否则仅赋值
{
    t[p].t[p2].l = l;
    t[p].t[p2].r = r;
    if(l == r)
    {
        if(flag) {
            t[p].t[p2].max = max(t[p * 2].t[p2].max, t[p * 2 + 1].t[p2].max);
            t[p].t[p2].min = min(t[p * 2].t[p2].min, t[p * 2 + 1].t[p2].min);
        }
        else
            t[p].t[p2].min = t[p].t[p2].max = a[t[p].l][l];
        return;
    }
    int mid = l + r >> 1;
    buildY(l, mid, p2 * 2, p, flag);
    buildY(mid + 1, r, p2 * 2 + 1, p, flag);
    t[p].t[p2].max = max(t[p].t[p2 * 2].max,t[p].t[p2 * 2 + 1].max);
    t[p].t[p2].min = min(t[p].t[p2 * 2].min,t[p].t[p2 * 2 + 1].min);
}

void buildX(int l, int r, int p2)
{
    t[p2].l = l;
    t[p2].r = r;
    if(l == r)
    {
        buildY(1, n, 1, p2, 0); 
        return;
    }
    int mid = t[p2].getmid();
    buildX(l, mid, p2 * 2);
    buildX(mid + 1, r, p2 * 2 + 1);
    buildY(1, n, 1, p2, 1);
}

int QueryMaxY(int l, int r, int p2, int p)
{
    if(t[p].t[p2].l == l && t[p].t[p2].r == r)
        return t[p].t[p2].max;
    int mid = t[p].t[p2].getmid();
    if(r <= mid)
        return QueryMaxY(l, r, p2 * 2, p);
    else if(l > mid)
        return QueryMaxY(l, r, p2 * 2 + 1, p);
    else
        return max(QueryMaxY(l, mid, p2 * 2, p), QueryMaxY(mid + 1, r, p2 * 2 + 1, p));
}

int QueryMaxX(int l, int r, int x, int y, int p2)
{
    if(t[p2].l == l && t[p2].r == r)
        return QueryMaxY(x, y, 1, p2);
    int mid = (t[p2].l + t[p2].r) >> 1;
    if(r <= mid)
        return QueryMaxX(l, r, x, y, p2 * 2);
    else if(l > mid)
        return QueryMaxX(l, r, x, y, p2 * 2 + 1);
    else
        return max(QueryMaxX(l, mid, x, y, p2 * 2), QueryMaxX(mid + 1, r, x, y, p2 * 2 + 1));
}

int QueryMinY(int l, int r, int p2, int p)
{
    if(t[p2].l == l&&t[p2].r == r)
        return t[p].t[p2].min;
    int mid = (t[p].t[p2].l + t[p].t[p2].r) >> 1;
    if(r <= mid)
        return QueryMinY(l, r, p2 * 2, p);
    else if(l > mid)
        return QueryMinY(l, r, p2 * 2 + 1, p);
    else
        return min(QueryMinY(l, mid, p2 * 2, p), QueryMinY(mid + 1, r, p2 * 2 + 1, p));
}

int QueryMinX(int l,int r,int x,int y,int p2)
{
    if(t[p2].l == l && t[p2].r == r)
        return QueryMinY(x, y, 1, p2);
    int mid = (t[p2].l + t[p2].r) >> 1;
    if(r <= mid)
        return QueryMinX(l, r, x, y, p2 * 2);
    else if(l > mid)
        return QueryMinX(l, r, x, y, p2 * 2 + 1);
    else
        return min(QueryMinX(l, mid, x, y, p2 * 2), QueryMinX(mid + 1, r, x, y, p2 * 2 + 1));
}

void changeY(int y, int p2, int val, int p, int flag)
{
    if(t[p].t[p2].l == t[p].t[p2].r)
    {
        if(!flag)
            t[p].t[p2].min = t[p].t[p2].max = val;
        else
        {
            t[p].t[p2].min = min(t[p * 2].t[p2].min, t[p * 2 + 1].t[p2].min);
            t[p].t[p2].max = max(t[p * 2].t[p2].max, t[p * 2 + 1].t[p2].max);
        }
        return;
    }    
    int mid = (t[p].t[p2].l + t[p].t[p2].r) >> 1;
    if(y <= mid)
        changeY(y, p2 * 2, val, p, flag);
    else
        changeY(y, p2 * 2 + 1, val, p, flag);
    t[p].t[p2].max = max(t[p].t[p2 * 2].max, t[p].t[p2 * 2 + 1].max);
    t[p].t[p2].min = min(t[p].t[p2 * 2].min, t[p].t[p2 * 2 + 1].min);
}

void changeX(int x, int y, int p2, int val)
{
    if(t[p2].l == t[p2].r)
    {
        changeY(y, 1, val, p2, 0);
        return;
    }
    int mid = (t[p2].l + t[p2].r) >> 1;
    if(x <= mid)
        changeX(x, y, p2 * 2, val);
    else
        changeX(x, y, p2 * 2 + 1,val);
    changeY(y, 1, val, p2, 1);
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                cin >> a[i][j];
        buildX(1, n, 1);
        cin >> m;
        while(m--)
        {
            int x, y, l;
            cin >> x >> y >> l;
            int sx = max(1, x - l / 2);
            int sy = max(1, y - l / 2);
            int mx = min(n, x + l / 2);
            int my = min(n, y + l / 2);
            int max = QueryMaxX(sx, mx, sy, my, 1);
            int min = QueryMinX(sx, mx, sy, my, 1);
            cout << (max + min) / 2;
            changeX(x, y, 1, (max + min) >> 1);
        }
    }
    return 0;
}