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

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

题目

代码

#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.…...

一个点绕任意点旋转后的点的坐标

在平面坐标上&#xff0c;任意点P(x1,y1)&#xff0c;绕一个坐标点Q(x2,y2)逆时针旋转θ角度后,新的坐标设为(x, y)的计算公式&#xff1a; x (x1 - x2)*cos(θ) - (y1 - y2)*sin(θ) x2 ; y (x1 - x2)*sin(θ) (y1 - y2)*cos(θ) y2 ; 另一个场景应用&#xff0c;坐标轴绕…...

大数据面试题每日练习--HDFS是如何工作的?

HDFS&#xff08;Hadoop Distributed File System&#xff09;是一个分布式文件系统&#xff0c;设计用于存储非常大的文件。它的主要工作原理如下&#xff1a; NameNode&#xff1a;管理文件系统的命名空间&#xff0c;维护文件目录树和文件元数据信息。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&#xff08;Asynchronous I/O&#xff0c;异步I/O&#xff09;&#xff0c;也被称为NIO.2&#xff0c;是Java平台提供的一种处理异步输入/输出操作的机制。作为Java NIO&#xff08;New I/O&#xff09;的扩展&#xff0c;AIO引入了一些新的API和特性&#xff0c;旨在…...

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");如以上代码所示&#xff0c;简单消息过滤通过指定多个 Tag 来过滤消息&#xff0c;过滤的动作在服务器进…...

linux ubuntu的脚本知

目录 一、变量的引用 二、判断指定的文件是否存在 三、判断目录是否存在 四、判断最近一次命令执行是否成功 五、一些比较符号 六、"文件"的读取和写入 七、echo打印输出 八、ubuntu切换到root用户 N、其它可以参考的网址 脚本功能强大&#xff0c;用起来也…...

HTTP有哪些风险?是怎么解决的?

一、风险 HTTP是通过明文传输的&#xff0c;存在窃听风险、篡改风险以及冒充风险。 二、如何解决 HTTPS在HTTP的下层加了一个SSL/TLS层&#xff0c;保证了安全&#xff0c;通过混合加密解决窃听风险、数字签名解决篡改风险、数字证书解决冒充风险。 &#xff08;1&#xff0…...

3.12MayBeSomeLinearAlgebra

X是M*(D1),XT为&#xff08;D1)*M Ω是一行D1列&#xff0c;X乘以欧米噶是M行D1列 行是说样本个数&#xff0c;列是特征数量 如果是小样本&#xff0c;那么可能会出现特征数量大于样本个数 如果MD*DM就是M*M&#xff0c;...

学习日志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&#xff0c;改用了Jakarta EE 历史背景 javax变成Jakarta的主要原因是因为Java EE项目从Oracle转移到了Eclipse Foundation&#xff0c;并改名为Jakarta EE。 JavaEE是从Java 1.2版本开始推出的Java企业级开发平台&#xff0c;最初的名称是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 ] 针对大规模资产的攻击思路

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

深入解析 Web 应用中的 CHIPS(Partitioned Cookie Attribute)

深入解析 Web 应用中的 CHIPS&#xff08;Partitioned Cookie Attribute&#xff09; 最新发现flask3.1.0 的版本引入了新的特性&#xff1a;对CHIPS的支持。不少同学对这个可能有点陌生&#xff0c;本文带大家了解一下。 为了在隐私保护和功能需求之间取得平衡&#xff0c;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&#xff0c;注意需要版本10&#xff0c;…...

归并排序与逆序对问题(C语言版)

一、引言 归并排序是一种高效且稳定的排序方法&#xff0c;而逆序对问题是算法领域的一个经典问题&#xff0c;本文教大家如何实现归并排序&#xff0c;以及如何使用归并排序去结果逆序对问题 二、归并排序 归并排序思想 分解&#xff1a;将待排序的数组分成两半&#xff0c…...

网络爬虫总结与未来方向

通过深入学习和实际操作&#xff0c;网络爬虫技术从基础到进阶得以系统掌握。本节将全面总结关键内容&#xff0c;并结合前沿技术趋势与最新资料&#xff0c;为开发者提供实用性强的深度思考和方案建议。 1. 网络爬虫技术发展趋势 1.1 趋势一&#xff1a;高性能分布式爬虫 随…...

C++ 核心数据结构:Stack 与 Queue 类深度解析

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 目录 &#x1f4af;前言 &#x1f4af;Stack 类 &#xff08;一&#xff09;Stack 类的概念与特点 &#xff08;二&#x…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

C++中vector类型的介绍和使用

文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...

STL 2迭代器

文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器&#xff1f; 1.迭代器…...

VUE3 ref 和 useTemplateRef

使用ref来绑定和获取 页面 <headerNav ref"headerNavRef"></headerNav><div click"showRef" ref"buttonRef">refbutton</div>使用ref方法const后面的命名需要跟页面的ref值一样 const buttonRef ref(buttonRef) cons…...

TMC2226超静音步进电机驱动控制模块

目前已经使用TMC2226量产超过20K,发现在静音方面做的还是很不错。 一、TMC2226管脚定义说明 二、原理图及下载地址 一、TMC2226管脚定义说明 引脚编号类型功能OB11电机线圈 B 输出 1BRB2线圈 B 的检测电阻连接端。将检测电阻靠近该引脚连接到地。使用内部检测电阻时,将此引…...