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...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
