2023 ICPC 江西省赛K. Split

K. Split

time limit per test: 3 seconds

memory limit per test: 512 megabytes

You are given a positive integer n and a non-increasing sequence ai of length n , satisfying ∀i∈[1,n−1],a_{i}\geq a_{i+1}.

Then, you are given a positive integer m, which represents the total number of operations.

There are two types of operations. The first type gives an integer x satisfying 1<x<n and changes a_{x} to a_{x-1}+a_{x+1}-a_{x}.

The second type is query operation and gives an integer k . Assuming the sequence is divided into k segments, and the length of each segment must be at least 1. The value of a segment is defined as the difference between the maximum element and the minimum element of the segment. You should print the mininum sum of the values of the k segments for all possible ways to divide the sequence into k segments.

Specifically, for each operation, you will be given the type of the operation first. If it is 0, it means the first type of operation, and if it is 1, it means the second type of operation. For the first type of operation, you will then be given a positive integer x. For the second type of operation, you will then be given a positive integer k.

Input

The first line contains a positive integer nn (3≤n≤10^{6}), representing the length of the sequence.

The second line contains nn positive integers a1,a2,...,an (1≤ai≤10^{9}).

The third line contains a positive integer mm (1≤m≤10^{6}), representing the total number of operations.

Next mm lines, each line containing either "0 x" (1<x<n) or "1 k" (1≤k≤n), denoting an operation.

Output

Print q lines where the i-th line contains one integer — the answer for the i-th query operation.

Example

Input

5
30 20 18 13 2
3
1 2
0 3
1 3

Output

17
7

【思路分析】

差分。显然本题答案为整序列最大值-整序列最小值-(k-1)个最大差分和,对于操作1,显然不会影响差分数组最大k个数的取值,仅会使差分数组中相邻元素改变顺序。那么我们sort差分数组,用后缀和记录差分和,那么对于每个操作2,我们只需要O(1)的时间复杂度。

由于需要sort,整体的时间复杂度为O(nlogn)。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <cstring>
#include <iomanip>
#include <set>
#include <queue>#define i64 long longusing namespace std;void solve() {i64 n;cin >> n;i64 a[n + 1];for (int i = 1; i <= n; ++i) cin >> a[i];i64 m, op, tmp;i64 diff[n - 1];for (int i = 1; i < n; ++i) diff[i - 1] = a[i] - a[i + 1];sort(diff, diff + n - 1);cin >> m;i64 suf[n], suff = 0;suf[n - 1] = 0;for (int i = n - 2; i >= 0; --i) {suf[i] = diff[i] + suff;suff = suf[i];}while (m--) {cin >> op >> tmp;if (op == 0) a[tmp] = a[tmp - 1] + a[tmp + 1] - a[tmp];else {i64 total = suf[n - tmp];cout << a[1] - a[n] - total << endl;}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;
//    cin >> t;while (t--) {solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/416462.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

传统CV算法——背景建模算法介绍

帧差法 由于场景中的目标在运动&#xff0c;目标的影像在不同图像帧中的位置不同。该类算法对时间上连续的两帧图像进行差分运算&#xff0c;不同帧对应的像素点相减&#xff0c;判断灰度差的绝对值&#xff0c;当绝对值超过一定阈值时&#xff0c;即可判断为运动目标&#xf…

HarmonyOS开发实战( Beta5版)小程序场景性能优化开发指导

简介 小程序是一种轻量级的应用&#xff0c;它不需要下载、安装即可使用&#xff0c;用户可以通过扫描二维码或者搜索直接打开使用。小程序运行在特定的平台上&#xff0c;平台提供了小程序的运行环境&#xff08;运行容器&#xff09;和一些基础服务&#xff08;小程序API&am…

Linux学习笔记5 值得一读,Linux(ubuntu)软件管理,搜索下载安装卸载全部搞定!(上)

本文记录Ubuntu操作系统的软件包管理。 一、背景 整个Linux系统就是大大小小的软件包构成的&#xff0c;在linux系统中&#xff0c;软件的管理非常重要&#xff0c;与其他操作系统不同&#xff0c;linux的软件包管理比较复杂&#xff0c;有时还需要处理软件包之间的冲突。本文…

【电池专题】软包电池封装工序

铝塑膜成型工序冲坑 铝塑膜成型工序,软包电芯可以根据客户的需求设计成不同的尺寸,当外形尺寸设计好后,就需要开具相应的模具,使铝塑膜成型。 成型工序也叫作冲坑,顾名思义,就是用成型模具在加热的情况下,在铝塑膜上冲出一个能够装卷芯的坑,具体的见下图。 …

使用VM创建centos7环境

目录 1、安装VMware Workstation1.1安装VMware Workstation pro 161.2激活VMware Workstation pro 16 2. 创建centos7虚拟机2.1 点击创建新的虚拟机2.2 配置iso镜像2.3开启虚拟机&#xff0c;安装centos7系统 3. 配置网络方法1&#xff1a;方法2&#xff1a;配置静态IP地址 4. …

js逆向--绕过debugger(一)

js逆向--绕过debugger 一、禁用断点二、一律不在此处暂停三、文件替换四、安装最新版火狐浏览器一、禁用断点 首先说明,以下所说的任意一种方法并不适用于所有情况,需要灵活使用。以网站(https://antispider8.scrape.center/page/1)为例,在开发者工具调试区点击停用断点按…

六、桥接模式

桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式&#xff0c;旨在将抽象与实现分离&#xff0c;使得两者可以独立变化。通过使用桥接模式&#xff0c;可以避免在多个维度上进行继承&#xff0c;降低代码的复杂度&#xff0c;从而提高系统的可扩展性。 组成…

STM32常用C语言知识总结

目录 一、引言 二、C 语言基础 1.数据类型 2.变量与常量 3.控制结构 4.数组与指针 5.字符串 6. extern变量声明 7.内存管理 三、STM32 中的 C 语言特性 1.位操作 2.寄存器操作 一、引言 STM32 作为一款广泛应用的微控制器&#xff0c;其开发离不开 C 语言的支持。C …

若依系统的学习

若依环境 介绍 ‌若依是一款快速开发平台(低代码)&#xff0c;用于快速构建企业级后台管理系统&#xff0c;它提供了许多常用的功能模块和组件&#xff0c;包括权限管理、代码生成、工作流、消息中心等 官方地址: https://www.ruoyi.vip/ ‌基于Spring Boot和Spring Cloud‌…

vue axios发送post请求跨域解决

跨越解决有两种方案&#xff0c;后端解决&#xff0c;前端解决。后端解决参考Django跨域解决-CSDN博客 该方法之前试着可以的&#xff0c;但是复制到其他电脑上报错&#xff0c;所以改用前端解决 1、main.js做增加如下配置 import axios from axios Vue.prototype.$axios a…

入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)

前言 链表&#xff08;Linked List&#xff09;是一种线性数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含两个部分&#xff1a;存储数据的部分和指向下一个节点的指针&#xff08;或引用&#xff09;。链表的结构使得它能够动态地增长和收缩&#xff0c;适合…

【c++】常量周边之const应用:常变量

【c】常量周边&#xff1a;常量概念及定义 承接上文&#xff0c;我们学习了常量的基础知识&#xff0c;在此基础上&#xff0c;本篇文章对于宏定义 #define 和常量 const进行深入学习。 目录 #define 预处理器 const:在常量方面应用 使用技巧 const与指针的结合 const 与 …

我的电脑/资源管理器里无法显示新硬盘?

前情提要 我新&#xff01;买了一个京东京造的SATA3硬盘&#xff0c;一个绿联的SATA3转USB读取 现在我的电脑里只能显示我本地的C盘和D盘&#xff0c;不能显示这个接入的SATA盘。 系统环境&#xff1a;windows11 问题描述 在我的电脑里&#xff0c;只能看到我原本的C和D&…

民宿酒店预订系统V1.0.8

多门店民宿酒店预订管理系统&#xff0c;快速部署属于自己民宿酒店的预订小程序&#xff0c;包含预订、退房、WIFI连接、吐槽、周边信息等功能。提供全部无加密源代码&#xff0c;支持私有化部署。 V1.0.8修复房间预订状态无法筛选的问题 修复房间预订状态无法筛选的问题 修复…

QtAV在windows下编译

官方编译参考 一、源代码下载 git执行操作&#xff1a; git clone https://github.com/wang-bin/QtAV.git cd QtAV && git submodule update --init二、依赖文件下载(ffmpeg) ffmpeg下载 下载完成后&#xff0c;拷贝到QtAV源代码目录&#xff0c;修改根目录名为ff…

MATLAB 计算凹凸多边形的面积(85)

MATLAB 计算凹凸多边形的面积(84) 一、算法介绍二、算法实现1.代码一、算法介绍 计算凹凸多边形的面积,并输出计算结果,可视化 二、算法实现 1.代码 % 设置多边形的顶点坐标 % 这里以一个五边形为例 x = [1, 3, 4

Windows 环境nginx安装使用及目录结构详解

一、 Windows 环境nginx安装及基本使用 1、下载 nginx-1.27.1 最新的主线版本 安装 nginx/Windows&#xff0c;请下载1.27.1最新的主线版本&#xff0c; nginx 的主线分支包含所有已知的修复程序。 2、 解压缩 nginx-1.27.1 版本 nginx/Windows 作为标准控制台应用程序&#x…

uniapp__微信小程序如何对比时间组件框选中框之后的时间大小

1、时间组件框选择时间 2、做判断 if (new Date(selectedDate) < new Date(this.startDate)) {uni.showToast({title: 结束时间不能早于起始时间,icon: none,duration: 2000});return;}console.log(new Date(selectedDate),new Date(this.endDate)); 3、打印出来的时间对比…

#QT 笔记一

重点&#xff1a;面试考试大概率涉及&#xff0c;需要不借助任何资料掌握。掌握&#xff1a;面试考试可能涉及&#xff0c;需要不借助任何资料掌握。熟悉&#xff1a;面试考试可能涉及&#xff0c;可以稍微参考资料掌握。了解&#xff1a;面试考试小概率涉及&#xff0c;面试拔…

【STM32+HAL库】---- 通用定时器PWM输出实现呼吸灯

硬件开发板&#xff1a;STM32G0B1RET6 软件平台&#xff1a;cubemaxkeilVScode1 新建cubemax工程 1.1 配置系统时钟RCC 1.2 配置定时器 找到LED所对应的引脚PA5&#xff0c;选择TIM2_CH1模式 在TIM2中&#xff0c;时钟源选择内部时钟Internal Clock&#xff0c;通道1选择PWM…