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

P4344 [SHOI2015] 脑洞治疗仪 线段树+二分

主要是维护一个连续区间,比较经典的题目,还要考虑一下二分的情况,否则很难处理,比较有难度。这里和序列操作一题的区别是不需要考虑1的个数,因为不需要取反。
传送门icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P4344

#include<iostream>
using namespace std;
#define lc u<<1
#define rc u<<1|1
const int N=2e5+10;
struct Tree{int l,r;int a,la,ra,ma;//  0的个数  左连续 右连续 总连续int len,add;
}tr[N*4];//
int n,m;void mo(int u,int k){Tree &t=tr[u];if(k==0){t.a=t.la=t.ra=t.ma=t.len;t.add=0;}if(k==1){t.a=t.la=t.ra=t.ma=0;t.add=1;}
}void pushdown(int u){Tree &t=tr[u];if(t.add==0) mo(lc,0),mo(rc,0);if(t.add==1) mo(lc,1),mo(rc,1);t.add=-1;
}void pushup(Tree &t,Tree l,Tree r){t.a=l.a+r.a;t.la=((l.a==l.len) ? l.la+r.la : l.la); t.ra=((r.a==r.len) ? r.ra+l.ra : r.ra);t.ma=max(max(l.ma,r.ma),l.ra+r.la);
}void build(int u,int l,int r){tr[u]={l,r,0,0,0,0,r-l+1,-1};if(l==r) return;int m=(l+r)>>1;build(lc,l,m);build(rc,m+1,r);pushup(tr[u],tr[lc],tr[rc]);
}void update(int u,int l,int r,int k){if(l<=tr[u].l&&tr[u].r<=r){mo(u,k);return;}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(l<=m) update(lc,l,r,k);if(r>m) update(rc,l,r,k);pushup(tr[u],tr[lc],tr[rc]);
}Tree query0(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u];}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(r<=m) return query0(lc,l,r);if(l>m) return query0(rc,l,r);Tree t;pushup(t,query0(lc,l,m),query0(rc,m+1,r));return t;
}int query0sum(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u].a;}pushdown(u);int ans=0;int m=(tr[u].l+tr[u].r)>>1;if(l<=m) ans+=query0sum(lc,l,r);if(r>m) ans+=query0sum(rc,l,r);return ans;
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;build(1,1,n);while(m--){int op,x1,y1;cin>>op>>x1>>y1;if(op==0) update(1,x1,y1,0);if(op==1){int x2,y2;cin>>x2>>y2;int x=(y1-x1+1)-query0sum(1,x1,y1);//1的个数update(1,x1,y1,0);int l=x2-1,r=y2+1;//二分if(x==0) continue;while(l+1<r){int mid=(l+r)>>1;if(query0sum(1,x2,mid)<=x) l=mid;else r=mid;}update(1,x2,l,1);}	if(op==2) cout<<query0(1,x1,y1).ma<<endl;	}return 0;
}

相关文章:

P4344 [SHOI2015] 脑洞治疗仪 线段树+二分

主要是维护一个连续区间&#xff0c;比较经典的题目&#xff0c;还要考虑一下二分的情况&#xff0c;否则很难处理&#xff0c;比较有难度。这里和序列操作一题的区别是不需要考虑1的个数&#xff0c;因为不需要取反。传送门https://www.luogu.com.cn/problem/P4344 #include&…...

解决大型语言模型中的幻觉问题:前沿技术的综述

大型语言模型中的幻觉问题及其解决技术综述 摘要 大型语言模型(LLM)如GPT-4、PaLM和Llama在自然语言生成能力方面取得了显著进步。然而&#xff0c;它们倾向于产生看似连贯但实际上不正确或与输入上下文脱节的幻觉内容&#xff0c;这限制了它们的可靠性和安全部署。随着LLM在…...

机器学习流程—AutoML

文章目录 机器学习流程—AutoMLAutoML工具Auto-SKLearnMLBoxTPOTRapidMinerPyCaretAuto-KerasH2OAutoML谷歌AutoML云Uber LudwigTransmogrifAIAutoGluonAutoWekaDataRobot...

Ubuntu 23.10 tar包安装和配置Elasticsearch kibana 7.13.3

目录 一、环境说明 二、准备工作 三、安装elasticsearch 3.1 安装elasticsearch 3.2 添加服务和设置开机启动 四、安装kibana 4.1. 安装kibana 4.2 添加服务和设置开机启动 出于工作需要&#xff0c;需要在Ubuntu 23.10系统上通过tar包方式安…...

glibc内存管理ptmalloc

1、前言 今天想谈谈ptmalloc如何为应用程序分配释放内存的&#xff0c;基于以下几点原因才聊它&#xff1a; C/C 70%的问题是内存问题。了解一点分配器原理对解决应用程序内存问题肯定有帮助。C也在用ptmalloc. 当你在C中new一个对象时&#xff0c;底层还是依赖glibc中的ptma…...

HarmonyOS入门学习

HarmonyOS入门学习 前言快速入门ArkTS组件基础组件Image组件Text组件TextInput 文本输入框Buttonslider 滑动组件 页面布局循环控制ForEach循环创建组件 List自定义组件创建自定义组件Builder 自定义函数 状态管理Prop和LinkProvide和ConsumeObjectLink和Observed ArkUI页面路由…...

【Mock|JS】Mock的get传参+获取参数信息

mockjs的get传参 前端请求 const { data } await axios("/video/childcomments", {params: {sort: 1,start: 2,count: 5,childCount: 6,commenIndex: 0,},});后端获取参数 使用正则匹配url /*** # 根据url获取query参数* param {Url} urlStr get请求获取参数 eg:…...

spring cloud gateway k8s优雅启停

通过配置readiness探针和preStop hook&#xff0c;实现优雅启动和停止&#xff08;滚动部署&#xff09; 1. k8s工作负载配置 readinessProbe:httpGet:path: /datetimeport: 8080scheme: HTTPinitialDelaySeconds: 30timeoutSeconds: 1periodSeconds: 30successThreshold: 1fa…...

嵌入式软件面试-linux-中高级问题

Linux系统启动过程&#xff1a; BIOS自检并加载引导程序。引导程序&#xff08;如GRUB&#xff09;加载Linux内核到内存。内核初始化硬件&#xff0c;加载驱动&#xff0c;建立内存管理。加载init进程&#xff08;PID为1&#xff09;&#xff0c;通常是systemd或SysVinit。init…...

css禁用元素指针事件,鼠标穿透,点击下层元素,用`pointer-events:none;`

pointer-events: 对鼠标事件的反应 MDN pointer-events 英文 https://developer.mozilla.org/en-US/docs/Web/CSS/pointer-events 菜鸟教程 CSS pointer-events 属性 https://www.runoob.com/cssref/css3-pr-pointer-events.html 常用取值 auto 和 none pointer-events: aut…...

Eureka的介绍和作用,以及搭建

一、Eureka的介绍和作用 Eureka是Netflix开源的一种服务发现和注册工具&#xff0c;它为分布式系统中的服务提供了可靠的服务发现和故障转移能力。Eureka是Netflix的微服务架构的关键组件之一&#xff0c;它能够实时地监测和管理服务实例的状态和可用性。 在Eureka架构中&…...

shell和linux的关系

Shell 和 Linux 之间存在密切的关系&#xff0c;但它们并不是同一个东西。让我们分别了解一下它们&#xff1a; Linux&#xff1a; Linux 是一个自由和开放源代码的类UNIX操作系统。 Linux 的内核由林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;于1991年首次发布&…...

数据在内存的存储

整数在内存中的存储 我们来回顾一下&#xff0c;整数在计算机是以补码的形式进行存储的&#xff0c;整数分为正整数和负整数&#xff0c;正整数的原码、反码和补码是一样的&#xff0c;负整数的原码、反码和补码略有不同&#xff08;反码是原码除符号位&#xff0c;其他位按位取…...

JavaScript之ES中的类继承与Promise

类 ES5中的类及继承 //人function Person(name,age){this.name name;this.age age;}Person.prototype.eat function () {console.log(this.name "eat");}//程序员&#xff0c;继承&#xff0c;人function Programmer(name,age,language){//构造函数继承Person.…...

​浅析多模态大模型技术路线梳理

前段时间 ChatGPT 进行了一轮重大更新&#xff1a;多模态上线&#xff0c;能说话&#xff0c;会看图&#xff01;微软发了一篇长达 166 页的 GPT-4V 测评论文&#xff0c;一时间又带起了一阵多模态的热议&#xff0c;随后像是 LLaVA-1.5、CogVLM、MiniGPT-5 等研究工作紧随其后…...

使用 Amazon SageMaker 微调 Llama 2 模型

本篇文章主要介绍如何使用 Amazon SageMaker 进行 Llama 2 模型微调的示例。 这个示例主要包括: Llama 2 总体介绍Llama 2 微调介绍Llama 2 环境设置Llama 2 微调训练 前言 随着生成式 AI 的热度逐渐升高&#xff0c;国内外各种基座大语言竞相出炉&#xff0c;在其基础上衍生出…...

牛客小白月赛86(D剪纸游戏)

题目链接:D-剪纸游戏_牛客小白月赛86 (nowcoder.com) 题目描述: 输入描述: 输入第一行包含两个空格分隔的整数分别代表 n 和 m。 接下来输入 n行&#xff0c;每行包含 m 个字符&#xff0c;代表残缺纸张。 保证&#xff1a; 1≤n,m≤10001 字符仅有 . 和 * 两种字符&#xf…...

MySQL的基础操作与管理

一.MySQL数据库基本操作知识&#xff1a; 1.SQL语句&#xff1a; 关系型数据库&#xff0c;都是使用SQL语句来管理数据库中的数据。 SQL&#xff0c;即结构化查询语言(Structured Query Language) 。 SQL语句用于维护管理数据库&#xff0c;包括数据查询、数据更新、访问控…...

Pytorch 中的forward 函数内部原理

PyTorch中的forward函数是nn.Module类的一部分&#xff0c;它定义了模型的前向传播规则。当你创建一个继承自nn.Module的类时&#xff0c;你实际上是在定义网络的结构。forward函数是这个结构中最关键的部分&#xff0c;因为它指定了数据如何通过网络流动。 单独设计 forward …...

四、C语言中的数组:如何输入与输出二维数组(数组,完)

本章的学习内容如下 四、C语言中的数组&#xff1a;数组的创建与初始化四、C语言中的数组&#xff1a;数组的输入与元素个数C语言—第6次作业—十道代码题掌握一维数组四、C语言中的数组&#xff1a;二维数组 1.二维数组的输入与输出 当我们输入一维数组时需要一个循环来遍历…...

SQL如何检测分组内是否存在满足条件的数据_EXISTS结合分组

用 MAX(CASE WHEN condition THEN 1 ELSE 0 END) 1 判断分组内是否存在符合条件的行最稳妥&#xff0c;避免 EXISTS 在 GROUP BY 中语法错误或逻辑失效&#xff0c;兼容性好且语义清晰。GROUP BY 后怎么判断某组里有没有符合条件的行直接用 HAVING 配合聚合函数最稳妥&#xf…...

告别Keil单调调试:用Ozone + J-Link可视化你的FreeRTOS任务状态(附工程配置避坑点)

告别Keil单调调试&#xff1a;用Ozone J-Link可视化你的FreeRTOS任务状态&#xff08;附工程配置避坑点&#xff09; 嵌入式开发中&#xff0c;调试环节往往占据大量时间成本。当项目复杂度上升到RTOS层面时&#xff0c;传统的Keil调试界面显得力不从心——开发者需要反复切换…...

.NET对象转JSON,到底有几种方式?荣

背景 在软件开发的漫长旅途中&#xff0c;"构建"这个词往往让人又爱又恨。爱的是&#xff0c;一键点击&#xff0c;代码变成产品&#xff0c;那是程序员最迷人的时刻&#xff1b;恨的是&#xff0c;维护那一堆乱糟糟的构建脚本&#xff0c;简直是噩梦。 在很多项目中…...

Folcolor:告别视觉疲劳!14种色彩让你的Windows文件夹管理效率提升3倍

Folcolor&#xff1a;告别视觉疲劳&#xff01;14种色彩让你的Windows文件夹管理效率提升3倍 【免费下载链接】Folcolor Windows explorer folder coloring utility 项目地址: https://gitcode.com/gh_mirrors/fo/Folcolor 你是否曾在成百上千个黄色文件夹中迷失方向&am…...

从矩阵SVD到张量T-SVD:算法原理与傅里叶变换的桥梁

1. 从矩阵到张量&#xff1a;理解SVD的核心思想 我第一次接触奇异值分解&#xff08;SVD&#xff09;是在处理图像压缩项目时。当时需要将一个20002000像素的图片压缩到原来大小的1/10&#xff0c;而传统的JPEG压缩算法会导致关键特征丢失。导师简单说了句"用SVD试试&quo…...

终极Cursor Pro破解指南:三步免费解锁AI编程无限体验

终极Cursor Pro破解指南&#xff1a;三步免费解锁AI编程无限体验 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your tria…...

从交流到直流:用一颗BL0910芯片搞定多路电能监测的硬件设计与SPI通信要点

从交流到直流&#xff1a;BL0910芯片在多路电能监测中的硬件设计与SPI通信实战 在能源管理系统中&#xff0c;精确测量交直流电能是核心需求。BL0910作为一款高度集成的计量芯片&#xff0c;能够同时处理多达10路的交直流混合信号&#xff0c;为智能电表、工业监控设备提供了高…...

解锁Windows无限可能:Windhawk模块化定制完全指南

解锁Windows无限可能&#xff1a;Windhawk模块化定制完全指南 【免费下载链接】windhawk The customization marketplace for Windows programs: https://windhawk.net/ 项目地址: https://gitcode.com/gh_mirrors/wi/windhawk 你是否曾对Windows系统一成不变的界面感到…...

Java实战:基于163邮箱的自动化邮件发送系统设计与实现

1. 为什么需要自动化邮件发送系统 在日常开发中&#xff0c;邮件发送功能几乎是每个系统都需要的标配功能。想象一下&#xff0c;当用户在你的网站注册时&#xff0c;系统自动发送一封欢迎邮件&#xff1b;当用户忘记密码时&#xff0c;系统自动发送密码重置链接&#xff1b;当…...

videopipe环境配置实战:从驱动安装到Docker镜像打包

1. NVIDIA驱动安装与常见问题排查 在Linux系统上配置videopipe环境的第一步就是搞定NVIDIA显卡驱动。很多开发者第一次接触这个环节时都会遇到各种"拦路虎"&#xff0c;我自己在项目中也踩过不少坑。先说说最基础的安装流程&#xff1a;对于Ubuntu系统&#xff0c;建…...