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

差分(续前缀和)(含一维二维)

题目引入

开发商小 Q 买下了一条街,他想在这条街的一边盖房子。

街道可以抽象为一条数轴,而小 Q 只会在坐标在 1~n 的范围内盖房子。

首先,小 Q 将街上坐标在 1∼ 𝑛1∼ n 范围内的物体全部铲平。也就是说,在正式动工盖房子之前,1∼ 𝑛1∼ n 范围内是没有东西的。

小 Q 的盖房子技术出奇的烂,他每次只会在坐标从 l 到 r 的一段区间上砌一堵高为 h 厘米的墙。如果某个位置已经有墙了,那么他会将墙加高 h 厘米。

好吧小 Q 不得不承认自己不会盖房子只会砌墙。

小 Q 已经砌了 m 次墙了,整条街已经乱七八糟的了。

什么是差分

差分是前缀和的逆运算,也就是说,对差分数组就是计算前缀和数组的“原数组”,例如,差分数组为:【1, 2, 3, 4, 5】,前缀和数组就是【1, 3, 6, 10, 15】。

优势

我们可以把题目中的墙当成一个前缀和数组,因为小Q每砌墙一次,就会把一段区间的数值一起加上若干厘米。

比如说,原本墙数组为:1, 0, 3, 0, 0

那么差分数组就是:1, -1, 3, -3, 0

如果我们要将2~3加上1,我们只需改变差分数组:1, 0(加一), 3, -4(减一), 0,对应的墙就是(前缀和):1, 1, 4, 0, 0

所以我们更改时,只需建立一个差分数组,无需建立前缀和数组,输出时直接计算即可。

#include <bits/stdc++.h>
using namespace std;int main() {int n, m, c[500005];memset(c, 0, sizeof (c));cin >> n >> m;while (m--) {int l, r, h;cin >> l >> r >> h;// 把墙数组当成前缀和来看,并建立它的逆运算差分数组c[l] += h;c[r + 1] -= h;}for (int i = 1; i <= n; i++) {if (i != 1)cout << " ";c[i] += c[i - 1];cout << c[i];}cout << endl;return 0;
}

二维差分

大哈有一面 n * n 的广告墙,他往墙上贴 m 张广告,广告之间有些部分会相互重叠,问墙上的每个点上覆盖了几张广告?

这题其实也是差分,贴广告,一定时覆盖了一个区域,而这个区域一定是二维上连续的。

假设要把以(x1, y1)为左上角,以(x2, y2)为右下角的子矩阵加c,可以这样操作:

c[_x1][_y1]++;
c[_x1][_y2 + 1]--;
c[_x2 + 1][_y1]--;
c[_x2 + 1][_y2 + 1]++;

#include <bits/stdc++.h>
using namespace std;int c[3005][3005];int main() {memset(c, 0, sizeof (c));int n, m;cin >> n >> m;while (m--) {int _x1, _y1, _x2, _y2;cin >> _x1 >> _y1 >> _x2 >> _y2;c[_x1][_y1]++;c[_x1][_y2 + 1]--;c[_x2 + 1][_y1]--;c[_x2 + 1][_y2 + 1]++;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (j != 1)cout << " ";c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + c[i][j];cout << c[i][j];}cout << endl;}return 0;
}

相关文章:

差分(续前缀和)(含一维二维)

题目引入 开发商小 Q 买下了一条街&#xff0c;他想在这条街的一边盖房子。 街道可以抽象为一条数轴&#xff0c;而小 Q 只会在坐标在 1~n 的范围内盖房子。 首先&#xff0c;小 Q 将街上坐标在 1∼ &#x1d45b;1∼ n 范围内的物体全部铲平。也就是说&#xff0c;在正式动工盖…...

【STM32-HAL库】自发电型风速传感器(使用STM32F407ZGT6)(附带工程下载链接)

一、自发电型风速传感器介绍 自发电型风速传感器&#xff0c;也称为风力发电型风速传感器或无源风速传感器&#xff0c;是一种不需要外部电源即可工作的风速测量设备。这种传感器通常利用风力来驱动内部的发电机构&#xff0c;从而产生电能来供电测量风速的传感器部分。以下是自…...

【计算机毕业设计】springboot就业信息管理系统

就业信息管理系统 摘 要 随着信息化时代的到来&#xff0c;管理系统都趋向于智能化、系统化&#xff0c;就业信息管理系统也不例外&#xff0c;但目前国内仍都使用人工管理&#xff0c;市场规模越来越大&#xff0c;同时信息量也越来越庞大&#xff0c;人工管理显然已无法应对时…...

实用工具推荐---- PDF 转换

直接上链接&#xff1a;爱PDF |面向 PDF 爱好者的在线 PDF 工具 (ilovepdf.com) 主要功能如下&#xff1a; 全免费&#xff01;&#xff01;&#xff01;&#xff01;...

安宝特案例 | 某知名日系汽车制造厂,借助AR实现智慧化转型

案例介绍 在全球制造业加速数字化的背景下&#xff0c;工厂的生产管理与设备维护效率愈发重要。 某知名日系汽车制造厂当前面临着设备的实时监控、故障维护&#xff0c;以及跨地域的管理协作等挑战&#xff0c;由于场地分散和突发状况的不可预知性&#xff0c;传统方式已无法…...

RabbitMQ基本原理

一、基本结构 所有中间件技术都是基于 TCP/IP 协议基础之上进行构建新的协议规范&#xff0c;RabbitMQ遵循的是AMQP协议&#xff08;Advanced Message Queuing Protocol - 高级消息队列协议&#xff09;。 生产者发送消息流程&#xff1a; 1、生产者和Broker建立TCP连接&#…...

【NodeJS】npm、yarn、pnpm当前项目设置国内镜像源

全局设置镜像源&#xff0c;可以参考下这篇文章&#xff0c;还挺详细&#xff1a;《npm、yarn、pnpm 最新国内镜像源设置和常见问题解决》 临时设置镜像源&#xff1a;《npm永久或临时切换源》 有时候可能要同时多个开发项目&#xff0c;又不想修改全局的镜像源(具体场景…自行…...

25考研咨询周开启,西安电子科技大学是否改考408??

学长这几天帮大家问了西安电子科技大学是否会从833、834、953改考为408&#xff1f; 西电老师回复&#xff1a;根据上级文件要求&#xff0c;招生简章以及专业目录会在网上报名开始前公布&#xff0c;专业课不会又大变动&#xff01; 因为大家安心复习即可&#xff0c;保证今…...

git(1) -- 环境配置

1. 配置文件 编辑~/.gitconfig文件&#xff0c;内容如下。 [user]email xflming163.comname xflm [core]editor vim [color]diff autostatus autobranch autoui true [commit]template /home/xflm/configuser/git-commit.template [diff]tool bc4 [difftool]prompt …...

Windows安装Vim,并在PowerShell中直接使用vim

大家好啊&#xff0c;我是豆小匠。 这期介绍下怎么在windows的PowerShell上使用vim&#xff0c;方便在命令行里修改配置文件等。 先上效果图&#xff1a; 1、下载Vim GitHub传送门&#xff1a;https://github.com/vim/vim-win32-installer/releases 选择win-64的版本下载即可&…...

力扣(leetcode)每日一题 983 最低票价 |动态规划

983. 最低票价 题干 在一个火车旅行很受欢迎的国度&#xff0c;你提前一年计划了一些火车旅行。在接下来的一年里&#xff0c;你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车票有 三种不同的销售方式 &#xff1a; 一张 为期一天 的通…...

【漏洞复现】VEXUS多语言货币交易所存在未授权访问漏洞

漏洞描述 java后端,非常完整的一套交易所,UI前端做的也很漂亮,新增了交易跟单功能,前端pc+wap都是uniapp纯源码,前端源码node_modules环境已经安装好了,拿去直接编译就可以. 后端 前端 免责声明 技术文章仅供参考,任何个人和组织使用网络应当遵守宪法法律,遵守公共…...

基于SpringBoot+Vue+MySQL的个性化电影推荐

系统展示 用户前台界面 管理员后台界面 系统背景 随着在线影视平台的迅猛发展&#xff0c;用户对个性化电影推荐的需求日益增长。传统的电影推荐系统往往基于简单的热门排行或分类筛选&#xff0c;难以满足用户的个性化需求。因此&#xff0c;开发一个基于SpringBootVueMySQL的…...

ASP.NET MVC-异步发送post请求+文件下载

环境&#xff1a; win10, .NET 6.0 前端向后台传递string型变量 前端&#xff1a; function PasteSubmit() {// 获取某个input的值var inName document.getElementById("xx").value;// 获取某个元素的属性值var inSeq document.getElementById("xxx").g…...

Unity 2D RPG Kit 学习笔记

学习资料&#xff1a; B站教学视频&#xff1a;https://www.bilibili.com/video/BV1dC4y1o7A5?p1&vd_source707ec8983cc32e6e065d5496a7f79ee6 2D RPG Kit Documentation.pdf文档 1、2D RPG Kit Documentation文档 1.1、Scenes/TitleScreen 开始菜单工程 1.2、https://it…...

联想天逸100使用笔记

文章目录 配置整理过程锁定功能键怎么弄? 翻出好多年不用的老电脑&#xff0c;饱受折磨&#xff0c;做个笔记。 之前不是我在使用&#xff0c;本身配置就不高&#xff0c;还被装了各种流氓软件&#xff0c;卡的几乎动不了。 配置 老电脑配置不行&#xff1a; i3 5005U 4G内存…...

【AI知识点】嵌入向量(Embedding Vector)

嵌入向量&#xff08;Embedding Vector&#xff09;是通过嵌入函数&#xff08;Embedding Function&#xff09;将复杂、高维或稀疏数据&#xff08;如文本、图像、分类特征等&#xff09;映射到低维、稠密空间中表示的向量。这种向量表示保留了原始数据的语义或结构信息&#…...

github命令行管理工具推荐

GitHub 管理工具推荐 背景 在使用 GitHub 管理仓库时&#xff0c;需要在 Web 端创建远程仓库&#xff0c;在本地创建本地仓库&#xff0c;然后再用 git remote add origin url 进行关联。这个过程相对繁琐&#xff0c;而且还有优化的空间。如果频繁创建仓库&#xff0c;就更能…...

【React】react项目中的redux使用

1. store目录结构设计 2. react组件中使用store中的数据——useSelector 3. react组件中修改store中的数据——useDispatch 4. 示例 react-basic\src\store\moduels\counterStore.js import { createSlice } from reduxjs/toolkitconst counterStore createSlice({name: cou…...

AJAX JSON 实例

AJAX JSON 实例 引言 AJAX(Asynchronous JavaScript and XML)和JSON(JavaScript Object Notation)是现代Web开发中常用的技术。AJAX允许在不重新加载整个页面的情况下,与服务器交换数据和更新部分网页内容。JSON是一种轻量级的数据交换格式,易于人阅读和编写,同时也易…...

java8:hutool:httputil.post读取配置项中的url

如果HttpUtil.post是静态方法&#xff0c;无法直接访问非静态的Value注入的属性。有以下几种解决办法&#xff1a; 构造函数注入 1. 首先将配置项的值通过Value注入到类的成员变量&#xff0c;然后在构造函数中将这个值传递给一个静态变量。 import org.springframework.bean…...

Springboot结合RabbitMQ

pom.xml <!--AMQP依赖&#xff0c;包含RabbitMQ--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency>application.yaml spring:rabbitmq:host: 127.0.0.1u…...

UNIAPP 动态菜单实现方法

1. 封装tabbar组件&#xff0c;组件UI使用uview的tabbar allList 定义出全部的菜单 list 定义当前用户能看到的菜单使用 u-tabbar 渲染出来 list 2. 权限判断处理 3. 使用方式 在 tab 页&#xff0c;底部放入该 tab 组件&#xff0c;并设置当前回显的页面&#xff0c;这里使用…...

windows C++-使用任务和 XML HTTP 请求进行连接(一)

本文会演示如何将 IXMLHTTPRequest2 和 IXMLHTTPRequest2Callback 接口与任务结合使用&#xff0c;以将 HTTP GET 和 POST 请求发送至通用 Windows 平台 (UWP) 应用中的 Web 服务。 通过将 IXMLHTTPRequest2 与任务组合在一起&#xff0c;你可以编写通过其他任务编写的代码。 例…...

HTB:Oopsie[WriteUP]

目录 连接至HTB服务器并开启靶机 1.With what kind of tool can intercept web traffic? 2.What is the path to the directory on the webserver that returns a login page? 3.What can be modified in Firefox to get access to the upload page? 4.What is the acc…...

【JAVA高级】如何使用Redis加锁和解锁(一)、Lua脚本执行原理及流程

文章目录 加锁方法一&#xff1a;使用SETNX命令结合EXPIRE命令方法二&#xff1a;使用SET命令的扩展参数&#xff08;NX和PX&#xff09;方法三&#xff1a;使用Lua脚本 解锁方法一&#xff1a;简单删除key方法二&#xff1a;使用Lua脚本验证后删除key Lua脚本的执行原理&#…...

2024年使用宝塔面板轻松部署Java Web

以下是2024年最新图形化部署Java Web项目到CentOS系统的手把手教程&#xff1a; 一、准备工作 确保服务器环境&#xff1a;确保你的服务器已经安装了CentOS 7操作系统&#xff0c;并且已经安装了宝塔面板。如果还没有安装&#xff0c;可以参考之前的教程进行安装。下载Java W…...

闯关训练一:Linux基础

闯关任务&#xff1a;完成SSH连接与端口映射并运行hello_world.py 1.创建开发机 2.SSH连接 3. VS-Code 连接 选择 Linux 平台 &#xff0c;输入密码 &#xff0c;选择进入文件夹 4.端口映射 按照下文安装Docs pip install gradio 运行server.py import gradio as grdef …...

鸿蒙NEXT开发-ArkTS(基于最新api12稳定版)

注意&#xff1a;博主有个鸿蒙专栏&#xff0c;里面从上到下有关于鸿蒙next的教学文档&#xff0c;大家感兴趣可以学习下 如果大家觉得博主文章写的好的话&#xff0c;可以点下关注&#xff0c;博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…...

laravel延迟队列 取消未支付超时订单订单

1&#xff1a;生成待支付订单时&#xff0c;调用延迟队列 超过十五分钟未支付自动取消 use App\Jobs\endTask; use Illuminate\Support\Carbon; $resPost1 array("act" > "cy_order_cancel", "id" > $id); endTask::dispatch($resPos…...