【最优清零方案——贪心+滑动窗口+线段树】
题目

代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int a[N];
struct node
{int l, r;int m, p, lazy;
} tr[4 * N];
void pushup(node &u, node &l, node &r)
{if (l.m == r.m){u.m = l.m;u.p = max(l.p, r.p);}else if (l.m < r.m){u.m = l.m;u.p = l.p;}else{u.m = r.m;u.p = r.p;}
}
void pushup(int u)
{pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(node &u, node &l, node &r)
{if (u.lazy){l.m = max(l.m + u.lazy, 0);r.m = max(r.m + u.lazy, 0);l.lazy += u.lazy;r.lazy += u.lazy;u.lazy = 0;}
}
void pushdown(int u)
{pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{if (l == r)tr[u] = {l, r, a[l], l};else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}
void modify(int u, int l, int r, int d)
{if (l <= tr[u].l && tr[u].r <= r){tr[u].lazy += d;tr[u].m = max(tr[u].m + d, 0);return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)modify(u << 1, l, r, d);if (r > mid)modify(u << 1 | 1, l, r, d);pushup(u);
}
node query(int u, int l, int r)
{if (l <= tr[u].l && tr[u].r <= r)return tr[u];pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (r <= mid)return query(u << 1, l, r);else if (l > mid)return query(u << 1 | 1, l, r);else{auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);node ans;pushup(ans, left, right);return ans;}
}
int main()
{int n, k;cin >> n >> k;ll sum = 0;for (int i = 1; i <= n; i++)cin >> a[i], sum += a[i];build(1, 1, n);int l = 1, r;ll cnt = 0;while (r = l + k - 1, r <= n){auto u = query(1, l, r);int minn = u.m;cnt += minn;modify(1, l, r, -minn);l = u.p + 1;}cout << sum - k * cnt + cnt;
}
相关文章:
【最优清零方案——贪心+滑动窗口+线段树】
题目 代码 #include <bits/stdc.h> using namespace std; using ll long long; const int N 1e6 10; int a[N]; struct node {int l, r;int m, p, lazy; } tr[4 * N]; void pushup(node &u, node &l, node &r) {if (l.m r.m){u.m l.m;u.p max(l.p, r.…...
一个点绕任意点旋转后的点的坐标
在平面坐标上,任意点P(x1,y1),绕一个坐标点Q(x2,y2)逆时针旋转θ角度后,新的坐标设为(x, y)的计算公式: x (x1 - x2)*cos(θ) - (y1 - y2)*sin(θ) x2 ; y (x1 - x2)*sin(θ) (y1 - y2)*cos(θ) y2 ; 另一个场景应用,坐标轴绕…...
大数据面试题每日练习--HDFS是如何工作的?
HDFS(Hadoop Distributed File System)是一个分布式文件系统,设计用于存储非常大的文件。它的主要工作原理如下: NameNode:管理文件系统的命名空间,维护文件目录树和文件元数据信息。NameNode记录每个文件…...
Python的3D可视化库 - vedo (2)visual子模块 基本可视化行为
文章目录 1. visual模块的继承关系2. 基类CommonVisual的方法2.1 获取对象信息2.1.1 对象本身信息2.1.2 对象的查找表2.1.3 对象标量范围2.1.4 对象缩略图 2.2 呈现对象2.2.1 在窗口显示1.2.2 对象可见性 2.2.3 对象颜色2.2.4 对象透明度 2.3 添加标度条2.3.1 2D标度条2.3.2 3D…...
Java AIO(NIO.2)
Java AIO(Asynchronous I/O,异步I/O),也被称为NIO.2,是Java平台提供的一种处理异步输入/输出操作的机制。作为Java NIO(New I/O)的扩展,AIO引入了一些新的API和特性,旨在…...
Flink 常用问题及常用配置(有用)
一、Flink 常用问题及常用配置 参数 示例 说明 execution.checkpointing.interval 3min Checkpoint 触发间隔 state.backend rocksdb / filesystem 用于设置statebackend类型, 默认会以内存为statebackend(无法支持大状态) taskmanager.memory.jvm-overhead.max 204…...
RocketMQ: 消息过滤,通信组件,服务发现
消息过滤 1 ) 简单消息过滤 /*** 订阅指定topic下tags分别等于 TagA 或 TagC 或 TagD */consumer.subscribe("TopicTest1", "TagA || TagC || TagD");如以上代码所示,简单消息过滤通过指定多个 Tag 来过滤消息,过滤的动作在服务器进…...
linux ubuntu的脚本知
目录 一、变量的引用 二、判断指定的文件是否存在 三、判断目录是否存在 四、判断最近一次命令执行是否成功 五、一些比较符号 六、"文件"的读取和写入 七、echo打印输出 八、ubuntu切换到root用户 N、其它可以参考的网址 脚本功能强大,用起来也…...
HTTP有哪些风险?是怎么解决的?
一、风险 HTTP是通过明文传输的,存在窃听风险、篡改风险以及冒充风险。 二、如何解决 HTTPS在HTTP的下层加了一个SSL/TLS层,保证了安全,通过混合加密解决窃听风险、数字签名解决篡改风险、数字证书解决冒充风险。 (1࿰…...
3.12MayBeSomeLinearAlgebra
X是M*(D1),XT为(D1)*M Ω是一行D1列,X乘以欧米噶是M行D1列 行是说样本个数,列是特征数量 如果是小样本,那么可能会出现特征数量大于样本个数 如果MD*DM就是M*M,...
学习日志015--python单链表
创建 class Node:def __init__(self,data):# 数据域self.data data# 链接域self.next Noneclass LinkList:def __init__(self,):# 初始化头节点self.head None# 记录链表的长度self.size 0 增加 #头插def insert_head(self,value):# 创建新节点node Node(value)q self…...
如何在Windows右键新建菜单中添加自定义项
Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\.py] "Python.File"[HKEY_CLASSES_ROOT\.py\ShellNew] "NullFile"""[HKEY_CLASSES_ROOT\Python.File] "FriendlyTypeName""文本.py"[HKEY_CLASSES_ROOT\Python.Fil…...
Spring Boot 3.0废弃了JavaEE,改用了Jakarta EE
Spring Boot 3.0废弃了JavaEE,改用了Jakarta EE 历史背景 javax变成Jakarta的主要原因是因为Java EE项目从Oracle转移到了Eclipse Foundation,并改名为Jakarta EE。 JavaEE是从Java 1.2版本开始推出的Java企业级开发平台,最初的名称是J2EE(J…...
pdf文档动态插入文字水印,45度角,旋转倾斜,位于文档中央,多行水印可插入中文
一行水印 /*** param inputFile 你的PDF文件地址* param outputFile 添加水印后生成PDF存放的地址* param waterMarkName 你的水印* return*/public static boolean waterMark(String inputFile,String outputFile, String waterMarkName){try {PdfReader reader new PdfRead…...
[ 渗透测试面试篇-2 ] 针对大规模资产的攻击思路
🍬 博主介绍 👨🎓 博主介绍:大家好,我是 _PowerShell ,很高兴认识大家~ ✨主攻领域:【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 🎉点赞➕评论➕收藏 养成习…...
深入解析 Web 应用中的 CHIPS(Partitioned Cookie Attribute)
深入解析 Web 应用中的 CHIPS(Partitioned Cookie Attribute) 最新发现flask3.1.0 的版本引入了新的特性:对CHIPS的支持。不少同学对这个可能有点陌生,本文带大家了解一下。 为了在隐私保护和功能需求之间取得平衡,Goo…...
从搭建uni-app+vue3工程开始
技术栈 uni-app、vue3、typescript、vite、sass、uview-plus、pinia 一、项目搭建 1、创建以 typescript 开发的工程 npx degit dcloudio/uni-preset-vue#vite-ts my-vue3-project2、安装sass npm install -D sass// 安装sass-loader,注意需要版本10,…...
归并排序与逆序对问题(C语言版)
一、引言 归并排序是一种高效且稳定的排序方法,而逆序对问题是算法领域的一个经典问题,本文教大家如何实现归并排序,以及如何使用归并排序去结果逆序对问题 二、归并排序 归并排序思想 分解:将待排序的数组分成两半,…...
网络爬虫总结与未来方向
通过深入学习和实际操作,网络爬虫技术从基础到进阶得以系统掌握。本节将全面总结关键内容,并结合前沿技术趋势与最新资料,为开发者提供实用性强的深度思考和方案建议。 1. 网络爬虫技术发展趋势 1.1 趋势一:高性能分布式爬虫 随…...
C++ 核心数据结构:Stack 与 Queue 类深度解析
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 目录 💯前言 💯Stack 类 (一)Stack 类的概念与特点 (二&#x…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
