当前位置: 首页 > article >正文

题解:SP1741 TETRIS3D - Tetris 3D

这是一道二维线段树(树套树)+标记永久化的模版题

前置知识点(来自董晓算法)

好,现在开始我们的分析:

题意简述:

在一个二维平面内,有给定的坐标,在这个坐标范围内加上这个物品的厚度。最后输出不超过极限的最高坐标。

解法分析:

由于看到了区间修改,所以第一时间想到了线段树。(好像树状数组也可以做,只是本人不会)但是,要注意到这是一个二维线区间修改,所以要引入一种新的东西:二维线段树(什么!你还没有点开前置知识点?!快去看看!)

因为有董晓老师对于二维线段树的详细讲解了,我在这里就不过多赘述。

发现问题:

对于内层而言,传统的做法可以胜任,可以打 lazy 标记,pushdown 和 pushup 也都是可以进行的。但是对于外层而言,信息量太大,无法进行,所以需要使用一种新办法:标记永久化

知识点,标记永久化

好了,问题到这就已经解决了,直接上代码吧。(四十几行真的不长了QAQ)

#include<iostream>
#include<cstring>
#include<algorithm>
#define ls(x) x*2
#define rs(x) x*2+1
#define mid l+(r-l)/2
using namespace std;
const int MAXN=4e3+10;
int d,s,n;
int a,b,h,x,y;
struct segy{
    int mx[MAXN],tag[MAXN];
    void change(int u,int l,int r,int y1,int y2,int h){
        mx[u]=max(mx[u],h);
        if(y1<=l&&r<=y2){tag[u]=max(tag[u],h);return ;}
        if(y1<=mid)change(ls(u),l,mid,y1,y2,h);
        if(y2>mid)change(rs(u),mid+1,r,y1,y2,h);
    }
    int query(int u,int l,int r,int y1,int y2){
        if(y1<=l&&r<=y2)return mx[u];
        int ans=tag[u];
        if(y1<=mid)ans=max(ans,query(ls(u),l,mid,y1,y2));
        if(y2>mid)ans=max(ans,query(rs(u),mid+1,r,y1,y2));
        return ans;
    }
}mx[MAXN],tag[MAXN];
void change(int u,int l,int r,int x1,int x2,int y1,int y2,int h){
    mx[u].change(1,1,s,y1,y2,h);
    if(x1<=l&&r<=x2){tag[u].change(1,1,s,y1,y2,h);return ;}
    if(x1<=mid)change(ls(u),l,mid,x1,x2,y1,y2,h);
    if(x2>mid)change(rs(u),mid+1,r,x1,x2,y1,y2,h);
}
int query(int u,int l,int r,int x1,int x2,int y1,int y2){
    if(x1<=l&&r<=x2)return mx[u].query(1,1,s,y1,y2);
    int ans=tag[u].query(1,1,s,y1,y2);
    if(x1<=mid)ans=max(ans,query(ls(u),l,mid,x1,x2,y1,y2));
    if(x2>mid)ans=max(ans,query(rs(u),mid+1,r,x1,x2,y1,y2));
    return ans;
}
int main(){
    cin>>d>>s>>n;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>h>>x>>y;x++;y++;
        h+=query(1,1,d,x,x+a-1,y,y+b-1);
        change(1,1,d,x,x+a-1,y,y+b-1,h);
    }
    cout<<mx[1].mx[1]<<"\n";
    return 0;
}

http://www.kler.cn/news/335530.html

相关文章:

  • AVL树的实现
  • 【LeetCode-热题100-128题】官方题解好像有误
  • Django学习笔记五:templates使用详解
  • 二叉搜索树(c++版)
  • No module named ‘_ssl‘
  • 通信工程学习:什么是B/S浏览器服务器模式
  • 内网穿透工具ngrok
  • 彻底释放服务器空间:多用户环境下Anaconda共享与优化指南
  • YOLOv7改进:Unified-loU,用于高品质目标检测的统一loU ,2024年8月最新IoU
  • 【颜色平衡树 / E】
  • 【ubuntu】Ubuntu20.04安装中文百度输入法
  • 力扣刷题 | 两数之和
  • web网页项目--用户登录,注册页面代码
  • Flink源码剖析
  • 统计方形(暴力枚举)
  • sql-server【bcp工具】
  • 20.1 分析pull模型在k8s中的应用,对比push模型
  • redis+mysql数据一致性+缓存穿透解决方案
  • Python知识点:如何使用SpaCy进行文本预处理与分析
  • Python知识点:如何使用Multiprocessing进行并行任务管理