当前位置: 首页 > 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 或更高版…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...