AtCoder ABC324G 启发式合并
题意
传送门 AtCoder ABC324G Generate Arrays
题解
逆则操作顺序考虑,可以看作至多 n n n 个联通分量不断合并的过程,此时使用启发式合并,即规模较小的连通分量向规模较大的连通分量合并,以单个元素合并为基本运算,则基本运算次数为 O ( n log n ) O(n\log n) O(nlogn)。
使用 std::set 分别维护以索引和值为关键字的集合,每次分裂出较小的分量即可。关于如何计算出所分裂两个分量的规模的问题,对于以索引为关键字的平衡树,操作直接给出了右侧元素的相对位置 x i x_i xi,则规模可以直接计算;而对于以值为关键字的平衡树,操作仅给出了需要大于的值 x i x_i xi,此时平衡树无法直接计算相对位置,那么可以二分出第一个满足 v a l > x i val>x_i val>xi 的位置,使用两个迭代器分别不断左右移动直到边界,则在操作数限制为较小分量规模大小的约束下,计算出了分裂的两个分量的规模。总时间复杂度 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}int q;cin >> q;using pst = set<pair<int, int>>;vector<pst> pos(q + 1), val(q + 1);for (int i = 0; i < n; ++i) {pos[0].insert({i, a[i]});val[0].insert({a[i], i});}for (int i = 1; i <= q; ++i) {int t, s, x;cin >> t >> s >> x;auto change = [](int a, int b, pst &_pos, pst &_val, pst &pos, pst &val) {if (a > b) {for (int j = 0; j < b; ++j) {auto [k, a] = *prev(_pos.end());_pos.erase({k, a});_val.erase({a, k});pos.insert({k, a});val.insert({a, k});}} else {swap(_pos, pos);swap(_val, val);for (int j = 0; j < a; ++j) {auto [k, a] = *pos.begin();pos.erase({k, a});val.erase({a, k});_pos.insert({k, a});_val.insert({a, k});}}};auto &_pos = pos[s];auto &_val = val[s];int a = -1, b = -1;if (t == 1) {int _n = _pos.size();if (x < _n) {a = x, b = _n - x;} else {a = _n, b = 0;}change(a, b, _pos, _val, pos[i], val[i]);} else {int _n = _val.size();auto it = _val.upper_bound({x, 1e9});if (it == _val.end()) {a = _n, b = 0;} else if (it == _val.begin()) {a = 0, b = _n;} else {a = b = 0;auto it2 = prev(it);for (;;) {a += 1;b += 1;if (it2 == _val.begin()) {b += _n - 2 * a;break;}it2 = prev(it2);it = next(it);if (it == _val.end()) {a += _n - 2 * a;break;}}}change(a, b, _val, _pos, val[i], pos[i]);}cout << (int)pos[i].size() << '\n';}return 0;
}
相关文章:
AtCoder ABC324G 启发式合并
题意 传送门 AtCoder ABC324G Generate Arrays 题解 逆则操作顺序考虑,可以看作至多 n n n 个联通分量不断合并的过程,此时使用启发式合并,即规模较小的连通分量向规模较大的连通分量合并,以单个元素合并为基本运算࿰…...
SpringBootCMS漏洞复现分析
SpringBootCMS,极速开发,动态添加字段,自定义标签,动态创建数据库表并crud数据,数据库备份、还原,动态添加站点(多站点功能),一键生成模板代码,让您轻松打造自己的独立网站ÿ…...
iOS- flutter flavor 多环境Configurations配置
一、点击PROJECT的Runner,选择Info选项,在Configurations下方的号添加不同环境的配置,如下图: 二、选择TAGETS的Runner项目,选择Build Settings选项,在输入框输入package,为不同环境配置相应的…...
【PyTorchTensorBoard实战】GPU与CPU的计算速度对比(附代码)
0. 前言 按照国际惯例,首先声明:本文只是我自己学习的理解,虽然参考了他人的宝贵见解,但是内容可能存在不准确的地方。如果发现文中错误,希望批评指正,共同进步。 本文基于PyTorch通过tensor点积所需要的时…...
npm 常用指令总结
1. 初始化包 一个存放了代码的文件夹,如果里面有 package.json 文件,则可以把这个文件夹称之为包。 npm init -y 注意: 由于包名不能有中文,不能有大写,不能和未来要下载的包重名. 所以我们快速初始化包时,我们的文件夹也不能违反前面说的规则.(因为默认会将文件夹的名称,作…...
布朗大学发现GPT-4存在新问题,可通过非常见语言绕过限制
🦉 AI新闻 🚀 布朗大学发现GPT-4存在新漏洞,可通过非常见语言绕过限制 摘要:布朗大学计算机科学研究人员发现了OpenAI的GPT-4存在新漏洞,利用不太常见的语言如祖鲁语和盖尔语可以绕过各种限制。研究人员测试了GPT-4对…...
ESP32网络编程-TCP客户端数据传输
TCP客户端数据传输 文章目录 TCP客户端数据传输1、IP/TCP简单介绍2、软件准备3、硬件准备4、TCP客户端实现本文将详细介绍在Arduino开发环境中,实现一个ESP32 TCP客户端,从而达到与TCP服务器数据交换的目标。 1、IP/TCP简单介绍 Internet 协议(IP)是 Internet 的地址系统,…...
微信小程序入门级
目录 一.什么是小程序? 二.小程序可以干什么? 三.入门使用 3.1. 注册 3.2. 安装 3.3.创建项目 3.4.项目结构 3.5.应用 好啦今天就到这里了,希望能帮到你哦!!! 一.什么是小程序? 微信小程…...
博客文档续更(二)
十五、博客前台模块-个人信息 1. 接口分析 进入个人中心的时候需要能够查看当前用户信息。请求不需要参数 请求方式 请求地址 请求头 GET /user/userInfo 需要token请求头 响应格式 {"code":200,"data":{"avatar":"头像的网络地址…...
Centos切换yum源
Centos切换yum源 常用命令 #查看内核/操作系统/CPU信息 uname -a #查看yum源 yum list repolist all切换步骤 1.备份yum源文件 cp -a /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.bak2.下载新的CentOS-Base.repo文件到/etc/yum.repos.d/目录下 …...
milvus和相似度检索
流程 milvus的使用流程是 创建collection -> 创建partition -> 创建索引(如果需要检索) -> 插入数据 -> 检索 这里以Python为例, 使用的milvus版本为2.3.x 首先按照库, python3 -m pip install pymilvus Connect from pymilvus import connections c…...
龙迅LT7911UXC 是一款高性能TYPE-C/DP/EDP转换四端口MIPI/LVDS的芯片,还支持图像处理
龙迅LT7911UXC 1.描述: LT7911UXC是一款用于VR/显示应用的高性能Type-C/DP1.4a到MIPI或LVDS芯片。HDCP RX作为 HDCP中继器的上游端,可以与其他芯片的HDCP TX协同工作,实现中继器的功能。对于DP1.4a 输入,LT7911UXC可以配置为1…...
TOR(Top of Rack)
TOR TOR(Top of Rack)指的是在每个服务器机柜上部署1~2台交换机,服务器直接接入到本机柜的交换机上,实现服务器与交换机在机柜内的互联。虽然从字面上看,Top of Rack指的是“机柜顶部”,但实际T…...
使用asp.net core web api创建web后台,并连接和使用Sql Server数据库
前言:因为要写一个安卓端app,实现从服务器中获取电影数据,所以需要搭建服务端代码,之前学过C#,所以想用C#实现服务器段代码用于测试,本文使用C#语言,使用asp.net core web api组件搭建服务器端&…...
LaTeX 公式与表格绘制技巧
LaTeX 公式与绘图技巧公式基本可以分为 单一公式单一编号单一公式按行编号单一公式多个子编号单一公式部分子编号分段公式现在给出各自的代码单一公式单一编号 公式1:equationaligned\begin{equation}\begin{aligned}a&bc\\b&a2\\c&b-3\end{aligned}\en…...
Spring Cloud--Nacos+@RefreshScope实现配置的动态更新
原文网址:Spring Cloud--NacosRefreshScope实现配置的动态更新_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍SpringCloud整合Nacos使用RefreshScope实现动态更新配置。 官网 Nacos Spring Cloud 快速开始 动态更新的介绍 动态更新的含义:修改应…...
Elasticsearch安装
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...
【JavaSE API 】生成随机数的2种方法:Random类和Math类的Random方法
生成随机数的两种方法 Random类和Math类的random方法都可以用来生成随机数 而Math类的random方法则是基于系统时间的伪随机数生成器,大于等于0.0小于1.0的随机double值范围[0,1)。例如: double num1 Math.random() * 5 4;//范围[4,9) Random类是基于种…...
微软和OpenAI正在开发AI芯片, 并计划下个月发布
今年初,Chat**引起了无数网友关注,一度成为了热门话题。这是由人工智能研究实验室OpenAI开发的一款聊天机器人模型,也称为一种人工智能(AI)技术驱动的自然语言处理工具。能够通过学习和理解人类的语言来进行对话&#…...
记一次Hbase2.1.x历史数据数据迁移方案
查看待迁移的表 list_namespace_tables vaas_dwm2. 制作待迁移表“DWM_TRIP_PART”的快照 snapshot vaas_dwm:DWM_TRIP_PART,dwm_trip_part_snapshot3. 统计待迁移表数据总数 hbase org.apache.hadoop.hbase.mapreduce.RowCounter vaas_dwm:DWM_TRIP_PART...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考
目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候,显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...
