P4560 [IOI2014] Wall 砖墙

*原题链接*

做法:线段树

一道比较基础的线段树练手题,区间赋值,在修改时加些判断剪枝。

对于add操作,如果此时区间里的最小值都大于等于h的话,就没必要操作,如果最大值都小于h的话,就直接区间赋值为h。对于remove操作同理。

时间复杂度大致为O(nlogn),实际会比这个要大一些。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,INF=0x3f3f3f3f;

int n,k;

struct node{
	int l,r;
	int mn,mx,tag;
}tr[N*4];

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-1') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}

void pushdown(int u){
	if(tr[u].tag==INF) return;
	tr[u<<1].mn=tr[u<<1].mx=tr[u<<1].tag=tr[u].tag;
	tr[u<<1|1].mn=tr[u<<1|1].mx=tr[u<<1|1].tag=tr[u].tag;
	tr[u].tag=INF;
}

void pushup(int u){
	tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
	tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}

void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,0,0,INF};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=(l+r)>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify1(int u,int l,int r,int x){//Add
	if(tr[u].l>=l&&tr[u].r<=r){
		if(tr[u].mn>=x) return;
		if(tr[u].mx<=x){
			tr[u].mn=tr[u].mx=tr[u].tag=x;
			return;
		}
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid) modify1(u<<1,l,r,x);
	if(r>mid) modify1(u<<1|1,l,r,x);
	pushup(u);
}

void modify2(int u,int l,int r,int x){//Remove
	if(tr[u].l>=l&&tr[u].r<=r){
		if(tr[u].mx<=x) return;
		if(tr[u].mn>=x){
			tr[u].mn=tr[u].mx=tr[u].tag=x;
			return;
		}
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid) modify2(u<<1,l,r,x);
	if(r>mid) modify2(u<<1|1,l,r,x);
	pushup(u);
}

int query(int u,int x){
	if(tr[u].l==x&&tr[u].r==x) return tr[u].mx;
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid) return query(u<<1,x);
	return query(u<<1|1,x);
}

int main(){
	
	n=read(),k=read();
	build(1,1,n);
	while(k--){
		int opt=read(),l=read(),r=read(),h=read();
		l++,r++;
		if(opt==1) modify1(1,l,r,h);
		else modify2(1,l,r,h);
	}
	for(int i=1;i<=n;i++) cout<<query(1,i)<<endl;
	
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/872498.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

坐牢第三十五天(c++)

一.作业 1.使用模版类自定义栈 代码&#xff1a; #include <iostream> using namespace std; template<typename T> // 封装一个栈 class stcak { private:T *data; //int max_size; // 最大容量int top; // 下标 public:// 无参构造函数stcak();// 有参…

【全志H616】【开源】 ARM-Linux 智能分拣项目:阿里云、网络编程、图像识别

【全志H616】【开源】 ARM-Linux 智能分拣项目&#xff1a;阿里云、网络编程、图像识 文章目录 【全志H616】【开源】 ARM-Linux 智能分拣项目&#xff1a;阿里云、网络编程、图像识1、实现功能2、软件及所需环境3、逻辑流程图及简述3.1 完整逻辑流程图3.2 硬件接线3.3 功能简述…

部署project_exam_system项目——及容器的编排

&#xff08;一&#xff09;安装docker、编辑daemon.json文件、安装docker-compose编排容器、启动docker 1.环境准备 [rootdocker--1 ~]# rz -Erz waiting to receive.[rootdocker--1 ~]# lsanaconda-ks.cfg docker.sh[rootdocker--1 ~]# source docker.sh [rootdocker--1 ~…

基于Flink的流式计算可视化开发实践之配置->任务生成->任务部署过程

1. 引言 在我们大数据平台(XSailboat)的DataStudio模块中实现了基于Hive的业务流程开发和基于Flink的实时计算管道开发。 DataStudio是用来进行数据开发的&#xff0c;属于开发环境&#xff0c;另外还有任务运维模块&#xff0c;负责离线分析任务和实时计算任务在生产环境的部…

30岁程序员的焦虑:转行还是继续死磕?现在什么方向更有前景?

最适合转入AI大模型的莫过于程序员和在读大学生了吧。 对于程序员来说&#xff0c;码农之路并不是一帆风顺。对于每一个入行IT业的社会青年来说&#xff0c;谁不是抱着想要成为最高峰的技术大咖或者跃进管理岗的小目标&#xff1f; 然而往往更多的人并非互联网吹捧的如此耀眼…

低代码平台:加速企业制造业数字化转型的新引擎

近期&#xff0c;国家发布了中小企业数字化转型试点城市的政策&#xff0c;旨在通过先行先试&#xff0c;探索支持制造业特别是汽车制造行业数字化转型的有效模式。这一政策的出台&#xff0c;为汽车制造企业的数字化转型提供了强有力的政策支持和方向指引&#xff0c;标志着汽…

【论文速读】| SEAS:大语言模型的自进化对抗性安全优化

本次分享论文&#xff1a;SEAS: Self-Evolving Adversarial Safety Optimization for Large Language Models 基本信息 原文作者: Muxi Diao, Rumei Li, Shiyang Liu, Guogang Liao, Jingang Wang, Xunliang Cai, Weiran Xu 作者单位: 北京邮电大学, 美团 关键词: 大语言模…

vue.js项目实战案例详细源码讲解

​ 大家好&#xff0c;我是程序员小羊&#xff01; 前言&#xff1a; 为帮助大家更好地掌握Vue.js项目的开发流程&#xff0c;我将为你讲解一个完整的Vue.js实战案例&#xff0c;并提供详细的源码解析。这个案例将涵盖从项目创建到实现各种功能模块的全过程&#xff0c;适合用于…

基于空间结构光场照明的三维单像素成像

单像素成像是一种新兴的计算成像技术。该技术使用不具备空间分辨能力的单像素探测器来获取目标物体或场景的空间信息。单像素探测器具有高的时间分辨率、光探测效率和探测带宽&#xff0c;因此单像素光学成像技术在散射、弱光等复杂环境下相较于传统面阵成像技术展现了很大优势…

面试题:软件测试缺陷产生的原因有哪些?

软件缺陷产生的原因多种多样&#xff0c;一般可能有以下几种原因&#xff1a; 1.需求表述、理解、编写引起的错误。 2.系统架构设计引起的错误。 3.开发过程缺乏有效的沟通及监督&#xff0c;甚至没有沟通或监督。 4.程序员编程中产生的错误。 5.软件开发工具本身隐藏的问…

哨兵排序算法

代码展示 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h>#define MAXSIZE 20 //直接排序 typedef struct {int r[MAXSIZE 1];int length; } SqList; int InsertSort(SqList* L) {int i, j;for (i 2; i < L->length; i){if (L-…

mysql自增主键插入后返回id与实际插入id不同

加入这一段即可 GeneratedValue(strategy GenerationType.IDENTITY)

张飞硬件10-TVS管篇笔记

TVS管的原理 TVS或称瞬变电压抑制二极管&#xff0c;是在二极管工艺基础上发展起来的新产品&#xff0c;其电路符号和普通稳压管相同&#xff0c;外形也与普通二极管无异。当TVS管两端经受瞬间的高能量冲击时&#xff0c;它能以极高的速度将其阻抗骤然降低&#xff0c;同时吸收…

el-table 单元格,双击编辑

el-table 单元格&#xff0c;双击编辑 实现效果 代码如下 <template><el-table :data"tableData" style"width: 100%"><el-table-column prop"name" label"姓名" width"180"><template slot-scope&q…

【机器学习】梯度提升和随机森林的概念、两者在python中的实例以及梯度提升和随机森林的区别

引言 梯度提升&#xff08;Gradient Boosting&#xff09;是一种强大的机器学习技术&#xff0c;它通过迭代地训练决策树来最小化损失函数&#xff0c;以提高模型的预测性能 随机森林&#xff08;Random Forest&#xff09;是一种基于树的集成学习算法&#xff0c;它通过组合多…

Java队列详细解释

队列 一、什么是队列&#xff08;Queue&#xff09; java队列是一种线性数据结构&#xff0c;它的特点是先进先出。在队列中&#xff0c;元素的添加&#xff08;入队&#xff09;操作在队尾进行&#xff0c;而元素的移除&#xff08;出队&#xff09;操作则在队头进行。因此&a…

最近大模型最火的就业方向有哪些?

在2023和2024年&#xff0c;大语言模型的发展迎来了绝对风口&#xff0c;吸引了大量创业者和投资者。然而&#xff0c;经过一年的发展&#xff0c;许多公司已经销声匿迹。那么&#xff0c;未来大模型方向上还有哪些可以继续发展的方向呢? 基座大模型预训练 现状 - 展现出“胜…

TikTok Live与跨境电商的深度融合:直播带货引领品牌出海

在TikTok Live的应用中&#xff0c;品牌能够利用这一互动性极强的功能开辟新的销售渠道&#xff0c;推动全球业务的增长。本文Nox聚星将和大家探讨TikTok Live如何与跨境电商相结合&#xff0c;分析其应用场景。 一、TikTok Live与跨境电商的结合优势 庞大的用户基础&#xff…

使用 OpenCV 和 NumPy 进行图像处理:HSV 范围筛选实现PS抠图效果

使用 OpenCV 和 NumPy 进行图像处理&#xff1a;HSV 范围筛选实现PS抠图效果 在计算机视觉和图像处理领域&#xff0c;OpenCV 是一个非常强大的库&#xff0c;能够帮助我们执行各种图像操作。在这篇博客中&#xff0c;我们将通过一个简单的示例演示如何使用 OpenCV 和 NumPy 来…

machine learning - 2

泛化误差 也可以认为是预测时的误差。 训练误差 并不是越小越好&#xff0c;太小会过拟合。 获得测试集合的方法&#xff1a; 1&#xff09;&#xff1a; 2&#xff09;&#xff1a;例如&#xff1a;k-折交叉验证法&#xff0c; 就的每k个数据取一个座位测试集 3&#xff0…