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

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...