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

P1903 [国家集训队] 数颜色 / 维护队列 Solution

news 来源：原创 2025/5/20 6:33:40

Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ ，有 $m$ 个操作分两种：

$\operatorname{modify}(i,x)$ ：执行 $a_i\gets x$ .
$\operatorname{query}(l,r)$ ：求 $|\{a_l,a_{l+1},\cdots,a_r\}|$ .

Limitations

$1\le n,m\le 133333$
$\le a_i,x \le 10^6$
$2.5\text{s},512\text{MB}$

Solution

依然是不好直接做的询问，考虑莫队，维护 $\textit{cnt}_i$ 表示当前区间内 $i$ 出现次数.
在 add 和 del 时更新 $\textit{cnt}$ ，若一个数新出现或消失，我们更新答案.
但这里带了修改，我们给莫队直接加上时间维，每个查询多存一个 上次修改的时间戳.
然后需要修改与回溯函数.
拿修改讲，如果 $i$ 在当前区间内，那它就会影响答案，我们 del 掉原来的数，add 上新的即可.

有几点要提一下：

修改完后可以将 $a_i$ 和 $x$ 交换，下次遇到是就是回溯，可以省一个函数.
不能用 map 维护 $\textit{cnt}$ ，直接用数组.
要调块长，取 $B=n^{\frac{2}{3}}$ 可以过，笔者试了好几发.

Code

$1.79\text{KB},3.93\text{s},8.99\text{MB}\;\texttt{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}
const int L = 1e6 + 10;
struct Modify { int pos, x; };
struct Query { int l, r, t, id; }; signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];vector<Modify> M;vector<Query> Q;for (int i = 0, x, y; i < m; i++) {char op;cin >> op >> x >> y, x--;if (op == 'R') M.push_back({x, y});else y--, Q.push_back({x, y, M.size() - 1, Q.size()});}const int B = pow(n, 2.0 / 3);sort(Q.begin(), Q.end(), [&](Query &a, Query &b) {if (a.l / B == b.l / B) {if (a.r / B == b.r / B) return a.t < b.t;return a.r / B < b.r / B;}return a.l / B < b.l / B;});array<int, L> cnt{};int ans = 0, l = 0, r = -1, t = -1;auto add = [&](int v) {if (cnt[v]++ == 0) ans++;};auto del = [&](int v) {if (--cnt[v] == 0) ans--;};auto upd = [&](int t, int l, int r) {auto &[pos, x] = M[t];if (l <= pos && pos <= r) del(a[pos]), add(x);swap(a[pos], x);};vector<int> res(Q.size());for (auto [ql, qr, qt, id] : Q) {while (ql < l) add(a[--l]);while (r < qr) add(a[++r]);while (l < ql) del(a[l++]);while (qr < r) del(a[r--]);while (t < qt) upd(++t, l, r);while (qt < t) upd(t--, l, r);res[id] = ans;}for (int i = 0; i < Q.size(); i++) cout << res[i] << endl;return 0;
}

P1903 [国家集训队] 数颜色 / 维护队列 Solution

Description 给定序列 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1,a2,⋯,an)，有 m m m 个操作分两种： modify ⁡ ( i , x ) \operatorname{modify}(i,x) modify(i,x)：执行 a i ← x a_i\gets x ai←x. query ⁡ ( …...

编程日记 2025/5/20 6:33:40

Transformer数学推导——Q33 分析正弦编码的频率衰减对长程依赖建模的影响

该问题归类到Transformer架构问题集——位置编码——绝对位置编码。请参考LLM数学推导——Transformer架构问题集。 1. 背景知识：Transformer 与长程依赖在自然语言处理和其他序列数据处理任务中，Transformer 模型凭借其强大的性能脱颖而出。与传统的…...

编程日记 2025/5/20 4:51:58

微服务架构下的熔断与降级：原理、实践与主流框架深度解析

微服务架构下的熔断与降级：原理、实践与主流框架深度解析在现代分布式系统中，熔断 (Circuit Breaker) 和降级 (Degrade) 是保障系统弹性与高可用性的核心机制。本文将系统解析两者的原理、区别与协同方式，并结合主流框架 (Resilience4j、S…...

编程日记 2025/5/20 5:50:07

大脑、机器人与贝叶斯信念及AI推理

在机器不再局限于重复性任务的世界里，机器人技术已经大胆地迈入了感知、学习和决策的领域。这篇文章探讨了智能机器人系统是如何构建的——从理解它们嘈杂的传感器和不确定的环境，到使它们能够做出明智的选择并随着时间的推移调整自己的行为。 AI推理 …...

编程日记 2025/4/30 7:43:02

stm32wb55rg (4) 启用usart串口

code repo: 访问gitee 上节课成功点亮了LED，这次来把usart 用起来，毕竟有交互才是系统。技术准备首先查看手册，发现mcu有1个usart和1个 lpuart。 usart 的使用需要两个pin，一个接收一个发送。继续查看pin and ball definition…...

编程日记 2025/5/20 5:07:40

LSTM预测模型

LSTM预测模型时间序列预测通常需要捕获时间依赖性，而 L S T M LSTM LSTM（长短时记忆网络）是处理时间序列数据的经典深度学习方法之一。结合长短时注意力机制（ L o n g − S h o r t A t t e n t i o n M e c h a n i s m Long-S…...

编程日记 2025/5/20 5:10:29

[计算机网络]物理层

文章目录物理层的概述与功能传输介质双绞线:分类:应用领域: 同轴电缆：分类: 光纤：分类: 无线传输介质：无线电波微波：红外线：激光： 物理层设备中继器：放大器：集线器(Hub)&#xff1a…...

编程日记 2025/5/20 5:11:51

Day16(贪心算法)——LeetCode45.跳跃游戏II763.划分字母区间

1 LeetCode45.跳跃游戏II 1.1 题目描述与跳跃游戏类似，跳跃游戏II给定长为n的从0开始索引的整数数组nums，nums[i]是你在i处能向右跳跃的最大步数，求到达数组最后一个索引处需要跳跃的最少次数。一个示例：nums[2,3,1,1,4]&a…...

编程日记 2025/4/30 7:41:56

【MySQL】表的内外连接

表的内外连接一. 内连接二. 外连接1. 左外连接2. 右外连接三. 简单案例四. SQL 实战表的连接分为内连接和外连接一. 内连接内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选，之前博客中的查询都是内连接，也是在开发过程中使用的最多…...

编程日记 2025/4/30 7:41:55

Prometheus使用Recoding Rules优化性能

通过PromQL可以实时对Prometheus中采集到的样本数据进行查询，聚合以及其它各种运算操作。而在某些PromQL较为复杂且计算量较大时，直接使用PromQL可能会导致Prometheus响应超时的情况。这时需要一种能够类似于后台批处理的机制能够在后台完成这些复杂运算…...

编程日记 2025/4/30 7:41:54

Linux 怎么安装 Oracle Java 8

在 Linux 系统上安装 Oracle Java 8 的步骤如下： 1. 下载 Oracle Java 8 访问 Oracle 官方网站的 Java 下载页面： 下载链接：Oracle Java 8 下载页面选择适合 Linux x64 的安装包（通常是 .tar.gz 格式）。需要登录 Or…...

编程日记 2025/5/6 13:03:22

项目三 - 任务2：创建笔记本电脑类（一爹多叔）

在本次实战中，我们通过Java的单根继承和多接口实现特性，设计了一个笔记本电脑类。首先创建了Computer抽象类，提供计算的抽象方法，模拟电脑的基本功能。接着定义了NetCard和USB两个接口，分别包含连接网络和USB设备的抽象…...

编程日记 2025/4/30 7:40:48

基于蓝耘MaaS平台进行api调用创建本地智能ai

关于MaaS平台 MaaS 平台即 “模型即服务”（Model as a Service）平台，是一种依托云计算的人工智能服务模式。模型即服务（MaaS）平台面向企业开发者、创业者及非技术背景用户，提供开箱即用的热门AI模型服务&…...

编程日记 2025/4/30 7:39:47

【Luogu】动态规划七

P1566 加等式 - 洛谷思路： 其实这道题就是一个纸老虎，说这么多，其实最后就是问所有 a[i] 的组成方法之和有多少种那么显然的一个dp就是 dp[j] dp[j - a[i]] 然后这题就结束了，就是这么简单，最后记得减去 n&…...

编程日记 2025/4/30 7:39:46

Kotlin 常见问题

以下从基础、中级、高级三个难度等级为你提供 Kotlin 面试题及参考答案： 基础难度 1. Kotlin 中 val 和 var 的区别是什么？ 答案要点：val 用于声明不可变变量，类似于 Java 中的 final 变量，一旦赋值后就不能再重新赋…...

编程日记 2025/4/30 7:39:44

应急演练考试排查-DC01

DC01：攻击者最早通过哪种方式获取了机器权限？（ ） A、远程登录（RDP登录） B、主机系统漏洞 C、软件服务漏洞 D、钓鱼 E、物理访问 F、内网横向手段 G、低权限账户提权 H、未获取到主机权限 DC01&…...

编程日记 2025/5/20 6:02:15

Spring MVC 中解决中文乱码问题

在 Spring MVC 中解决中文乱码问题，需要从请求参数编码和响应内容编码两方面入手。以下是完整的解决方案： 一、解决请求参数中文乱码 1. POST 请求编码（表单提交） 配置 CharacterEncodingFilter 在 web.xml 中添加 Spring 提…...

编程日记 2025/5/20 6:05:31

排序算法详解笔记（二）

归并排序 #include <vector> #include <iostream> #include <algorithm> // For std::inplace_merge in optimization// Helper function to merge two sorted subarrays void merge(std::vector<int>& arr, int left, int mid, int right) {int …...

编程日记 2025/4/30 7:38:40

Spark GraphX 机器学习：图计算

引言在数字化时代，图数据（Graph Data）的价值日益凸显：社交网络中的用户关系、电商平台的商品关联、知识图谱的实体链接……这些以“节点（Vertex）”和“边（Edge）”为核心的非结构化…...

编程日记 2025/5/20 6:12:13

claude 3.7,极为均衡的“全能型战士”大模型，国内直接使用

文章目录零、前言一、操作指南操作指导二、小球弹跳三、生成 Mandelbrot set 集四、文本总结能力五、智力推理题六、感受零、前言 Claude 3.7 Sonnet（下面简称 Claude 3.7）由 Anthropic 发布，“全球首个混合推理模型”的 AI 大模型&#x…...

编程日记 2025/5/20 6:19:21

机器学习-入门-决策树(1)

机器学习-入门-决策树(1) 4.1决策树的基本流程决策树基于“树”结构进行决策每个“内部结点”对应于某个属性上的“测试”(test)每个分支对应于该测试的一种可能结果（即该属性的某个取值）每个“叶结点”对应于一个“预测结果” 学习过程&#xff1…...

编程日记 2025/5/20 6:13:51

机器学习实操第一部分机器学习基础第6章决策树

机器学习实操第一部分机器学习基础第6章决策树内容概要第6章深入介绍了决策树，这是一种功能强大的机器学习算法，能够处理分类、回归以及多输出任务。决策树通过递归地分割数据集来构建模型，具有易于解释和可视化的特点。本章详细讲解…...

编程日记 2025/5/20 5:25:35

Python实例题：ebay在线拍卖数据分析

目录 Python实例题题目实现思路代码实现代码解释 read_auction_data 函数： clean_auction_data 函数： exploratory_analysis 函数： visualize_auction_data 函数： 主程序： 运行思路注意事项 Python实…...

编程日记 2025/5/20 6:17:28

算法题（137）：丢手绢

审题： 本题需要我们找到距离最远的两个孩子之间的距离，并打印思路： 方法一：暴力枚举我们可以找到每个孩子的距离其他孩子的最远距离，然后维护一个maxdis变量得到所有孩子距离其他孩子最远距离的最大值。而距离分为顺…...

编程日记 2025/5/20 6:07:10

2025年具身智能科技研报

引言本报告系统梳理了2025年具身智能领域的最新进展，基于国内外权威新闻源与行业研究报告，通过数据可视化与深度分析相结合的方式，呈现该领域多维发展态势。从技术突破层面看，多模态大模型的突破性进展为具身智能注入新动能&…...

编程日记 2025/5/20 4:42:46

TCL科技2025一季度归母净利润10.1亿，半导体显示业务业绩创新高

4月29日，TCL科技（000100）披露2024年年报及2025年一季报。2024全年，TCL科技实现营业收入1648亿元，归母净利润15.6亿元；实现经营现金流净额295亿元，同比增长16.6%。2025年一季度，TCL科…...

编程日记 2025/4/30 7:37:30

阿里云 CentOS YUM 源配置指南

阿里云 CentOS YUM 源配置指南在使用 CentOS 7 时，由于 CentOS 官方源停止维护等原因，yum install 命令可能会报错 “Cannot find a valid baseurl for repo: centos-sclo-rh/x86_64”。以下是通过更换阿里云源解决该问题的详细步骤。一、备份原有配…...

编程日记 2025/5/20 5:55:09

阿里云 OpenManus 实战：高效AI协作体系

阿里云 OpenManus 实战：高效AI协作体系写在最前面初体验：快速部署，开箱即用真实案例分享：从单体开发到智能良好提示词过程展示第一步：为亚马逊美国站生成商品描述第二步：为eBay全球站生成商品描述结果分析…...

编程日记 2025/4/30 7:36:27

阿里云服务迁移实战: 05-OSS迁移

概述 Bucket 复制分为两种，同区域复制和跨区域复制同账号复制比较简单，根据提示填写信息即可，本文主要介绍跨账号复制。同区域复制授权角色选择 “AliyunOSSRole”, 创建方法见 “跨区域复制”。然后点击确定即可。跨区域复制假设我…...

编程日记 2025/5/20 5:48:27

Vue高级特性实战：自定义指令、插槽与路由全解析

一、自定义指令 1.如何自定义指令 ⑴.全局注册语法通过 Vue.directive 方法注册，语法格式为： Vue.directive(指令名, {// 钩子函数，元素插入父节点时触发（仅保证父节点存在，不一定已插入文档）inserted(…...

编程日记 2025/5/20 4:55:49

Python入门：流程控制练习

本文将介绍Python中流程控制的基础知识，包括条件判断和循环结构，并提供多个实用示例帮助初学者快速掌握这些概念。所有代码都使用基础语法，非常适合Python新手学习。 1. 简单条件判断： 编写一个程序，要求用户输入一个…...

编程日记 2025/5/20 5:28:44

Unity PBR基础知识

PBR原理基于物理的渲染（Physically Based Rendering，PBR）是指使用基于物理原理和微平面理论建模的着色/光照模型，以及使用从现实中测量的表面参数来准确表示真实世界材质的渲染理念。 PBR基础理念微平面理论（Micr…...

编程日记 2025/5/16 15:40:24

智慧交警系统架构设计方案

一、引言：智慧交警为何成为城市治理的刚需？ 当前，中国城市化进程加速，汽车保有量激增，交通拥堵、事故频发、执法效率不足等问题日益突出。传统交通管理依赖人力巡查与分散系统，已难以应对复杂需求。智慧交…...

编程日记 2025/4/30 7:35:23

NOC科普一

拓扑结构 NoC里Router之间的link链路连接可以定义成不同的结构以改变通信测量和简化片上通信结构。 （a）Ring：环形，每个router都有2个相邻节点，虽然部署和故障排除相对容易，但主要缺点是其通信的距离也即环…...

编程日记 2025/5/20 6:02:15

Linux CentOS 7 安装Apache 部署html页面

*、使用yum包管理器安装Apache。运行以下命令： sudo yum install httpd *、启动Apache服务 sudo systemctl start httpd *、设置Apache服务开机自启 sudo systemctl enable httpd *、验证Apache是否运行 sudo systemctl status httpd 或者，通过浏…...

编程日记 2025/5/20 4:50:15

人工智能在医疗行业的应用和发展前景

人工智能在医疗行业的应用和发展前景引言在科技日新月异的今天，人工智能（Artificial Intelligence，AI）已然成为全球最具潜力与影响力的技术之一。医疗行业，作为关乎人类健康与生命的关键领域，正迅速成为人工智能应用的热门阵地。人工智能在医疗领域的应用，不仅为解决…...

编程日记 2025/4/30 7:35:21

vue3+Nest.js项目部署阿里云

可以先参考之前的vue3express部署的文章 vue3viteexpressmongoDB上线(新手向)_vue3 vite express-CSDN博客区别在于express和数据库前端前往上面文章查看 1.nest.js部署首先，把nest.js中相关的文件打包除去依赖（node_modules）上传到服…...

编程日记 2025/5/20 4:35:06

phpstudy修改Apache端口号

1. 修改Listen.conf文件本地phpstudy安装目录： 2.其他问题 ① 修改httpd.conf不起作用 ② 直接通过控制面板配置好像有延迟缓存...

编程日记 2025/4/30 7:34:19

JSON-RPC 2.0 规范中文版——无状态轻量级远程过程调用协议

前言 JSON-RPC是一种简单、轻量且无状态的远程过程调用（RPC）协议，它允许不同系统通过标准化的数据格式进行通信。自2010年由JSON-RPC工作组发布以来，已成为众多应用中实现远程交互的基础协议之一。本规范主要表达了JSON-RPC 2.0版…...

编程日记 2025/5/20 5:27:06

DeepSeek+Dify之七借助API和Trae完成demo

DeepSeek+Dify之六通过API调用工作流文章目录背景准备资料1、借助Trae来创建demo2、前后端主要代码3、测试demo4、完整项目背景在软件开发与项目实践领域，常常需要借助各种工具与技术来快速搭建可运行的示例项目，以验证思路、展示功能或进行技术探索。本文聚焦于借助 Tra…...

编程日记 2025/5/20 6:03:49

C++ 红黑树

上一节我介绍了二叉搜索树家族的AVL树，这里我们来介绍二叉搜索树家族的另一个成员，也是使用最广泛的成员。 1.AVL树与红黑树的区别平衡性质 AVL 树：是严格的平衡二叉树，要求任意节点的左右子树高度差的绝对值不超过 1&#xff…...

编程日记 2025/4/30 7:34:15

学习海康VisionMaster之线圆测量

一：进一步学习了今天学习下VisionMaster中的线圆测量：核心就是坐标点到直线的距离量测 1：什么是线圆测量？ 工业自动化中很常见的应用尺寸测量，需要量测一个零件的外形尺寸，其中一项如果是需要测量圆心到直…...

编程日记 2025/4/30 7:33:12

Uniapp：置顶

目录一、出现场景二、效果展示三、具体使用一、出现场景在项目的开发过程中，我们经常会用到置顶的功能，比如说从页面的最下方滑动到最上面太慢了，这个时候我们就可以使用置顶功能。二、效果展示三、具体使用参数名类型必填说明scrollTopNumber否滚动到页面的目标位置…...

编程日记 2025/5/4 4:58:51

UDP数据报和TCP流套接字编程

文章目录 UDP数据报套接字编程1.DatagramSocket类2.DatagramPacket类3. InetSocketAddress类构建服务端和客户端 TCP流套接字编程1. ServerSocket类2.Socket类构建服务端和客户端扩展对话形式简易的字典多线程实现线程池实现 UDP数据报套接字编程 1.DatagramSocket类 Datagr…...

编程日记 2025/4/30 7:33:11

某建筑石料用灰岩矿自动化监测

1. 项目简介某建材有限公司成立于2012年，是一家集矿山开采、石料生产及销售为一体的建筑材料生产企业，拥有两条年产500万吨的环保型精品骨料生产线，各类工程机械 30 多台套，运输车辆50多辆。公司坚持生态优先，以高质…...

编程日记 2025/4/30 7:33:10

C++11 的编译器支持

C11 主要功能特性一览特性描述提案GCCClangMSVCApple ClangEDG eccpIntel CNvidia HPC C (ex PGI)*Nvidia nvccCrayEmbarcadero C BuilderIBM Open XL C for AIXIBM Open XL C for z/OSIBM XL CSun/Oracle CHP aCCDigital Mars C核心功能右值引用 (T&&)支持移动语义和…...

编程日记 2025/4/30 7:33:09

20250429 垂直地表发射激光测量偏转可以验证相对性原理吗

垂直地表发射激光测量偏转可以验证相对性原理吗垂直地表发射激光测量偏转可以在一定条件下用于检验广义相对论中的等效原理和引力对光传播的影响，但要说直接验证整个相对性原理（狭义广义）是不准确的。我们可以逐步分析这个问题：…...

编程日记 2025/4/30 7:33:08

Makefile 在 ARM MCU 开发中的编译与链接参数详解与实践

内容大纲引言一、预处理与宏定义头文件搜索路径：-I 宏定义：-D 二、编译器选项（CFLAGS）架构与指令集：-mcpu、-mthumb 优化与调试：-Os、-O2、-g 警告与错误：-Wall、-Werror 代码剥离：-ffunction-sections、-fdata-sections 其他常用选项三、链接器选项（LDFLAGS）链…...

编程日记 2025/4/30 7:33:08

AimRT 从零到一：官方示例精讲 —— 四、logger示例.md

logger示例官方仓库：logger 配置文件(configuration_logger.yaml) 依据官方示例项目结构自行编写YAML配置文件： # 基础信息 base_info:project_name: Logger # 项目名称build_mode_tags: ["EXAMPLE", "SIMULATION", "TE…...

编程日记 2025/5/19 15:36:26

mybatis传递多个不同类型的参数到mapper xml文件

在业务中查询某张表时需要设置多个查询条件，并且还要根据id列表进行权限过滤，这时推荐采用Map<String, Object>作为参数进行查询，因为：Object可以设置成不同的类型，比如：List<Integer> ids&…...

编程日记 2025/4/30 7:32:06

Description

Limitations

Solution

Code

相关文章：