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

离线查询+线段树,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、思路分析 考虑查询区间已经给出&#xff0c;我们可以离线查询 对于这类区间离线查询的问题我们通常可以通过左端点排序&#xff0c;然后遍历询问同时维护左区间信息…...

CTF常用sql注入(二)报错注入(普通以及双查询)

0x05 报错注入 适用于页面无正常回显&#xff0c;但是有报错&#xff0c;那么就可以使用报错注入 基础函数 floor() 向下取整函数 返回小于或等于传入参数的最大整数。换句话说&#xff0c;它将数字向下取整到最接近的整数值。 示例&#xff1a; floor(3.7) 返回 3 floor(-2…...

LabVIEW汽车ECU测试系统

开发了一个基于LabVIEW开发的汽车发动机控制单元&#xff08;ECU&#xff09;测试系统。该系统使用了NI的硬件和LabVIEW软件&#xff0c;能够自动执行ECU的功能测试和性能测试&#xff0c;确保其在不同工作条件下的可靠性和功能性。通过自动化测试系统&#xff0c;大大提高了测…...

3个让你爽到爆炸的学习工具

We OCR WeOCR 是一个基于浏览器的文字识别工具&#xff0c;用户可以通过上传图片来识别其中的文本信息。它是一个渐进式网络应用程序&#xff08;PWA&#xff09;&#xff0c;可以在浏览器中离线使用。WeOCR 是开源的&#xff0c;并且基于 Tesseract OCR 引擎开发。用户无需在本…...

Java 重载和重写

Java 重载和重写 重写重载定义指子类定义了一个与其父类中具有相同名称、参数列表和返回类型的方法&#xff0c;并且子类方法的实现覆盖了父类方法的实现。 参数列表和方法名必须相同&#xff0c;即外壳不变&#xff0c;核心重写指在一个类里面&#xff0c;方法名字相同&#x…...

ode45的例程|MATLAB例程|四阶龙格库塔定步长节微分方程

ode45自己编的程序和测试代码 模型 模拟一个卫星绕大行星飞行的轨迹计算。 结果 轨迹图如下: 源代码 以下代码复制到MATLAB上即可运行,并得到上面的图像: % ode45自己编的程序和测试代码 % Evand©2024 % 2024-7-2/Ver1 clear;clc;close all; rng(0); % 参数设定…...

“第六感”真的存在吗?

现在已有证据表明&#xff0c;人类除视觉、听觉、嗅觉、味觉和触觉五种感觉以外&#xff0c;确实存在“第六感” “第六感”的学术名称为“超感自知觉”(简称ESP)&#xff0c;它能透过正感官之外的渠道接收信息&#xff0c; 预知将要发生的事&#xff0c;而且与当事人之前的经…...

软信天成:您的数据仓库真的“达标”了吗?

在复杂多变的数据环境中&#xff0c;您的数据仓库是否真的“达标”了&#xff1f;本文将深入探讨数据仓库的定义、合格标准及其与数据库的区别&#xff0c;帮助您全面审视并优化您的数据仓库。 一、什么是数据仓库&#xff1f; 数据仓库是一个面向主题的、集成的、相对稳定的、…...

TCP/IP模型每层内容和传输单位

TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;模型是一种用于描述网络通信中协议层次结构的模型&#xff0c;它最初被设计用来描述互联网的协议栈。TCP/IP模型通常分为四层&#xff0c;自下而上分别为&#xff1a; 网络接入层&#xff08;Ne…...

EtherCAT通讯介绍

一、EtherCAT简介 EtherCAT&#xff08;Ethernet for Control Automation Technology&#xff09;是一种实时以太网技术&#xff0c;是由德国公司Beckhoff Automation在2003年首次推出的。它是一种开放的工业以太网标准&#xff0c;被设计用于满足工业自动化应用中的高性能和低…...

14-4 深入探究小型语言模型 (SLM)

大型语言模型 (LLM) 已经流行了一段时间。最近&#xff0c;小型语言模型 (SLM) 增强了我们处理和使用各种自然语言和编程语言的能力。但是&#xff0c;一些用户查询需要比在通用语言上训练的模型所能提供的更高的准确性和领域知识。此外&#xff0c;还需要定制小型语言模型&…...

ai智能语音机器人化繁为简让沟通无界限

人工智能这些年的飞速发展一方面顺应着国家智能化发展的规划&#xff0c;一方面印证着智能改动生活的预言。人工智能的开展与人们最息息相关大约就是智能手机的换代更迭&#xff0c;相信大家都有这方面的感受吧&#xff01;如今企业的电销话务员越来越少&#xff0c;机器人智能…...

c++ primer plus 第15章友,异常和其他:友元类

c primer plus 第15章友&#xff0c;异常和其他&#xff1a;友元类 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;友元类 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的…...

面试题002-Java-Java集合

面试题002-Java-Java集合 目录 面试题002-Java-Java集合题目自测题目答案1. 说说 List,Set,Map 三者的区别&#xff1f;三者底层的数据结构&#xff1f;2. 有哪些集合是线程不安全的&#xff1f;怎么解决呢&#xff1f;3. 比较 HashSet 、LinkedHashSet 和 TreeSet 三者的异同&…...

数组越界情况

数组越界情况...

工作日常学习记录

使用情景 今天开发上遇到一个搜索的需求&#xff0c;要求可以多选&#xff0c;模糊查询。我首先和前端沟通&#xff0c;前端多选后使用逗号分隔&#xff0c;拼成字符串传输给我&#xff0c;我后端再进行具体的处理。 具体处理 初步构想 由于需要查询的字段也是一个长的字符…...

C#中的容器

1、数组 数组是存储相同类型元素的固定大小的顺序集合 声明数组时&#xff0c;必须指定数组的大小 2.数组的插入和删除数据比较麻烦&#xff0c;但是查询比较快 2、动态数组&#xff08;ArrayList&#xff09; 动态数组&#xff1a;可自动调节数组的大小 可以存储任意类型数…...

rust + mingw安装教程

0. 说明 windows上安装rust时&#xff0c;需要在电脑上安装C/C构建工具。推荐的的两种工具链可以选择&#xff1a; visual studio build toolsmingw 官方推荐使用visual studio&#xff0c;若你的电脑上已经安装了visual studio&#xff0c;则无需再安装&#xff0c;直接安装…...

【sqlite3】联系人管理系统

SQLite3实现简单的联系人管理系统 有关sqlite3的基础知识请点击&#xff1a;SQLite3的使用 效果展示&#xff1a; 创建一个名为contacts.db的数据库 首先&#xff0c;我们需要创建一个名为contacts.db的数据库&#xff0c;并建立一个名为"contact"的表&#xff0…...

秋招Java后端开发冲刺——并发篇2(JMM与锁机制)

本文对Java的内存管理模型、volatile关键字和锁机制进行详细阐述&#xff0c;包括synchronized关键字、Lock接口及其实现类ReentrantLock、AQS等的实现原理和常见方法。 一、JMM&#xff08;Java内存模型&#xff09; 1. 介绍 JMM定义了共享内存中多线程程序读写操作的行为规…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

【Java】Ajax 技术详解

文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...