当前位置: 首页 > news >正文

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 [国家集训队] 数颜色 / 维护队列

带修改的莫队 带修改的莫队就是在基础莫队的基础上增加了一维属性&#xff0c;之前只需要维护l&#xff0c;r现在还需要维护一下时间t&#xff0c;排序还是先按照左端点块儿号排序&#xff0c;然后右端点块儿号排序&#xff0c;最后按时间排序。其它的都是差不多的。 #include…...

uniapp 请求接口的方式

在UniApp中&#xff0c;我们可以使用多种方式来发送请求接口。以下是几种常用的方式&#xff1a; 1、使用unmireuest方法:uni.reuest是uniApp提供的原生AP&#xff0c;可以发送HTTP请&#xff0c;我们可以通过传递一个图对象来设置请求的参数&#xff0c;RL、请求方法GET/POST…...

怎么查看当前vue项目,要求的node.js版本

要查看当前 Vue 项目所需的 Node.js 版本&#xff0c;你可以查看项目根目录下的 package.json 文件中的 engines 属性。该属性定义了项目所需的 Node.js 版本范围。 例如&#xff0c;以下是一个示例 package.json 文件&#xff1a; {"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 日。令小明头疼的是&#xff0c;这些日期采用的格式非常不统一&#xff0c;有采用年/月/日的&#xff0c;有采用月/日/年的&#xff0c;还有采…...

PDF文件解析

一、PDF文件介绍 PDF是英文Portable Document Format缩写&#xff0c;就是可移植的意思&#xff0c;它是以PostScript语言图象模型为基础&#xff0c;无论在哪种打印机上都可保证精确的颜色和准确的打印效果&#xff0c;PostScript咱也不懂&#xff0c;估计和SVG的原理差不多吧…...

初识微服务技术栈

认识微服务 随着互联网行业的发展&#xff0c;对服务的要求也越来越高&#xff0c;服务架构也从单体架构逐渐演变为现在流行的微服务架构&#xff0c;这些架构之间有怎样的差别呢&#xff1f; 导学&#xff1a; 了解微服务的优缺点&#xff1b;了解微服务架构的演变过程&am…...

windows 下运行正常,但是linux下报错 : Could not find or load main class

使用指令 "sed -i s/\r$// xxxxxxx.sh"&#xff0c;将 .sh 文件中的 "\r" 全部替换成空白符&#xff0c;即可解决问题 转转&#xff1a;https://www.cnblogs.com/cmxbky1314/p/12096611.html...

MySQL 数据目录和 InnoDB 表空间补充知识:详细结构

1. 数据目录 在Ubuntu下&#xff0c;MySQL的数据目录为/var/lib/mysql 1.1 数据库在文件系统中的表示 &#xff08;1&#xff09;创建数据库时&#xff0c;会在数据目录下创建一个与数据库名同名的子目录。&#xff08;除了information_schema这个系统数据外&#xff09; &…...

移远EC600U-CN开发板 day02

1.QuecPythonLVGL显示图片 由于官方提供的显示图片函数使用失败&#xff0c;为了能在屏幕上显示图片&#xff0c;通过对出厂脚本的分析&#xff0c;成功使用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&#xff08;qgis&#xff09;教程 这个教程全网独一份啊&#xff0c;博主是自己摸索出来的。 visual studio Python 配置QGIS&#xff08;qgis&#xff09;环境一共分为两部&#xff1a; 第一步安装QGIS&#xff1a; 下载链接如下 https://www…...

第二证券:消费电子概念活跃,博硕科技“20cm”涨停,天龙股份斩获10连板

消费电子概念7日盘中再度拉升&#xff0c;到发稿&#xff0c;博硕科技“20cm”涨停&#xff0c;光大同创、波长光电涨超10%&#xff0c;易德龙、向阳科技、得润电子、天龙股份、同兴达等涨停。 博硕科技强势涨停&#xff0c;公司昨日在接受安排调研时表明&#xff0c;公司从上…...

petalinux 2022.2 在 ubantu18.04 下的安装

下载 Ubuntu下载&#xff1a; https://releases.ubuntu.com/18.04/ubuntu-18.04.6-desktop-amd64.iso petalinux 下载&#xff1a; https://www.xilinx.com/support/download/index.html/content/xilinx/en/downloadNav/embedded-design-tools/2022-2.html 安装虚拟机 安装…...

【进程与线程】进程与线程 QA

进程与线程常见知识点&#xff1a; 1、什么是进程、线程&#xff0c;有什么区别? 进程是资源(CPU、内存等)分配的基本单位&#xff0c;线程是CPU调度和分配的基本单位程序执行的最小单位)。同一时间&#xff0c;如果CPU是单核&#xff0c;只有一个进程在执行&#xff0c;所谓…...

电脑风扇控制软件 Macs Fan Control Pro mac中文版功能介绍

Macs Fan Control mac是一款专门为 Mac 用户设计的软件&#xff0c;它可以帮助用户控制和监控 Mac 设备的风扇速度和温度。这款软件允许用户手动调整风扇速度&#xff0c;以提高设备的散热效果&#xff0c;减少过热造成的风险。 Macs Fan Control 可以在菜单栏上显示当前系统温…...

【13】c++11新特性 —>call_once

在某些特定情况下&#xff0c;某些函数只能在多线程环境下调用一次&#xff0c;比如&#xff1a;要初始化某个对象&#xff0c;而这个对象只能被初始化一次&#xff0c;就可以使用std::call_once()来保证函数在多线程环境下只能被调用一次。使用call_once()的时候&#xff0c;需…...

解决logstash插件logstash-outputs-mongodb一条数据失败后一直重复尝试

描述 从日志中读取数据时&#xff0c;有一条数据不符合规范&#xff0c;导致logstash读取数据插入时出错&#xff0c;而插件又无限尝试插入&#xff0c;导致堵塞。 解决方案 找到logstash文件夹目录&#xff0c;例如是&#xff1a;/data/logstash-7.3.2 cd /data/logstash-…...

【网络协议】聊聊HTTPDNS如何工作的

传统 DNS 存在哪些问题&#xff1f; 域名缓存问题 我们知道CND会进行域名解析&#xff0c;但是由于本地会进行缓存对应的域名-ip地址&#xff0c;所以可能出现过期数据的情况。 域名转发问题 出口 NAT 问题 域名更新问题 解析延迟问题 因为在解析DNS的时候&#xff0c;需要进行…...

TikTok与老年用户:社交媒体的跨代交流

在数字时代&#xff0c;社交媒体已成为人们沟通、分享和互动的主要平台。然而&#xff0c;社交媒体不再仅仅局限于年轻一代&#xff0c;老年用户也逐渐加入其中。 其中&#xff0c;TikTok是一个引领潮流的短视频社交媒体应用&#xff0c;正在吸引越来越多的老年用户。本文将探…...

如何在Linux机器上使用ssh远程连接Windows Server服务器

如何在Linux机器上使用ssh远程连接Windows Server服务器 一、源起二、使用ssh远程连接Windows1.先决条件&#xff08;1&#xff09;至少运行 Windows Server 2019 或 Windows 10&#xff08;内部版本 1809&#xff09;的设备。&#xff08;2&#xff09;PowerShell 5.1 或更高版…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

负载均衡器》》LVS、Nginx、HAproxy 区别

虚拟主机 先4&#xff0c;后7...

【多线程初阶】单例模式 指令重排序问题

文章目录 1.单例模式1)饿汉模式2)懒汉模式①.单线程版本②.多线程版本 2.分析单例模式里的线程安全问题1)饿汉模式2)懒汉模式懒汉模式是如何出现线程安全问题的 3.解决问题进一步优化加锁导致的执行效率优化预防内存可见性问题 4.解决指令重排序问题 1.单例模式 单例模式确保某…...

RKNN开发环境搭建2-RKNN Model Zoo 环境搭建

目录 1.简介2.环境搭建2.1 启动 docker 环境2.2 安装依赖工具2.3 下载 RKNN Model Zoo2.4 RKNN模型转化2.5编译C++1.简介 RKNN Model Zoo基于 RKNPU SDK 工具链开发, 提供了目前主流算法的部署例程. 例程包含导出RKNN模型, 使用 Python API, CAPI 推理 RKNN 模型的流程.   本…...