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...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
