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

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...