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

蓝桥杯备赛-差分-重新排序

news 来源：原创 2025/8/22 10:53:11

问题描述

给定一个数组 AA 和一些查询 Li,RiLi,Ri, 求数组中第 LiLi 至第 RiRi 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

输入格式

输入第一行包含一个整数 nn 。

第二行包含 nn 个整数 A1,A2,⋯,AnA1,A2,⋯,An, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数 mm 表示查询的数目。

接下来 mm 行, 每行包含两个整数 Li、RiLi、Ri, 相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

样例输出

样例说明

原来的和为 6+14=206+14=20, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 10+14=2410+14=24, 增加了 4。

评测用例规模与约定

对于 30%30% 的评测用例， n,m≤50n,m≤50;

对于 50%50% 的评测用例, n,m≤500n,m≤500;

对于 70%70% 的评测用例, n,m≤5000n,m≤5000;

对于所有评测用例, 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤1061≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤106 。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//计算每个位置的查询次数，查询次数最多的放最大的数字
//注意查询和要用long long
//差分--对于一段区间的操作--先在差分数组上做标记--再利用a[i]=a[i-1]+d[i]---重置a数组
//cha是d的前缀和数组，d是cha的差分数组
int main() {int n;cin >> n;vector<int> a(n + 5, 0);vector<int> cha(n + 5, 0);vector<int> d(n + 5, 0);for (int i = 1; i <= n; i++) {cin >> a[i];}//初始化a数组int m;cin >> m;int l, r;for (int i = 1; i <= m; i++) {cin >> l >> r;d[l]++;d[r + 1]--;}//初始化差分数组for (int i = 1; i <= n; i++) {cha[i] = cha[i - 1] + d[i];}//更新cha数组long long sum1 = 0;long long sum2 = 0;for (int i = 1; i <= n; i++){sum1 += (long long)a[i] * cha[i];
//将 sum1 += a[i] * cha[i]; 改为 sum1 += (long long)a[i] * cha[i]; 原因在于数据类型的溢出问题。当 a[i] 和 cha[i] 的值较大时，a[i] * cha[i] 的结果可能会超出 int 类型的表示范围（int 通常是 32 位，范围是 -2^31 到 2^31 - 1）。}sort(a.begin() + 1, a.begin() + 1 + n);//从大到小sort(cha.begin() + 1, cha.begin() + 1 + n);for (int i = 1; i <= n; i++) {sum2 += (long long)a[i] * cha[i];}cout << sum2 - sum1;return 0;
}

前缀和与差分图文并茂超详细整理（全网最通俗易懂）-CSDN博客

蓝桥杯备赛-差分-重新排序

问题描述给定一个数组 AA 和一些查询 Li,RiLi,Ri, 求数组中第 LiLi 至第 RiRi 个元素之和。小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少? 输入格式输…...

编程日记 2025/8/22 10:53:11

①Modbus TCP转Modbus RTU/ASCII网关同步采集无需编程高速轻松组网

Modbus TCP转Modbus RTU/ASCII网关同步采集无需编程高速轻松组网https://item.taobao.com/item.htm?ftt&id784749793551 MODBUS TCP 通信单元 MODBUS TCP 转 RS485 MS-A1-50X1 系列概述 MS-A1-50X1 系列概述 MS-A1-50X1系列作为MODBUS TCP通信的服务器进行动作。可通…...

编程日记 2025/8/22 10:40:18

2025年四川烟草工业计算机岗位备考详细内容

四川烟草工业计算机岗位备考详细内容（持续更新） 文章目录四川烟草工业计算机岗位备考详细内容（持续更新）一、计算机基础（一）计算机发展与组成计算机发展历程计算机系统组成软件系统 （二&#x…...

编程日记 2025/8/21 17:52:51

Git 设置全局代理

Git 设置全局代理或项目代理 git config： 全局配置，设置git代理服务器 # 设置 HTTP 代理 git config --global http.proxy http://127.0.0.1:7897# 设置 HTTPS 代理 git config --global https.proxy http://127.0.0.1:7897# 设置所有协议的代理&…...

编程日记 2025/8/22 2:09:27

【Java开发指南 | 第三十四篇】IDEA没有Java Enterprise——解决方法

读者可订阅专栏：Java开发指南 |【CSDN秋说】文章目录 1、新建Java项目2、单击项目名，并连续按两次shift键3、在搜索栏搜索"添加框架支持"4、勾选Web应用程序5、最终界面6、添加Tomcat 1、新建Java项目 2、单击项目名，并连续按两次…...

编程日记 2025/8/22 10:53:11

ROS实践（二）构建Gazebo机器人模型文件urdf

目录一、基础语法 1. urdf文件组成 2. robot根标签 3. link 和 joint标签 4. sensor标签二、实验：使用launch文件启动rviz查看机器人模型 1. 编写机器人模型的urdf文件。 2. 编写launch文件。 3. 运行launch，查看效果。 URDF（Unifi…...

编程日记 2025/8/21 21:25:40

论文阅读-秦汉时期北方边疆组织的空间互动模式与直道的定位（中国）

论文英文题目：A spatial interaction model of Qin-Han Dynasty organisation on the northern frontier and the location of the Zhidao highway (China) 发表于：journal of archaeological science，影响因子：3.030 论文主要是…...

编程日记 2025/8/22 10:40:18

【MySQL_04】数据库基本操作（用户管理--配置文件--远程连接--数据库信息查看、创建、删除）

文章目录一、MySQL 用户管理1.1 用户管理1.11 mysql.user表详解1.12 添加用户1.13 修改用户权限1.14 删除用户1.15 密码问题二、MySQL 配置文件2.1 配置文件位置2.2 配置文件结构2.3 常用配置参数三、MySQL远程连接四、数据库的查看、创建、删除4.1 查看数据库4.2 创建、删除…...

编程日记 2025/8/21 22:28:02

设计模式之建造者模式：原理、实现与应用

引言建造者模式（Builder Pattern）是一种创建型设计模式，它通过将复杂对象的构建过程分解为多个简单的步骤，使得对象的创建更加灵活和可维护。建造者模式特别适用于构建具有多个组成部分的复杂对象。本文将深入探讨建造者模式的原…...

编程日记 2025/8/22 10:51:04

2025最新群智能优化算法：山羊优化算法（Goat Optimization Algorithm, GOA）求解23个经典函数测试集，MATLAB

一、山羊优化算法山羊优化算法（Goat Optimization Algorithm, GOA）是2025年提出的一种新型生物启发式元启发式算法，灵感来源于山羊在恶劣和资源有限环境中的适应性行为。该算法旨在通过模拟山羊的觅食策略、移动模式和躲避寄生虫的能力&…...

编程日记 2025/8/22 10:49:00

Apache Log4j 2

目录 1. Apache Log4j 2 简介 1.1 什么是Log4j 2？ 1.2 Log4j 2 的主要特性 2. Log4j 2 的核心组件 2.1 Logger 2.2 Appender 2.3 Layout 2.4 Filter 2.5 Configuration 3. Log4j 2 的配置 4. Log4j 2 的使用示例 4.1 Maven 依赖 4.2 示例代码 4.3 输出…...

编程日记 2025/8/20 22:59:06

ArcGIS Pro字段编号相关代码

一、引言在地理信息系统（GIS）的数据管理与分析中，字段操作是不可或缺的一环。 SHP文件作为常见的地理数据存储格式，其字段的灵活运用对于数据的组织、展示和分析具有重要意义。在实际工作中，常常需要对字段进行编…...

编程日记 2025/8/22 10:46:53

ubuntu22.04机器人开发环境配置

1. ros2环境配置（humble） #配置源 # https://docs.ros.org/en/humble/Installation/Ubuntu-Install-Debs.html sudo apt install software-properties-common sudo add-apt-repository universe sudo apt update && sudo apt install curl -y# …...

编程日记 2025/8/22 10:42:30

万字深度剖析——JS数据结构（上）

数组本质是对象，键就是索引，值就是元素。 push /unshift 在数组最后/最前添加 pop /shift 把数组最后/最前的元素删除,返回的是被删除的元素 splice(0,2，5)从第0给位置开始删除2个元素，并添加一个元素数组自带的…...

编程日记 2025/8/19 15:51:17

golang dlv调试工具

golang dlv调试工具在goland2022.2版本中调试go程序报错 WARNING: undefined behavior - version of Delve is too old for Go version 1.20.7 (maximum supported version 1.19) 即使你go install了新的dlv也无济于事分析得出Goland实际使用的是 Goland安装目录下dlv 例…...

编程日记 2025/8/22 10:40:18

【算法 C/C++】二维前缀和

2025 - 03 - 08 - 第 70 篇 Author: 郑龙浩 / 仟濹【二维前缀和】文章目录前缀和与差分 - 我的博客前缀和(二维)1 基本介绍(1) **sum[i][j] 表示什么？？？**(2) **前缀和怎么求？？？计算 sum[i][j]&#xf…...

编程日记 2025/8/21 12:33:36

如何使用postman来测试接口

一、postman的介绍与下载可参考： https://blog.csdn.net/freeking101/article/details/80774271 二、api获取网站阿里云API应用市场地址：云市场_镜像市场_软件商店_建站软件_服务器软件_API接口_应用市场 - 阿里云三、具体测试过程可模拟浏览…...

编程日记 2025/8/16 11:57:55

olmOCR：高效精准的 PDF 文本提取工具

在日常的工作和学习中，是否经常被 PDF 文本提取问题困扰？例如： 想从学术论文 PDF 中提取关键信息，却发现传统 OCR 工具识别不准确或文本格式混乱？需要快速提取商务合同 PDF 中的条款内容，却因工具不给力而…...

编程日记 2025/8/22 10:46:53

Vue项目通过内嵌iframe访问另一个vue页面，获取token适配后端鉴权(以内嵌若依项目举例)

1. 改造子Vue项目进行适配(ruoyi举例) (1) 在路由文件添加需要被外链的vue页面配置 // 若依项目的话是 router/index.js文件 {path: /contrast,component: () > import(/views/contrast/index),hidden: true },(2) 开放白名单 // 若依项目的话是 permission.js 文件 cons…...

编程日记 2025/8/19 23:11:57

请谈谈 HTTP 中的重定向，如何处理 301 和 302 重定向？

HTTP重定向深度解析：301与302的正确使用姿势一、重定向本质解析重定向就像快递员送快递时发现地址变更，新地址会写在包裹单的"改派地址"栏。浏览器收到3xx状态码时，会自动前往Location头指定的新地址。常用状态码对比&…...

编程日记 2025/8/22 10:51:05

隧道定向号角喇叭为隧道安全保驾护航

隧道广播系统的搭建：科技赋能，打造安全高效的隧道环境。隧道作为现代交通网络的重要组成部分，其安全管理和信息传递的效率直接关系到整个交通系统的运行。然而，隧道环境的特殊性——封闭、狭窄、回声干扰多，使得传统的…...

编程日记 2025/8/22 10:38:41

RuleOS：区块链开发的“破局者”，开启Web3新纪元

RuleOS：区块链开发的“破冰船”，驶向Web3的星辰大海在区块链技术的浩瀚宇宙中，一群勇敢的探索者正驾驶着一艘名为RuleOS的“破冰船”，冲破传统开发的冰层，驶向Web3的星辰大海。这艘船，正以一种前所未有的姿…...

编程日记 2025/8/22 10:46:52

C#程序结构及基本组成说明

C# 程序的结构主要由以下几个部分组成，以下是对其结构的详细说明和示例： 1. 基本组成部分命名空间 (Namespace) 用于组织代码，避免命名冲突。通过 using 引入其他命名空间。 using System; // 引入 System 命名空间类 (Class) C# 是面向对象的语言，所有代码必须定义在类或…...

编程日记 2025/8/22 10:36:40

Django与数据库

我叫补三补四，很高兴见到大家，欢迎一起学习交流和进步今天来讲一讲alpha策略制定后的测试问题 mysql配置 Django模型体现了面向对象的编程技术，是一种面向对象的编程语言和不兼容类型能相互转化的编程技术，这种技术也叫ORM&#…...

编程日记 2025/8/22 10:49:01

力扣热题 100：二叉树专题进阶题解析（后7道）

系列文章目录力扣热题 100：哈希专题三道题详细解析(JAVA) 力扣热题 100：双指针专题四道题详细解析(JAVA) 力扣热题 100：滑动窗口专题两道题详细解析（JAVA） 力扣热题 100：子串专题三道题详细解析(JAVA) 力…...

编程日记 2025/8/22 10:40:17

Linux——system V共享内存

共享内存区是最快的IPC(进程内通信)形式，不再通过执行进入内核的系统调用来传递彼此的数据 1.共享内存的原理 IPC通信的本质是让不同的进程先看到同一份资源，然后再进行通信，所以想要通过共享内存进行通信，那么第一步一定是让两个…...

编程日记 2025/8/16 9:06:17

【C语言】指针篇

目录 C 语言指针概述指针的声明和初始化声明指针初始化指针指针的操作解引用操作指针算术运算指针的用途动态内存分配作为函数参数指针与数组数组名作为指针通过指针访问数组元素指针算术和数组数组作为函数参数指针数组和数组指针指针数组数组指针函数指针函数指针的定义和…...

编程日记 2025/8/21 11:13:34

XGBoost介绍

XGBoost：是eXtreme Gradient Boosting(极端梯度提升)的缩写，是一种强大的集成学习(ensemble learning)算法，旨在提高效率、速度和高性能。XGBoost是梯度提升(Gradient Boosting)的优化实现。集成学习将多个弱模型组合起来，形成一个…...

编程日记 2025/8/18 3:03:52

力扣：找到一个数字的 K 美丽值（C++）

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的子字符串数目： 子字符串长度为 k 。子字符串能整除 num 。给你整数 num 和 k ，请你返回 num 的 k 美丽值。注意： 允许有前缀 0 。0 不能整除任何值。一个子字符串是一个字符串里…...

编程日记 2025/8/16 9:57:06

数据结构：有序表的合并

前文介绍了《有序表的插入》，本文介绍有序表的合并。这两种对有序表的操作，是数据结构中常考的内容，特别是在 408 考卷中，在算法设计的题目中，有可能会考查对有序表的操作。那么，这两篇文章中的方法就是能够…...

编程日记 2025/8/16 11:40:41

AI写论文提示词指令大全，快速写论文

目录一、十大学术写作提示词1、研究主题2、研究问题3、论文架构4、学术论证5、文献关键要素6、专业文本可读性转换7、学术语言规范化8、提高语言准确性9、多维度、深层论证10、优化文本结构二、快速写论文提示词1、确认研究选题2、整理相关资料3、快速完成论文大纲4、整合文献…...

编程日记 2025/8/21 9:56:45

物联网IoT系列之MQTT协议基础知识

文章目录物联网IoT系列之MQTT协议基础知识物联网IoT是什么？什么是MQTT？为什么说MQTT是适用于物联网的协议？MQTT工作原理核心组件核心机制 MQTT工作流程1. 建立连接2. 发布和订阅3. 消息确认4. 断开连接 MQTT工作流程图MQTT在物联网中的应用 …...

编程日记 2025/8/21 7:00:35

【从零开始学习计算机科学】计算机组成原理（七）存储器与存储器系统

【从零开始学习计算机科学】计算机组成原理（七）存储器与存储器系统存储器存储器相关概念存储器分类存储器系统存储器性能指标存储器层次概述程序访问的局部性原理SRAM存储器存储器的读写周期DRAM存储器DRAM控制器高性能的主存储器存储器扩展只读存储器ROM光擦可编程只读存储…...

编程日记 2025/8/16 9:57:25

ctf-WEB: 关于 GHCTF Message in a Bottle plus 与 Message in a Bottle 的非官方wp解法

Message in a Bottle from bottle import Bottle, request, template, runapp Bottle()# 存储留言的列表 messages [] def handle_message(message):message_items "".join([f"""<div class"message-card"><div class"me…...

编程日记 2025/8/18 22:33:39

Java集合_八股场景题

Java集合在Java开发中，集合框架是面试和实际开发中非常重要的内容。以下是一些常见的Java集合八股文问题和场景题，以及详细答案和示例代码。 1. Java集合框架的结构是什么？ 答案： Java集合框架主要分为三大接口：Col…...

编程日记 2025/8/20 21:52:08

Scaled_dot_product_attention(SDPA)使用详解

在学习huggingFace的Transformer库时，我们不可避免会遇到scaled_dot_product_attention(SDPA)这个函数，它被用来加速大模型的Attention计算，本文就详细介绍一下它的使用方法，核心内容主要参考了torch.nn.functional中该函数的注释…...

编程日记 2025/8/19 20:21:25

SpringBoot（一）--搭建架构5种方法

目录一、⭐Idea从spring官网下载打开 2021版本idea 1.打开创建项目 2.修改pom.xml文件里的版本号 2017版本idea 二、从spring官网下载再用idea打开三、Idea从阿里云的官网下载打开编辑四、Maven项目改造成springboot项目五、从阿里云官网下载再用idea打开 Spri…...

编程日记 2025/8/19 19:45:09

初识大模型——大语言模型 LLMBook 学习（一）

1. 大模型发展历程 🔹 1. 早期阶段（1950s - 1990s）：基于规则和统计的方法代表技术： 1950s-1960s：规则驱动的语言处理早期的 NLP 主要依赖基于规则的系统，如 Noam Chomsky 提出的生成语法&…...

编程日记 2025/8/18 16:49:52

Array and string offset access syntax with curly braces is deprecated

警告信息 “Array and string offset access syntax with curly braces is deprecated” 是 PHP 中的一个弃用警告（Deprecation Notice），表明在 PHP 中使用花括号 {} 来访问数组或字符串的偏移量已经被标记为过时。背景在 PHP 的早期版本…...

编程日记 2025/8/16 9:59:57

27. Harmonyos Next仿uv-ui 组件NumberBox 步进器组件禁用状态

温馨提示：本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦！ 文章目录 1. 组件介绍2. 效果展示3. 禁用状态设置3.1 整体禁用3.2 输入框禁用3.3 长按禁用 4. 完整示例代码5. 知识点讲解5.1 禁用状态属性5.2 禁用…...

编程日记 2025/8/20 8:56:40

Java高频面试之集合-08

hello啊，各位观众姥爷们！！！本baby今天来报道了！哈哈哈哈哈嗝🐶 面试官：详细说说CopyOnWriteArrayList CopyOnWriteArrayList 详解 CopyOnWriteArrayList 是 Java 并发包（java.util…...

编程日记 2025/8/20 14:40:47

做到哪一步才算精通SQL

做到哪一步才算精通SQL-Structured Query Language 数据定义语言 DDL for StructCREATE：用来创建数据库、表、索引等对象ALTER：用来修改已存在的数据库对象DROP：用来删除整个数据库或者数据库中的表TRUNCATE：用来删除表中所有的行…...

编程日记 2025/8/16 9:56:44

SpringAI介绍及本地模型使用方法

博客原文地址前言 Spring在Java语言中一直稳居高位，与AI的洪流碰撞后也产生了一些有趣的”化学反应“，当然你要非要说碰撞属于物理反应也可以， 在经历了一系列复杂的反应方程后，Spring家族的新成员——SpringAI，就…...

编程日记 2025/8/22 2:09:19

空指针异常的触发

面向对象分析： 当你要吃饭，饭是对象，提供吃饭这个功能，所以饭为null时，你去调吃饭这个功能，就是去操作饭这个抽象模型，但这个模型是null，就是空指针异常了，但如果有了饭…...

编程日记 2025/8/16 13:07:19

尚硅谷爬虫note15n

1. 多条管道多条管道开启（2步）： (1)定义管道类 （2）在settings中开启管道在pipelines中： import urllib.request # 多条管道开启 #(1)定义管道类 #（2）在setti…...

编程日记 2025/8/20 11:59:10

基于SSM+Vue的汽车维修保养预约系统+LW示例

1.项目介绍系统角色：管理员、员工、用户功能模块：用户管理、员工管理、汽车类型管理、项目类型管理、维修/预约订单管理、系统管理、公告管理等技术选型：SSM，vue（后端管理web），Layui&#xff…...

编程日记 2025/8/20 11:49:50

【商城实战(13)】购物车价格与数量的奥秘

【商城实战】专栏重磅来袭！这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建，运用 uniapp、Element Plus、SpringBoot 搭建商城框架，到用户、商品、订单等核心模块开发，再到性能优化、安全加固、多端适配&#xf…...

编程日记 2025/8/16 9:56:37

在线json转ArkTs-Harmonyos

轻松将 JSON 数据转换为类型安全的 ArkTs 接口。快速准确地生成代码，提升开发效率，告别手动编写，让您的开发流程更加流畅！ gotool...

编程日记 2025/8/16 12:47:20

Cannot resolve symbol ‘view‘ Androidstudio报错解决办法

报错原因出现 Cannot resolve symbol view 错误是因为代码中的 view 变量未正确定义或不在当前作用域内。以下是常见场景和解决方法： 场景 1：在点击事件监听器中获取 view 如果代码在 OnClickListener 的 onClick 方法中，view 是方法的参…...

编程日记 2025/8/20 19:07:10

三级缓存架构

三级缓存架构是一种通过分层缓存设计来优化系统性能、降低数据库负载、提高数据访问效率的解决方案，尤其适用于高并发、高吞吐量的业务场景（如电商、社交平台、实时推荐等）。其核心思想是通过多级缓存逐层过滤请求，减少对底层存储…...

编程日记 2025/8/18 18:43:24

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

相关文章：