题解 P3437 【[POI2006]TET-Tetris 3D】

主要内容在代码后方的注释里 主要对该题的流程进行一个梳理并对有争议的地方进行解释 并提供一个算好懂的代码吧。 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int read() { char ch=getchar();int h=0,t=1; while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();} return h*t; } const int MAXN=1010; int N,M,TT; struct Seg1//内层线段树，维护y轴 { int t[MAXN<<2],tag[MAXN<<2]; int Query(int now,int l,int r,int gl,int gr) { if(l>gr||r<gl) return -1e9; if(l>=gl&&r<=gr) return max(t[now],tag[now]);//取max int mid=(l+r)>>1,Tag=tag[now]; return max(Tag,max(Query(now<<1,l,mid,gl,gr),//标记永久化后要和祖先的tag取max Query(now<<1|1,mid+1,r,gl,gr))); } void Replace(int now,int l,int r,int gl,int gr,int k) { if(l>gr||r<gl) return; t[now]=max(t[now],k);//为了方便都取max if(l>=gl&&r<=gr) {tag[now]=max(tag[now],k);return;} int mid=(l+r)>>1; Replace(now<<1,l,mid,gl,gr,k); Replace(now<<1|1,mid+1,r,gl,gr,k); } }; struct Seg2//外层线段树，维护x轴 { Seg1 t[MAXN<<2],tag[MAXN<<2]; int Query(int now,int l,int r,int gl,int gr,int dn,int up) { if(l>gr||r<gl) return -1e9; if(l>=gl&&r<=gr) return t[now].Query(1,1,M,dn,up);//打标记的时候已经取了max，所以不用和tag取max了 int mid=(l+r)>>1,Tag=tag[now].Query(1,1,M,dn,up); return max(Tag,max(Query(now<<1,l,mid,gl,gr,dn,up),//要和祖先的tag取max Query(now<<1|1,mid+1,r,gl,gr,dn,up))); } void Replace(int now,int l,int r,int gl,int gr,int dn,int up,int k) { if(l>gr||r<gl) return; t[now].Replace(1,1,M,dn,up,k);//要把祖先的tag也更新 if(l>=gl&&r<=gr) {tag[now].Replace(1,1,M,dn,up,k);return;} int mid=(l+r)>>1; Replace(now<<1,l,mid,gl,gr,dn,up,k); Replace(now<<1|1,mid+1,r,gl,gr,dn,up,k); } }T; int main() { N=read(),M=read(),TT=read(); while(TT--) { int d=read(),s=read(),h=read(),x=read()+1,y=read()+1; h+=T.Query(1,1,N,x,x+d-1,y,y+s-1); T.Replace(1,1,N,x,x+d-1,y,y+s-1,h); } printf("%d\n",T.Query(1,1,N,1,N,1,M)); return 0; } /* 理解线段树套线段树 首先这题肯定会想到用区间覆盖标记 外层线段树表示x轴，其中每个节点又代表一棵内层线段树，内层表示y轴 为了方便，要标记永久化（你不知道下放的位置） 流程就是： St1 区间覆盖的时候要把所有的母区间的value树更新 这样可以不用pushup，value树中的value和tag都是取max 在value树中的tag处取max这个地方纠结了很久 比如说修改x轴上[3,5]的[4,6]为1 但是已经修改过[7,9]的[4,6]为8 那么在修改[1,10]的[4,6]区间时，tag已经为8了 那么不能将它改成1 因为询问是把区间卡死的，如果会询问到[1,10]中的[4,6]的tag 就说明一定会取到8这个最大值，所以都要取max St2 然后再把卡死的区间tag树更新 tag树的value和tag都是直接赋值而不是取max 但是这道题能够保证一个地方的值只会不断增大，所以为了节省代码量就和上面的操作一并写了 也就是因为这个性质，才让我以为value树中的tag也是不断增大然后删掉maxWA一片 St1 区间询问的时候不断和这个区间的Tag取最值 这样就可以过了，在取不取max上纠结了一个下午 TOT */ ```