1. 题目

传送门=￣ω￣=

题意：
给定一个 N×N 的矩阵，再给 M 个询问，询问以 x,y 为中心，边长为 l 的正方形区域内的最大值和最小值的平均值，并且把点 x,y 的值改为这个平均值

有多组数据

2. 题解

二维线段树模板题

真是写死我了

线段树套线段树即可

代码：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define mkp make_pair
using namespace std;
typedef pair<int,int> pii;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();int f=1;dig=0;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    dig*=f;
}
int t,n,m;
struct N2{int l,r,min,max;};
struct N1{int l,r;N2 d[3205];}e[3205];
void update(int a,int b)
{
    e[a].d[b].max=max(e[a].d[LS(b)].max,e[a].d[RS(b)].max);
    e[a].d[b].min=min(e[a].d[LS(b)].min,e[a].d[RS(b)].min);
}
void build2(int l,int r,int a,int b)
{
    N2&k=e[a].d[b];
    k.l=l,k.r=r,k.max=INT_MIN,k.min=INT_MAX;
    if(l==r)return;
    build2(l,(l+r)>>1,a,LS(b)),build2(((l+r)>>1)+1,r,a,RS(b));
}
void build1(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    build2(1,n,a,1);
    if(l==r)return;
    build1(l,(l+r)>>1,LS(a)),build1(((l+r)>>1)+1,r,RS(a));
}
void change2(int x,int a,int b)
{
    if(e[a].l==e[a].r)return;
    e[a].d[b].max=max(e[LS(a)].d[b].max,e[RS(a)].d[b].max);
    e[a].d[b].min=min(e[LS(a)].d[b].min,e[RS(a)].d[b].min);
    if(e[a].d[b].l==e[a].d[b].r)return;
    if(x<=((e[a].d[b].l+e[a].d[b].r)>>1))change2(x,a,LS(b));
    else change2(x,a,RS(b));
}
void change(int x,int y,int k,int a)
{
    if(e[a].l==e[a].r)
    {
        int i=1;
        while(e[a].d[i].l!=e[a].d[i].r)
            if(x<=((e[a].d[i].l+e[a].d[i].r)>>1))i=LS(i);
            else i=RS(i);
        e[a].d[i].min=e[a].d[i].max=k;
        while(i>>=1)update(a,i);
    }
    else
        if(y<=((e[a].l+e[a].r)>>1))change(x,y,k,LS(a));
        else change(x,y,k,RS(a));
    change2(x,a,1);
}
pii query2(int l,int r,int a,int b)
{
    N2&k=e[a].d[b];
    if(l<=k.l&&k.r<=r)return mkp(k.min,k.max);
    pii tot=mkp(INT_MAX,INT_MIN),tmp;
    if(l<=((k.l+k.r)>>1))
        tmp=query2(l,r,a,LS(b)),
        tot.first=min(tot.first,tmp.first),
        tot.second=max(tot.second,tmp.second);
    if(r>((k.l+k.r)>>1))
        tmp=query2(l,r,a,RS(b)),
        tot.first=min(tot.first,tmp.first),
        tot.second=max(tot.second,tmp.second);
    return tot;
}
pii query(int x1,int x2,int y1,int y2,int a)
{
    if(y1<=e[a].l&&e[a].r<=y2)return query2(x1,x2,a,1);
    pii tot=mkp(INT_MAX,INT_MIN),tmp;
    if(y1<=((e[a].l+e[a].r)>>1))
        tmp=query(x1,x2,y1,y2,LS(a)),
        tot.first=min(tot.first,tmp.first),
        tot.second=max(tot.second,tmp.second);
    if(y2>((e[a].l+e[a].r)>>1))
        tmp=query(x1,x2,y1,y2,RS(a)),
        tot.first=min(tot.first,tmp.first),
        tot.second=max(tot.second,tmp.second);
    return tot;
}
int main()
{
    IN(t);
    for(int cnt=1;cnt<=t;cnt++)
    {
        printf("Case #%d:\n",cnt);
        IN(n),build1(1,n,1);
        for(int i=1,a;i<=n;i++)for(int j=1;j<=n;j++)IN(a),change(i,j,a,1);
        IN(m);
        for(int i=1,a,b,c;i<=m;i++)
        {
            IN(a),IN(b),IN(c),c>>=1;
            pii d=query(max(a-c,0),min(a+c,n),max(b-c,0),min(b+c,n),1);
            printf("%d\n",(d.second+d.first)>>1);
            change(a,b,(d.second+d.first)>>1,1);
        }
    }
    return 0;
}