无论是线段树还是树状数组维护最大值最小值的时候一定要注意，如果有修改操作的话，这个最小值和最大值的更新一定不能由原来的和修改的值得到，一定要重新查询一次，否则可能出现当前最小值是原来的未修改值，但事实上若修改了，此最小值不存在了。此题线段树套线段树，写的代码有点挫了。
#include<cstdio> #include<cstdlib> #include<iostream> #include<string> #include<set> #include<algorithm> #include<vector> #include<queue> #include<list> #include<cmath> #include<cstring> #include<map> #include<stack> using namespace std; #define INF 0x3f3f3f3f #define maxn 805 #define ull unsigned long long #define ll long long #define hashmod 99999839 #define mod 7 #define repe(x,y,i) for(i=x;i<=y;++i) #define repne(x,y,i) for(i=x;i<y;++i) #define MAX(x,y) (x) < (y) ? (y) : (x); #define MIN(x,y) (x) < (y) ? (x) : (y); int rson[maxn<<2][2],nex[maxn<<2],lenr,lenc,rootr; int cson[(maxn*maxn)<<2][2],mi[(maxn*maxn)<<2],ma[(maxn*maxn)<<2]; int a[maxn][maxn],n,ls,rs,fa,x,y,z; int cx,cy,rx,ry; inline void pushup(int o){ ls = cson[o][0],rs = cson[o][1]; mi[o] = MIN(mi[ls],mi[rs]); ma[o] = MAX(ma[ls],ma[rs]); } void find(int o){ int l = 1,r = n,mid = (l + r) >> 1; while(l < r){ if(mid < x) o = cson[o][1],l = mid + 1; else o = cson[o][0],r = mid; mid = (l + r) >> 1; } x = mi[o],y = ma[o]; } int buildc(int l,int r){ int o = lenc; lenc++; if(l == r){//其最小,最大值可由行树的左右子树的根指向的列树中得到 if(rx == ry) mi[o] = ma[o] = a[rx][l];//如果是同一行则直接得到 else{ mi[o] = INF,ma[o] = -1; ls = nex[rson[fa][0]],rs = nex[rson[fa][1]]; x = l,y = r; find(ls); mi[o] = MIN(mi[o],x); ma[o] = MAX(ma[o],y); x = l,y = r; find(rs); mi[o] = MIN(mi[o],x); ma[o] = MAX(ma[o],y); } cson[o][0] = cson[o][1] = -1; return o; } int mid = (l + r) >> 1; cson[o][0] = buildc(l,mid),cson[o][1] = buildc(mid+1,r),pushup(o); return o; } int buildr(int l,int r){ int o = lenr; lenr++; if(l == r){ rson[o][0] = rson[o][1] = -1,fa = o,rx = l,ry = r; nex[o] = buildc(1,n); return o; } int mid = (l + r) >> 1; rson[o][0] = buildr(l,mid),rson[o][1] = buildr(mid+1,r),fa = o,rx = l,ry = r; nex[o] = buildc(1,n); return o; } void queryc(int o,int l,int r){ if(r < cx || l > cy) return; if(l >= cx && r <= cy){x = MIN(x,mi[o]);y = MAX(y,ma[o]);return;} int mid = (l + r) >> 1; queryc(cson[o][0],l,mid),queryc(cson[o][1],mid+1,r); } void queryr(int o,int l,int r){ if(r < rx || l > ry) return; if(l >= rx && r <= ry){ queryc(nex[o],1,n);return;} int mid = (l + r) >> 1; queryr(rson[o][0],l,mid),queryr(rson[o][1],mid+1,r); } void updatec(int o,int l,int r){ if(l == r){ if(rx == ry) mi[o] = ma[o] = z; else { mi[o] = INF,ma[o] = -1; ls = nex[rson[fa][0]],rs = nex[rson[fa][1]]; int tx = x,ty = y; x = l,y = r; find(ls); mi[o] = MIN(mi[o],x); ma[o] = MAX(ma[o],y); x = l,y = r; find(rs); mi[o] = MIN(mi[o],x); ma[o] = MAX(ma[o],y); x = tx,y = ty; } return; } int mid = (l + r) >> 1; if(mid >= y) updatec(cson[o][0],l,mid); else updatec(cson[o][1],mid+1,r); pushup(o); } void updater(int o,int l,int r){ if(l == r){rx = ry = l,fa = o,updatec(nex[o],1,n);return;} int mid = (l + r) >> 1; if(mid >= x) updater(rson[o][0],l,mid); else updater(rson[o][1],mid+1,r); rx = l,ry = r,fa = o; updatec(nex[o],1,n); } int main(){ freopen("a.in","r",stdin); freopen("b.out","w",stdout); int q,t = 0,T; scanf("%d",&T); register int i,j; while(T--){ scanf("%d",&n); repe(1,n,i) repe(1,n,j) scanf("%d",&a[i][j]); lenr = lenc = 0; rootr = buildr(1,n); scanf("%d",&q); printf("Case #%d: ",++t); repe(1,q,i){ scanf("%d%d%d",&x,&y,&z); rx = x - (z>>1),cx = y - (z>>1),ry = x + (z>>1),cy = y + (z>>1); if(rx <= 0) rx = 1;if(cx <= 0) cx = 1;if(ry > n) ry = n;if(cy > n) cy = n; int tx = x,ty = y; x = INF,y = -1,queryr(rootr,1,n),z = (x + y) >> 1,printf("%d ",z); x = tx,y = ty,updater(rootr,1,n); } } return 0; }