题解 P3437 【[POI2006]TET-Tetris 3D】
xzyxzy
2018-04-04 18:39:17
主要内容在代码后方的注释里
主要对该题的流程进行一个梳理并对有争议的地方进行解释
并提供一个算好懂的代码吧。
```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
*/
```