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

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...