P1903 [国家集训队] 数颜色 / 维护队列
带修改的莫队
带修改的莫队就是在基础莫队的基础上增加了一维属性,之前只需要维护l,r现在还需要维护一下时间t,排序还是先按照左端点块儿号排序,然后右端点块儿号排序,最后按时间排序。其它的都是差不多的。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define x first
//#define y second
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
const int mod = 1e9 + 7;
const int N = 1e6+ 10;
int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
int n, m, mc, mq, len;
int o[N], f[N], st[N], res;
// 结果 标记
struct query{ // 记录询问的列表int l, r, id, t;
}q[N];
struct modify{ // 记录修改操作的列表int x, y;
}c[N];inline int get(int a) // 得到块儿号
{return a / len;
}inline void add(int a) // 增加
{if(!st[a]) res ++;st[a] ++;
}inline void del(int a) // 删除
{st[a] --;if(!st[a]) res --;
}
bool cmp(query a, query b) // 排序
{int ai = get(a.l), aj = get(a.r);int bi = get(b.l), bj = get(b.r);if(ai != bi) return ai < bi; // 按左端点块儿号if(aj != bj) return aj < bj; // 按右端点块儿号return a.t < b.t; // 按时间
}inline void sovle()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> o[i];for(int i = 0; i < m; i ++){char op;int a, b;cin >> op >> a >> b;if(op == 'Q') mq ++, q[mq] = {a, b, mq, mc};else c[++ mc] = {a, b};}len = pow(n, 0.666); // 怎么分块儿,,,可以找一些大手子的博客看一下stable_sort(q + 1, q + mq + 1, cmp);int now = 0, l = 1, r = 0;for(int i = 1; i <= mq; i ++){int id = q[i].id, t = q[i].t;while(r < q[i].r) add(o[++ r]);while(r > q[i].r) del(o[r --]); // 更新右端点while(l < q[i].l) del(o[l ++]);while(l > q[i].l) add(o[-- l]); // 更新左端点while(now < t) // 更新时间{now ++;if(c[now].x <= r && c[now].x >= l) // 不在修改范围内,直接跳过{del(o[c[now].x]);add(c[now].y);}swap(o[c[now].x], c[now].y); // 交换两个颜色} while(now > t){if(c[now].x <= r && c[now].x >= l){del(o[c[now].x]);add(c[now].y);}swap(o[c[now].x], c[now].y);now --;}f[id] = res; // 记录结果}for(int i = 1; i <= mq; i ++){cout << f[i] << endl;}
}signed main(void)
{IOS;int t = 1;
// cin >> t;while(t --) sovle();return 0;
}
相关文章:
P1903 [国家集训队] 数颜色 / 维护队列
带修改的莫队 带修改的莫队就是在基础莫队的基础上增加了一维属性,之前只需要维护l,r现在还需要维护一下时间t,排序还是先按照左端点块儿号排序,然后右端点块儿号排序,最后按时间排序。其它的都是差不多的。 #include…...
uniapp 请求接口的方式
在UniApp中,我们可以使用多种方式来发送请求接口。以下是几种常用的方式: 1、使用unmireuest方法:uni.reuest是uniApp提供的原生AP,可以发送HTTP请,我们可以通过传递一个图对象来设置请求的参数,RL、请求方法GET/POST…...
怎么查看当前vue项目,要求的node.js版本
要查看当前 Vue 项目所需的 Node.js 版本,你可以查看项目根目录下的 package.json 文件中的 engines 属性。该属性定义了项目所需的 Node.js 版本范围。 例如,以下是一个示例 package.json 文件: {"name": "my-vue-project&…...
QT5自适应
//集成屏幕自适应功能 QApplication::setAttribute(Qt::AA_EnableHighDpiScaling); QCoreApplication::setAttribute(Qt::AA_UseHighDpiPixmaps); DEVMODE NewDevMode; //获取屏幕设置中的分辨率 EnumDisplaySettings(0, ENUM_CURRENT_SETTINGS, &NewDevMo…...
蓝桥杯官网练习题(日期问题)
题目描述 小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采…...
PDF文件解析
一、PDF文件介绍 PDF是英文Portable Document Format缩写,就是可移植的意思,它是以PostScript语言图象模型为基础,无论在哪种打印机上都可保证精确的颜色和准确的打印效果,PostScript咱也不懂,估计和SVG的原理差不多吧…...
初识微服务技术栈
认识微服务 随着互联网行业的发展,对服务的要求也越来越高,服务架构也从单体架构逐渐演变为现在流行的微服务架构,这些架构之间有怎样的差别呢? 导学: 了解微服务的优缺点;了解微服务架构的演变过程&am…...
windows 下运行正常,但是linux下报错 : Could not find or load main class
使用指令 "sed -i s/\r$// xxxxxxx.sh",将 .sh 文件中的 "\r" 全部替换成空白符,即可解决问题 转转:https://www.cnblogs.com/cmxbky1314/p/12096611.html...
MySQL 数据目录和 InnoDB 表空间补充知识:详细结构
1. 数据目录 在Ubuntu下,MySQL的数据目录为/var/lib/mysql 1.1 数据库在文件系统中的表示 (1)创建数据库时,会在数据目录下创建一个与数据库名同名的子目录。(除了information_schema这个系统数据外) &…...
移远EC600U-CN开发板 day02
1.QuecPythonLVGL显示图片 由于官方提供的显示图片函数使用失败,为了能在屏幕上显示图片,通过对出厂脚本的分析,成功使用LVGL显示图片 (1)代码 import lvgl as lv from tp import gt9xx from machine import LCD from machine import Pin …...
visual studio Python 配置QGIS(qgis)教程
visual studio Python 配置QGIS(qgis)教程 这个教程全网独一份啊,博主是自己摸索出来的。 visual studio Python 配置QGIS(qgis)环境一共分为两部: 第一步安装QGIS: 下载链接如下 https://www…...
第二证券:消费电子概念活跃,博硕科技“20cm”涨停,天龙股份斩获10连板
消费电子概念7日盘中再度拉升,到发稿,博硕科技“20cm”涨停,光大同创、波长光电涨超10%,易德龙、向阳科技、得润电子、天龙股份、同兴达等涨停。 博硕科技强势涨停,公司昨日在接受安排调研时表明,公司从上…...
petalinux 2022.2 在 ubantu18.04 下的安装
下载 Ubuntu下载: https://releases.ubuntu.com/18.04/ubuntu-18.04.6-desktop-amd64.iso petalinux 下载: https://www.xilinx.com/support/download/index.html/content/xilinx/en/downloadNav/embedded-design-tools/2022-2.html 安装虚拟机 安装…...
【进程与线程】进程与线程 QA
进程与线程常见知识点: 1、什么是进程、线程,有什么区别? 进程是资源(CPU、内存等)分配的基本单位,线程是CPU调度和分配的基本单位程序执行的最小单位)。同一时间,如果CPU是单核,只有一个进程在执行,所谓…...
电脑风扇控制软件 Macs Fan Control Pro mac中文版功能介绍
Macs Fan Control mac是一款专门为 Mac 用户设计的软件,它可以帮助用户控制和监控 Mac 设备的风扇速度和温度。这款软件允许用户手动调整风扇速度,以提高设备的散热效果,减少过热造成的风险。 Macs Fan Control 可以在菜单栏上显示当前系统温…...
【13】c++11新特性 —>call_once
在某些特定情况下,某些函数只能在多线程环境下调用一次,比如:要初始化某个对象,而这个对象只能被初始化一次,就可以使用std::call_once()来保证函数在多线程环境下只能被调用一次。使用call_once()的时候,需…...
解决logstash插件logstash-outputs-mongodb一条数据失败后一直重复尝试
描述 从日志中读取数据时,有一条数据不符合规范,导致logstash读取数据插入时出错,而插件又无限尝试插入,导致堵塞。 解决方案 找到logstash文件夹目录,例如是:/data/logstash-7.3.2 cd /data/logstash-…...
【网络协议】聊聊HTTPDNS如何工作的
传统 DNS 存在哪些问题? 域名缓存问题 我们知道CND会进行域名解析,但是由于本地会进行缓存对应的域名-ip地址,所以可能出现过期数据的情况。 域名转发问题 出口 NAT 问题 域名更新问题 解析延迟问题 因为在解析DNS的时候,需要进行…...
TikTok与老年用户:社交媒体的跨代交流
在数字时代,社交媒体已成为人们沟通、分享和互动的主要平台。然而,社交媒体不再仅仅局限于年轻一代,老年用户也逐渐加入其中。 其中,TikTok是一个引领潮流的短视频社交媒体应用,正在吸引越来越多的老年用户。本文将探…...
如何在Linux机器上使用ssh远程连接Windows Server服务器
如何在Linux机器上使用ssh远程连接Windows Server服务器 一、源起二、使用ssh远程连接Windows1.先决条件(1)至少运行 Windows Server 2019 或 Windows 10(内部版本 1809)的设备。(2)PowerShell 5.1 或更高版…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
