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

UOJ 228 基础数据结构练习题 Solution

news 来源：原创 2025/6/22 3:58:53

Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ ，有 $m$ 个操作分三种：

$\operatorname{add}(l,r,k)$ ：对每个 $i\in[l,r]$ 执行 $a_i\gets a_i+k$ .
$\operatorname{square}(l,r)$ ：对每个 $i\in[l,r]$ 执行 $a_i\gets \lfloor \sqrt {a_i} \rfloor$ .
$\operatorname{query}(l,r)$ ：求 $\sum_{i=l}^r a_i$ .

Limitations

$1\le n,m\le 10^5$
$1\le l\le r\le n$
$1\le a_i,k\le 10^5$

Solution

考虑 $\operatorname{sqrt}$ 操作怎么做.
显然当区间极差为 $0$ 时，直接对整个区间开方.
但是当极差为 $1$ 时，可以被开方直到极差为 $1$ 后加回去的方法卡成 $O (nm)$ .
这个也很好解决，如果当前区间与开方后的区间极差均为 $1$ ，也直接进行开方.

Code

$3.3\text{KB},637\text{ms},11.57\text{MB}\;\texttt{(in total, C++20)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}namespace seg_tree {struct Node {int l, r;i64 max, min, sum, tag;};inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<i64>& a) {const int n = a.size();tr.resize(n << 1);build(0, 0, n - 1, a);}inline void pushup(int u, int mid) {tr[u].sum = tr[ls(mid)].sum + tr[rs(mid)].sum;tr[u].max = max(tr[ls(mid)].max, tr[rs(mid)].max);tr[u].min = min(tr[ls(mid)].min, tr[rs(mid)].min);}inline void apply(int u, i64 tag) {tr[u].sum += tag * (tr[u].r - tr[u].l + 1);tr[u].min += tag;tr[u].max += tag;tr[u].tag += tag;}inline void pushdown(int u, int mid) {if (tr[u].tag) {apply(ls(mid), tr[u].tag);apply(rs(mid), tr[u].tag);tr[u].tag = 0;}}void build(int u, int l, int r, const vector<i64>& a) {tr[u].l = l, tr[u].r = r;if (l == r) return (void)(tr[u].sum = tr[u].min = tr[u].max = a[l]);const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}void sqrt(int u, int l, int r) {if (tr[u].max == 1) return;if (l <= tr[u].l && tr[u].r <= r) {i64 tmin = std::sqrt(tr[u].min), tmax = std::sqrt(tr[u].max);if (tr[u].min == tr[u].max || (tmin + 1 == tmax && tr[u].min + 1 == tr[u].max)) {return apply(u, tmax - tr[u].max);}}const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) sqrt(ls(mid), l, r);if (r > mid) sqrt(rs(mid), l, r);pushup(u, mid);}void add(int u, int l, int r, i64 k) {if (l <= tr[u].l && tr[u].r <= r) return apply(u, k);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) add(ls(mid), l, r, k);if (r > mid) add(rs(mid), l, r, k);pushup(u, mid);}i64 query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;const int mid = (tr[u].l + tr[u].r) >> 1;i64 res = 0;pushdown(u, mid);if (l <= mid) res += query(ls(mid), l, r);if (r > mid) res += query(rs(mid), l, r);return res;}inline void range_sqrt(int l, int r) { sqrt(0, l, r); }inline void range_add(int l, int r, i64 v) { add(0, l, r, v); }inline i64 range_sum(int l, int r) { return query(0, l, r); }};
}
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m; scanf("%d %d", &n, &m);vector<i64> a(n);for (int i = 0; i < n; i++) scanf("%lld", &a[i]);SegTree sgt(a);for (int i = 0, op, l, r, v; i < m; i++) {scanf("%d %d %d", &op, &l, &r), l--, r--;if (op == 1) {scanf("%d", &v);sgt.range_add(l, r, v);}else if (op == 2) sgt.range_sqrt(l, r);else printf("%lld\n", sgt.range_sum(l, r));}return 0;
}

UOJ 228 基础数据结构练习题 Solution

Description 给定序列 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1,a2,⋯,an)，有 m m m 个操作分三种： add ⁡ ( l , r , k ) \operatorname{add}(l,r,k) add(l,r,k)：对每个 i ∈ [ l , r ] i\in[l,r] i∈[l,r] 执行 …...

编程日记 2025/6/22 3:58:53

工业相机——镜头篇【机器视觉，图像采集系统，成像原理，光学系统，成像光路，镜头光圈，镜头景深，远心镜头，分辨率，MTF曲线，焦距计算，子午弧矢】

文章目录 1 机器视觉，图像采集系统2 相机镜头，属于一种光学系统3 常规镜头成像光路4 镜头光圈5 镜头的景深6 远心镜头及成像原理7 远心镜头种类及应用场景8 镜头分辨率10 镜头的对比度11 镜头的MTF曲线12 镜头的焦距计算13 子午弧矢图解反差工业…...

编程日记 2025/6/22 2:57:53

珍爱网：从降本增效到绿色低碳，数字化新基建价值凸显

2024年12月24日，法大大联合企业绿色发展研究院发布《2024签约减碳与低碳办公白皮书》，深入剖析电子签在推动企业绿色低碳转型中的关键作用，为企业实现环境、社会和治理（ESG）目标提供新思路。近期，法大大将陆…...

编程日记 2025/5/29 22:22:49

Java大师成长计划之第3天：Java中的异常处理机制

📢 友情提示： 本文由银河易创AI（https://ai.eaigx.com）平台gpt-4o-mini模型辅助创作完成，旨在提供灵感参考与技术分享，文中关键数据、代码与结论建议通过官方渠道验证。在 Java 编程中，异常处理…...

编程日记 2025/6/22 3:09:51

主题模型三大基石：Unigram、LSA、PLSA详解与对比

🌟 主题模型演进图谱文本建模三阶段： 词袋模型 → 潜在语义 → 概率生成 Unigram → LSA → PLSA → LDA 📦 基础模型：Unigram模型核心假设文档中每个词独立生成（词袋假设） 忽略词语顺序和语义关联 …...

编程日记 2025/6/22 3:56:05

【Linux网络】TCP服务中IOService应用与实现

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/6/22 3:05:22

终端运行java出现？？？

1.检查是否系统区域设置冲突（控制面板 → 区域 → 管理 → 更改系统区域设置 → 勾选 Beta: UTF-8）。 2.修改 Windows 终端编码方法 1：临时修改（当前窗口） 在终端执行：cmd chcp 65001 …...

编程日记 2025/6/4 4:25:51

Mysql8.0 推出的强大功能窗口函数（Window Functions）

🧠 一、什么是窗口函数？ 窗口函数是 SQL 中一种在保留原始行的基础上，对行进行分组排序后执行聚合、排名、累计等计算的方法。与传统的 GROUP BY 聚合不同的是： 👉 窗口函数不会把多行聚成一行，而是为每…...

编程日记 2025/6/22 3:32:21

opencv--通道，彩色和灰度

图像的灰度值和颜色值的区别灰度值（Grayscale Value）和颜色值（Color Value）是描述像素信息的两种基本方式，它们的核心区别在于对颜色信息的表示方式和应用场景。 (1) 灰度值（Grayscale Value）…...

编程日记 2025/6/20 16:17:15

cmake 执行命令

在命令行中执行 CMake 的命令主要用于配置、生成和构建项目。以下是一些常用的 CMake 命令及其用法。 1. 配置项目配置项目是 CMake 的第一步，它会根据 CMakeLists.txt 文件生成相应的构建系统文件（如 Makefile 或 Visual Studio 解决方案文件&#x…...

编程日记 2025/5/30 15:56:22

Shell脚本-for循环语法结构

在Shell脚本编程中，for循环是一种非常常用的流程控制语句。它允许我们对一系列值进行迭代，并为每个值执行特定的命令或代码块。无论是处理文件列表、遍历目录内容还是简单的计数任务，for循环都能提供简洁而强大的解决方案。本文将详细介绍She…...

编程日记 2025/6/22 3:09:51

【AI落地应用实战】借助 Amazon Q 实现内容分发网络（CDN）CDK 构建的全流程实践

随着生成式 AI 技术的快速发展，开发者在构建云原生应用时正以前所未有的效率推进项目落地。而 Amazon Q，作为亚马逊云科技推出的专为开发者和 IT 人员设计的生成式 AI 助手，正逐步改变着我们与代码、基础设施以及亚马逊云科技服务交互的方式…...

编程日记 2025/6/22 3:17:40

Windows同步技术-使用命名对象

在 Windows 系统下使用命名对象（如互斥体、事件、信号量、文件映射等内核对象）时，需注意以下关键要点： 命名规则唯一性：名称需全局唯一，避免与其他应用或系统对象冲突，建议使用 GUID 或应用专…...

编程日记 2025/6/3 13:57:42

Python Cookbook-6.8 避免属性读写的冗余代码

任务你的类会用到某些 property 实例，而 getter 或者 setter 都是一些千篇一律的获取或者设置实例属性的代码。你希望只用指定属性名，而不用写那些非常相似的代码。解决方案需要一个工厂函数，用它来处理那些 getter 或 setter 的参数是…...

编程日记 2025/6/22 3:26:30

热带气旋【CH报文数据插值】中央气象台-台风路径数据每小时插值

对CH报文数据进行每小时插值原始数据文件数据三小时一次的报文数据需求按小时补齐热带气旋路径信息插值后数据效果如下： 插值代码 # 对ch文件插值import pandas as pd import datetime import osdef interpolate_ch_one_hour (file_name):new_file_name…...

编程日记 2025/6/22 3:28:14

06-stm32时钟体系

一、时钟体系 1、概念 1.时钟信号：是一种周期性的电信号，例如为方波，正弦波，余弦波等各种波形，用于同步数字电路中的各种操作，它控制着数据的传输以及电路状态的变化。 2、时钟系统在 STM32 的系统中扮演…...

编程日记 2025/6/22 3:51:46

Hbase集群管理与实践

一、HBase集群搭建实战 1.1 环境规划建议硬件配置基准（以10节点集群为例）： 角色CPU内存磁盘网络HMaster4核16GBSSD 200GB（系统盘）10GbpsRegionServer16核64GB124TB HDD（JBOD）25GbpsZooKeepe…...

编程日记 2025/6/20 4:26:30

基于大模型对先天性巨结肠全流程预测及医疗方案研究报告

目录一、引言 1.1 研究背景与意义 1.2 研究目的与创新点二、大模型在先天性巨结肠预测中的理论基础 2.1 大模型概述 2.2 大模型预测先天性巨结肠的可行性分析三、术前预测与准备方案 3.1 大模型对术前病情的预测 3.1.1 疾病确诊预测 3.1.2 病情严重程度评估 3.2 …...

编程日记 2025/6/22 3:43:19

计算机组成原理-408考点-数的表示

常见题型：C语言中的有符号数和无符号数的表示。【例】有如下C语言程序段: short si-32767；unsigned short usisi；执行上述两条语句后，usi的值为___。short和unsigned short均使用16位二进制数表示。【分析】考点：同…...

编程日记 2025/5/29 16:41:00

vue滑块组件设计与实现

vue滑块组件设计与实现设计一个滑块组件的思想主要包括以下几个方面：用户交互、状态管理、样式设计和事件处理。以下是详细的设计思想： 1. 用户交互滑块组件的核心是用户能够通过拖动滑块来选择一个值。因此，设计时需要考虑以下几点&…...

编程日记 2025/5/30 2:24:44

Linux阻塞与非阻塞I/O：从原理到实践详解

Linux阻塞与非阻塞I/O：从原理到实践详解 1. 阻塞与非阻塞I/O基础概念 1.1 阻塞与非阻塞简介在Linux系统编程中，I/O操作可以分为两种基本模式：阻塞I/O和非阻塞I/O。这两种模式决定了当设备或资源不可用时，程序的行为方式。阻…...

编程日记 2025/6/20 23:46:02

form表单提交前设置请求头request header及文件下载

需求：想要在form表单submit之前，设置一下请求头。除了用Ajax发起请求之外，还可以使用FormData来实现，咱不懂就问。 1 问：FormData什么时间出现的？与ajax什么联系？ 2 问：FormData使…...

编程日记 2025/6/22 3:21:19

整合 CountVectorizer 和 TfidfVectorizer 绘制词云图

本文分别整合 CountVectorizer 和 TfidfVectorizer 绘制词云图 ✨ CountVectorizer CountVectorizer 是 scikit-learn 中用于文本特征提取的一个工具，它的主要作用是将一组文本（文本集合）转换为词频向量（Bag-of-Words&#xf…...

编程日记 2025/6/3 12:58:25

国产AI大模型超深度横评：技术参数全解、商业落地全场景拆解

评测方法论与指标体系评测框架设计采用三层评估体系，涵盖技术性能、商业价值、社会效益三大维度，细分为12个二级指标、36个三级指标： 测试环境配置项目配置详情硬件平台8NVIDIA H100集群，NVLink全互联，3TB内存软…...

编程日记 2025/6/22 3:21:19

Shell脚本-流程控制语句应用案例

在Shell脚本编程中，流程控制语句是实现逻辑控制和自动化任务处理的关键。通过合理运用条件判断、循环等流程控制语句，可以编写出高效、灵活的脚本程序。本文将通过几个实际的应用案例来展示如何使用这些流程控制语句解决具体的编程问题。案例一&#x…...

编程日记 2025/6/22 3:01:21

HarmonyOS NEXT应用开发-Notification Kit（用户通知服务）notificationManager.addSlot

1.notificationManager.addSlot 支持设备Phone2in1TabletCarWearable addSlot(type: SlotType, callback: AsyncCallback<void>): void 创建指定类型的通知渠道。使用callback异步回调。系统能力：SystemCapability.Notification.Notification 示例&#xf…...

编程日记 2025/6/20 16:02:53

计算机网络核心知识点全解析（面试通关版）

一、网络体系结构：从OSI到TCP/IP的分层设计 1.1 七层模型与四层模型对比 OSI七层模型核心功能TCP/IP四层对应典型协议生活类比应用层为应用程序提供服务（如文件传输、邮件、Web浏览）应用层HTTP、FTP、SMTP、DNS快递面单信息（收件…...

编程日记 2025/6/21 15:36:43

表示学习与部分域适应

表示学习（Representation Learning） 表示学习是机器学习的一个分支，旨在自动从原始数据中提取有意义的特征或表示，使得这些表示更适合后续任务（如分类、检测、回归等）。其核心思想是将高维、复杂、冗余的原…...

编程日记 2025/5/30 10:22:58

AI与思维模型【77】——PDCA思维模型

一、定义 PDCA思维模型是一种用于持续改进和优化工作流程、项目实施以及问题解决的科学管理方法。它由四个英文字母组成，分别代表计划（Plan）、执行（Do）、检查（Check）和处理（Act&…...

编程日记 2025/5/27 23:25:32

Flink 系列之七 - Data Stream API的源算子原理

之前做过数据平台，对于实时数据采集，使用了Flink。现在想想，在数据开发平台中，Flink的身影几乎无处不在，由于之前是边用边学，总体有点混乱，借此空隙，整理一下Flink的内容&#xff0c…...

编程日记 2025/6/22 1:55:09

使用 SSE + WebFlux 推送日志信息到前端

为什么使用 SSE 而不使用 WebSocket, 请看 SEE 对比 Websocket 的优缺点。特性SSEWebSocket通信方向单向（服务器→客户端）双向（全双工）协议基于 HTTP独立协议（需 ws:// 前缀）兼容性现代浏览器&#xff08…...

编程日记 2025/5/29 14:04:51

Java多线程同步有哪些方法?

大家好，我是锋哥。今天分享关于【Java多线程同步有哪些方法?】面试题。希望对大家有帮助； Java多线程同步有哪些方法? 1000道互联网大厂Java工程师精选面试题-Java资源分享网在 Java 中，多线程同步是确保多个线程在访问共享资源时不会…...

编程日记 2025/6/20 1:46:52

Java—数组

数组就是一个容器，用来存一批同种类型的数据。一、静态初始化数组 1.1 定义方式语法： 完整格式：数据类型 [ ] 数组名 new 数据类型 []{ 元素 1 ，元素 2 ，元素3… };简化格式：数据类型 [ ] 数组名 {…...

编程日记 2025/6/4 14:30:27

iOS/Android 使用 C++ 跨平台模块时的内存与生命周期管理

在移动应用开发领域，跨平台开发已经成为一种不可忽视的趋势。随着智能手机市场的持续扩张，开发者需要同时满足iOS和Android两大主流平台的需求，而这往往意味着重复的工作量和高昂的维护成本。跨平台开发的目标在于通过一套代码库实现多平台的支持，从而降低开发成本、加速产…...

编程日记 2025/5/29 14:53:00

为什么vue的key值，不用index？

在 Vue 中，key 的作用是帮助框架高效地识别和复用 DOM 节点或组件实例。使用数组索引 (index) 作为 key 值可能会导致以下问题，因此通常不建议这样做： 1. 列表数据变化时，可能导致错误的 DOM 复用问题：当列表的顺序…...

编程日记 2025/6/20 11:22:22

Hi3516CV608 超高清智慧视觉 SoC 芯片可提供开发资料

Hi3516CV608 超高清智慧视觉SoC 产品简介总体介绍 Hi3516CV608是一颗面向消费类市场的IPC SoC，在新一代视频编解码标准、网络安全、隐私保护和人工智能方面引领行业发展。主要应用于室内外场景下的云台机、枪机、球机、枪球一体机、双目长短焦机等产品形态&#…...

编程日记 2025/5/30 18:05:46

Flink部署与应用——部署方式介绍

引入我们通过Flink相关论文的介绍，对于Flink已经有了初步理解，这里简单的梳理一下Flink常见的部署方式。 Flink 的部署方式 StandAlone模式介绍 StandAlone模式是Flink框架自带的分布式部署模式，不依赖其他的资源调度框架&#xff0c…...

编程日记 2025/5/29 11:40:33

数据挖掘技术与应用课程论文——数据挖掘中的聚类分析方法及其应用研究

数据挖掘中的聚类分析方法及其应用研究摘要聚类分析是数据挖掘技术中的一个重要组成部分，它通过将数据集中的对象划分为多个组或簇，使得同一簇内的对象具有较高的相似性，而不同簇之间的对象具有较低的相似性。本文系统地研究了数据挖掘中的多种聚类分析方法及其应用。首先…...

编程日记 2025/5/28 7:06:16

SIEMENS PLC程序解读 ST 语言车型识别

1、ST程序代码 IF #Type1_MIX < #CFG_Type.Type.CT AND #CFG_Type.Type.CT < #Type1_MAX AND #CFG_Type.Type.CT<>0 THEN#Type[1] : 1;FOR #I : 0 TO 39 DOIF #CFG_Type.Type.CT/10 (#Type1_MIX 10 * #I)/10 THEN#Sub_Type."1"[#I 1] : 1;END_IF; E…...

编程日记 2025/6/21 22:43:50

神经网络基础[损失函数,bp算法,梯度下降算法 ]

关于神经网络的基础的概念可以看我前面的文章损失函数在深度学习中, 损失函数是用来衡量模型参数的质量的函数, 衡量的方式是比较网络输出和真实输出的差异作用:指导模型的训练过程，通过反向传播算法计算梯度，从而更新网络的参数，最终使…...

编程日记 2025/6/4 1:37:51

python打印颜色（python颜色、python print颜色、python打印彩色文字、python print彩色、python彩色文字）

文章目录 python怎么打印彩色文字1. 使用ANSI转义码：2. 使用colorama库（更好的跨平台支持）：3. 使用termcolor库： python怎么打印彩色文字在Python中打印彩色文字有几种方法： 1. 使用ANSI转义码&#xff…...

编程日记 2025/6/21 15:37:53

数字域残留频偏的补偿原理

模拟域的频谱搬移一般通过混频器实现。一般情况下模拟域调整完频偏后数字域还会存在一部分残留频偏这部分就需要在数字域补偿。原理比较简单本文进行下粗略总结。首先我们需要了解下采样具体可参考下信号与系统笔记(六)：采样 - 知乎。采样前和采样后，角…...

编程日记 2025/6/19 22:08:17

Linux文件管理2

Linux 文件管理是系统操作的核心内容之一，涉及文件和目录的创建、删除、移动、查看、权限管理等操作。以下是 Linux 文件管理的核心知识点和常用操作总结： 一、文件系统结构 Linux 文件系统采用树形结构，以 /（根目录&#xff0…...

编程日记 2025/5/30 19:58:13

C++----模拟实现string

模拟实现string，首先我们要知道成员变量有哪些： class _string{private:char* _str;size_t capacity;//空间有多大size_t size;//有效字符多少const static size_t npos;};const size_t _string::npos-1;//static在外面定义不需要带static，np…...

编程日记 2025/5/29 21:37:05

Python torch.optim.lr_scheduler 常用学习率调度器使用方法

在看学习率调度器之前，我们先看一下学习率的相关知识： 学习率学习率的定义学习率（Learning Rate）是深度学习中一个关键的超参数，它决定了在优化算法（如梯度下降法）更新模型参数时&#xff0…...

编程日记 2025/6/4 4:29:00

从零开始学Python游戏编程39-碰撞处理1

在《从零开始学Python游戏编程38-精灵5》代码的基础上，添加两个敌人的防御塔，玩家的坦克无法移动到防御塔所在的空格中，如图1所示。图1 游戏中的碰撞处理 1 游戏中空格的坐标在《从零开始学Python游戏编程36-精灵3》中提到，可…...

编程日记 2025/5/24 21:04:40

同步定时器的用户数要和线程组保持一致，否则jmeter会出现接口不执行’stop‘和‘×’的情况

调试压测时发现了一个问题就是线程计划总是出现‘stop’的按钮无法执行完毕发现时同步定时器导致的，就是有接口使用了同步定时器，但是这个同步定时器的用户数量设置的＜线程组用户数量时，会出现执行无法结束的情况，如下…...

编程日记 2025/6/21 6:00:21

如何在Linux用libevent写一个聊天服务器

废话少说，先看看思路因为libevent的回调机制，我们可以借助这个机制来创建bufferevent来实现用户和用户进行通信如果成功连接后我们可以直接在listener回调函数里创建一个bufferevent缓冲区，并为每个缓冲区设置相应的读回调和事件回调&…...

编程日记 2025/6/21 13:18:33

Virtuoso ADE采用Spectre仿真中出现MOS管最小长宽比满足要求依然报错的情况解决方法

在ADE仿真中错误问题如下： ERROR (CMI-2440): "xxx.scs" 46338: I2.M1: The length, width, or area of the instance does not fit the given lmax-lmin, wmax-wmin, or areamax-areamin range for any model in the I2.M3.nch_hvt group. The channel w…...

编程日记 2025/5/29 7:05:23

防火墙原理与应用总结

防火墙介绍： 防火墙（Firewall）是一种网络安全设备，其核心目标是通过分析数据包的源地址、端口、协议等内容，保护一个网络区域免受来自另一个网络区域的网络攻击和网络入侵行为，同时允许合法流量自由通行。…...

编程日记 2025/6/21 9:25:11

Description

Limitations

Solution

Code

相关文章：