离线查询+线段树,CF522D - Closest Equals
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
522D - Closest Equals
二、解题报告
1、思路分析
考虑查询区间已经给出,我们可以离线查询
对于这类区间离线查询的问题我们通常可以通过左端点排序,然后遍历询问同时维护左区间信息来完成
我们考虑可以预处理出d[], d[i]代表a[i]和其左边最近的相等的值的距离,如果没有就置为n
然后线段树维护区间最值
预处理nxt[i]即a[i]下一个出现位置
考虑将询问按照左端点升序排序
遍历查询q,如果当前遍历到的l < q[i].l,我们就右扩展左区间,同时modify nxt[l]为正无穷
然后查询区间[l, r]的最值即可
2、复杂度
时间复杂度: O(NlogN + MlogN)空间复杂度:O(N)
3、代码详解
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e9 + 7, P = 1e9 + 7;template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree(int _n): n(_n), info(2 << (32 - __builtin_clz(_n))) {}SegmentTree(std::vector<Info>& _init): SegmentTree(_init.size()) {auto build = [&](auto&& self, int p, int l, int r) {if (l == r) {info[p] = _init[l];return;}int mid = l + r >> 1;self(self, p << 1, l, mid), self(self, p << 1 | 1, mid + 1, r);pull(p);};build(build, 1, 0, n - 1);}void pull(int p) {info[p] = info[p << 1] + info[p << 1 | 1];}void modify(int p, int l, int r, int x, const Info& v) {if (l == r) {info[p] = v;return;}int mid = l + r >> 1;if (x <= mid) modify(p << 1, l, mid, x, v);else modify(p << 1 | 1, mid + 1, r, x, v);pull(p);}void modify(int x, const Info& v) {modify(1, 0, n - 1, x, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l > y || r < x) return Info();if (x <= l && r <= y) return info[p];int mid = l + r >> 1;return rangeQuery(p << 1, l, mid, x, y) + rangeQuery(p << 1 | 1, mid + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n - 1, l, r);}};
struct Info {int x = inf;Info operator + (const Info& b) const {return { std::min(x, b.x) };}
};void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(n), nxt(n, n);std::map<int, int> last;for (int i = 0; i < n; i ++ ) {std::cin >> a[i];if (last.count(a[i]))nxt[last[a[i]]] = i;last[a[i]] = i;}std::vector<Info> d(n);for (int i = 0; i < n; i ++ )if (nxt[i] < n) d[nxt[i]] = { nxt[i] - i };SegmentTree<Info> sgt(d);std::vector<std::array<int, 3>> q(m);std::vector<int> ans(m);for (int i = 0, l, r; i < m; i ++ ) std::cin >> l >> r, q[i] = { l, r, i };std::sort(q.begin(), q.end(), [](auto& x, auto& y) {return x[0] < y[0];});for (int i = 0, st = 0; i < m; i ++ ) {auto [l, r, id] = q[i];-- l, -- r;while (st < l) {if (nxt[st] < n)sgt.modify(nxt[st], Info());++ st;}ans[id] = sgt.rangeQuery(l, r).x;}for (int x : ans) std::cout << (x < inf ? x : -1) << '\n';
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}
相关文章:
离线查询+线段树,CF522D - Closest Equals
一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 522D - Closest Equals 二、解题报告 1、思路分析 考虑查询区间已经给出,我们可以离线查询 对于这类区间离线查询的问题我们通常可以通过左端点排序,然后遍历询问同时维护左区间信息…...
CTF常用sql注入(二)报错注入(普通以及双查询)
0x05 报错注入 适用于页面无正常回显,但是有报错,那么就可以使用报错注入 基础函数 floor() 向下取整函数 返回小于或等于传入参数的最大整数。换句话说,它将数字向下取整到最接近的整数值。 示例: floor(3.7) 返回 3 floor(-2…...
LabVIEW汽车ECU测试系统
开发了一个基于LabVIEW开发的汽车发动机控制单元(ECU)测试系统。该系统使用了NI的硬件和LabVIEW软件,能够自动执行ECU的功能测试和性能测试,确保其在不同工作条件下的可靠性和功能性。通过自动化测试系统,大大提高了测…...
3个让你爽到爆炸的学习工具
We OCR WeOCR 是一个基于浏览器的文字识别工具,用户可以通过上传图片来识别其中的文本信息。它是一个渐进式网络应用程序(PWA),可以在浏览器中离线使用。WeOCR 是开源的,并且基于 Tesseract OCR 引擎开发。用户无需在本…...
Java 重载和重写
Java 重载和重写 重写重载定义指子类定义了一个与其父类中具有相同名称、参数列表和返回类型的方法,并且子类方法的实现覆盖了父类方法的实现。 参数列表和方法名必须相同,即外壳不变,核心重写指在一个类里面,方法名字相同&#x…...
ode45的例程|MATLAB例程|四阶龙格库塔定步长节微分方程
ode45自己编的程序和测试代码 模型 模拟一个卫星绕大行星飞行的轨迹计算。 结果 轨迹图如下: 源代码 以下代码复制到MATLAB上即可运行,并得到上面的图像: % ode45自己编的程序和测试代码 % Evand©2024 % 2024-7-2/Ver1 clear;clc;close all; rng(0); % 参数设定…...
“第六感”真的存在吗?
现在已有证据表明,人类除视觉、听觉、嗅觉、味觉和触觉五种感觉以外,确实存在“第六感” “第六感”的学术名称为“超感自知觉”(简称ESP),它能透过正感官之外的渠道接收信息, 预知将要发生的事,而且与当事人之前的经…...
软信天成:您的数据仓库真的“达标”了吗?
在复杂多变的数据环境中,您的数据仓库是否真的“达标”了?本文将深入探讨数据仓库的定义、合格标准及其与数据库的区别,帮助您全面审视并优化您的数据仓库。 一、什么是数据仓库? 数据仓库是一个面向主题的、集成的、相对稳定的、…...
TCP/IP模型每层内容和传输单位
TCP/IP(Transmission Control Protocol/Internet Protocol)模型是一种用于描述网络通信中协议层次结构的模型,它最初被设计用来描述互联网的协议栈。TCP/IP模型通常分为四层,自下而上分别为: 网络接入层(Ne…...
EtherCAT通讯介绍
一、EtherCAT简介 EtherCAT(Ethernet for Control Automation Technology)是一种实时以太网技术,是由德国公司Beckhoff Automation在2003年首次推出的。它是一种开放的工业以太网标准,被设计用于满足工业自动化应用中的高性能和低…...
14-4 深入探究小型语言模型 (SLM)
大型语言模型 (LLM) 已经流行了一段时间。最近,小型语言模型 (SLM) 增强了我们处理和使用各种自然语言和编程语言的能力。但是,一些用户查询需要比在通用语言上训练的模型所能提供的更高的准确性和领域知识。此外,还需要定制小型语言模型&…...
ai智能语音机器人化繁为简让沟通无界限
人工智能这些年的飞速发展一方面顺应着国家智能化发展的规划,一方面印证着智能改动生活的预言。人工智能的开展与人们最息息相关大约就是智能手机的换代更迭,相信大家都有这方面的感受吧!如今企业的电销话务员越来越少,机器人智能…...
c++ primer plus 第15章友,异常和其他:友元类
c primer plus 第15章友,异常和其他:友元类 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:友元类 提示:写完文章后,目录可以自动生成,如何生成可参考右边的…...
面试题002-Java-Java集合
面试题002-Java-Java集合 目录 面试题002-Java-Java集合题目自测题目答案1. 说说 List,Set,Map 三者的区别?三者底层的数据结构?2. 有哪些集合是线程不安全的?怎么解决呢?3. 比较 HashSet 、LinkedHashSet 和 TreeSet 三者的异同&…...
数组越界情况
数组越界情况...
工作日常学习记录
使用情景 今天开发上遇到一个搜索的需求,要求可以多选,模糊查询。我首先和前端沟通,前端多选后使用逗号分隔,拼成字符串传输给我,我后端再进行具体的处理。 具体处理 初步构想 由于需要查询的字段也是一个长的字符…...
C#中的容器
1、数组 数组是存储相同类型元素的固定大小的顺序集合 声明数组时,必须指定数组的大小 2.数组的插入和删除数据比较麻烦,但是查询比较快 2、动态数组(ArrayList) 动态数组:可自动调节数组的大小 可以存储任意类型数…...
rust + mingw安装教程
0. 说明 windows上安装rust时,需要在电脑上安装C/C构建工具。推荐的的两种工具链可以选择: visual studio build toolsmingw 官方推荐使用visual studio,若你的电脑上已经安装了visual studio,则无需再安装,直接安装…...
【sqlite3】联系人管理系统
SQLite3实现简单的联系人管理系统 有关sqlite3的基础知识请点击:SQLite3的使用 效果展示: 创建一个名为contacts.db的数据库 首先,我们需要创建一个名为contacts.db的数据库,并建立一个名为"contact"的表࿰…...
秋招Java后端开发冲刺——并发篇2(JMM与锁机制)
本文对Java的内存管理模型、volatile关键字和锁机制进行详细阐述,包括synchronized关键字、Lock接口及其实现类ReentrantLock、AQS等的实现原理和常见方法。 一、JMM(Java内存模型) 1. 介绍 JMM定义了共享内存中多线程程序读写操作的行为规…...
OpenClaw创始人加入OpenAI:这不是跳槽新闻,是整个AI行业换挡的信号
OpenClaw创始人加入OpenAI:这不是跳槽新闻,是整个AI行业换挡的信号摘要OpenClaw创始人Peter Steinberger正式加入OpenAI,项目移交开源基金会。Sam Altman亲自官宣,称他是"天才"。这件事的真正意义不在人事变动ÿ…...
双项目驱动:AI教育轻创合伙人对比传统教育创业的显著优势
随着人工智能技术的飞速发展,AI教育正成为教育行业的新风口。在这一背景下,轻创合伙模式应运而生,为创业者提供了低门槛、高潜力的入局机会。本文将深入分析AI教育轻创合伙人相较于传统教育创业的核心优势,探讨其规模化路径的实现…...
MongoDB高级面试:进阶面试题50题及答案详解
更多内容请见: 《深入掌握MongoDB数据库》 - 专栏介绍和目录 文章目录 一、高级查询优化与执行计划 (8题) 二、高级索引策略 (8题) 三、高级分片策略与优化 (8题) 四、性能调优与瓶颈分析 (7题) 五、高级复制集配置与故障处理 (6题) 六、高级事务与一致性模型 (5题) 七、安全高…...
网络安全有哪些岗位,如何成为一位优秀的网络安全工程师?
网络安全是什么? 首先说一下什么是网络安全? 网络安全工程师工作内容具体有哪些? 网络安全是确保网络系统的硬件、软件及其系统中的数据受到保护,不因偶然的或者恶意的原因而受到破坏、更改、泄露,系统连续可靠正常地…...
如何通过 SEO 优化提高企业品牌的曝光度
SEO优化提高企业品牌曝光度的关键策略 在当今数字化时代,企业品牌的曝光度直接关系到其市场竞争力和商业成功。SEO(搜索引擎优化)是提升企业品牌在搜索引擎中排名的重要手段。本文将详细探讨如何通过SEO优化提高企业品牌的曝光度,…...
DanKoe 视频笔记:个人成长:如何变得更加“不同意”(创造一个现实扭曲场)
在本节课中,我们将学习如何通过有意识地坚持自我、明确目标并有效沟通,来构建一个强大的“现实扭曲场”,从而更坚定地追求自己想要的生活,而非被动地迎合他人。 我们常常被教导要友善、随和,避免冲突。然而,…...
告别版本冲突:利用快马平台高效管理多jdk环境,提升开发效率
作为一名Java开发者,我经常遇到这样的困扰:接手不同项目时,每个项目可能要求使用不同版本的JDK。手动切换环境变量、反复安装卸载JDK版本,不仅浪费时间,还容易出错。最近我发现了一个高效的解决方案——利用InsCode(快…...
Oni-Duplicity:轻松定制《缺氧》游戏体验,告别资源与角色困扰
Oni-Duplicity:轻松定制《缺氧》游戏体验,告别资源与角色困扰 【免费下载链接】oni-duplicity A web-hosted, locally-running save editor for Oxygen Not Included. 项目地址: https://gitcode.com/gh_mirrors/on/oni-duplicity 你是否曾在《缺…...
3月31日(AI审批+技术岗位情况+知识获取方法)
如何用 AI 分类器替代人工审批 Claude 每执行一个命令、每改一个文件,都要你点一次“同意”。用户 93% 的操作都会批准。也就是说,这个“安全审批”环节,绝大多数时候只是一个条件反射。 告警疲劳:100 条告警里只有 7 条需要关注…...
继电器触点粘接?手把手教你用NTC热敏电阻搞定大功率负载保护
大功率负载下继电器触点粘接的工程解决方案:NTC热敏电阻实战指南 当你在深夜调试一块电源板时,突然闻到焦糊味——继电器又粘接了。这不是个例,据统计,工业控制系统中约23%的继电器故障源于触点粘接,而大电流场景下这一…...


