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 或更高版…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
