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 或更高版…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...