Codeforces Round 923 (Div. 3)D. Find the Different Ones! 双指针

Problem - D - Codeforces

双指针O(2n),其实本场B题我写的是O(26n),结果这道题不敢想哈哈。

题意就是给你一串数字,然后问区间(l , r)内是否有不同的数字,输出任意一组下标即可,没有就输出 -1 -1

所以我们看l 在 l+1~r 中是否有不同即可。

所以我们对每个数都存一个下一个不同的数字的下标即可。

(最后几个可能都是相同的,没处理到就是0,0的话下面特判一下即可。)

代码:

void solve()
{int n;cin >> n;vector<int>arr(n+1);for (int i = 1; i <= n; i++){cin >> arr[i];}vector<int>nd(n);//next diffint l = 1;for (int i = 2; i <= n; i++){if (arr[i] != arr[l]){while (l < i){nd[l++] = i;}}}int q;cin >> q;for (int i = 1; i <= q; i++){int l, r;cin >> l >> r;if (nd[l] > r||nd[l] == 0)/* 0 */{cout << -1 << " " << -1 << endl;}else{cout << l << " " << nd[l] << endl;}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;for (int i = 1; i <= t; i++){solve();}return 0;
}

多组询问问题:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774697.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Python(21)正则表达式中的“元字符”

大家好&#xff01;我是码银&#x1f970; 欢迎关注&#x1f970;&#xff1a; CSDN&#xff1a;码银 公众号&#xff1a;码银学编程 获取资源&#xff1a;公众号回复“python资料” 在本篇文章中介绍的是正则表达式中一部分具有特殊意义的专用字符&#xff0c;也叫做“元…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Stepper组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Stepper组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Stepper组件 鸿蒙&#xff08;HarmonyOS&#xff09;仅能包含子组件StepperIte…

服务器与电脑的区别?

目录 一、什么是服务器 二、什么是电脑 三、服务器和电脑的区别 一、什么是服务器 服务器是指一种专门提供计算和存储资源、运行特定软件服务的物理或虚拟计算机。服务器主要用于接受和处理来自客户端&#xff08;如个人电脑、手机等&#xff09;的请求&#xff0c;并向客户…

力扣精选算法100道—— 连续数组(前缀和专题)

连续数组&#xff08;前缀和专题&#xff09; 目录 &#x1f6a9;了解题意 &#x1f6a9;算法原理 ❗为什么hash设置成<0,-1>键值对 ❗与和为K的子数组比较hash的键值对 &#x1f6a9;代码实现 &#x1f6a9;了解题意 我们看到给定数组里面只有0和1&#xff0c;我们…

高斯伪谱C++封装库开源!

Windows x64/86 C无依赖运行高斯伪谱法求解最优控制问题&#xff0c;你只需要ElegantGP! Author: Y. F. Zhang His Github: https://github.com/ZYunfeii 写在前面 这个库在你下载它的那一时刻起不再依赖任何其他代码&#xff0c;直接可用来构建C的最优控制问题并进行求解。…

[C/C++] -- CMake使用

CMake&#xff08;Cross-platform Make&#xff09;是一个开源的跨平台构建工具&#xff0c;用于自动生成用于不同操作系统和编译器的构建脚本。它可以简化项目的构建过程&#xff0c;使得开发人员能够更方便地管理代码、依赖项和构建设置。 CMake 使用一个名为 CMakeLists.tx…

微服务入门篇:Nacos注册中心(Nacos安装,快速入门,多级存储,负载均衡,环境隔离,配置管理,热更新,集群搭建,nginx反向代理)

目录 1.Nacos安装1.官网下载2.解压到本地3.启动nacos 2.Nacos快速入门1.在父工程中导入nacos依赖2.给子项目添加客户端依赖3.修改对应服务的配置文件4.启动服务&#xff0c;查看nacos发现情况 3.Nacos服务多级存储模型4.NacosRule负载均衡5. 服务实例的权重设置6.环境隔离&…

双重OSPF + OSPF综合实验

一、实验要求 1.R4为ISP&#xff0c;所连接的所有物理接口为公有网段&#xff0c;任意指定IP即可。 2.R1-2-3 构建一个星型结构的MGRE结构&#xff0c;其中R1为中心点&#xff0c;假设R1的公有IP为固定地址。 3.R1-5-6 构建另一个全连网状的MGRE网络&#xff0c;其中R1/5均为中…

网络套件字(理论知识)

一、源IP地址和目的IP地址 上次说到IP地址是为了是为了让信息正确的从原主机传送到目的主机&#xff0c;而原IP地址和目的IP地址就是用于标识两个主机的&#xff0c;既然叫做地址必然有着路径规划的作用&#xff0c;而路径规划最重要的就是&#xff0c;从哪来到哪去&#xff0…

计算机网络基本知识(二)

文章目录 概要分层为什么分层怎么分层&#xff1f;1.实体2.协议3.服务 分层基本原则正式认识分层详细例子解释 总结 概要 分层知识&#xff1a;概念理解 分层 为什么分层 大致以上五点 为了解决上面的问题&#xff08;复杂&#xff09; 大问题划分为小问题 怎么分层&#…

新手小白做steam搬砖项目,这些内幕要了解

转眼2024年已经过去了五分之一&#xff0c;很多粉丝都在问steam搬砖项目真的假的&#xff0c;害怕项目的风险&#xff0c;担心steam搬砖项目到底能不能做&#xff0c;所以一直在犹豫和徘徊。我发现很多人想赚钱&#xff0c;但苦于找不到好的副业&#xff0c;高门槛的项目又做不…

C语言的循环结构

目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…

【机器学习】数据清洗之识别缺失点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

Verilog刷题笔记23

题目: Suppose you’re building a circuit to process scancodes from a PS/2 keyboard for a game. Given the last two bytes of scancodes received, you need to indicate whether one of the arrow keys on the keyboard have been pressed. This involves a fairly simp…

【LeetCode】51. N 皇后(困难)——代码随想录算法训练营Day30

题目链接&#xff1a;51. N 皇后 题目描述 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回…

day34 本地存储(重要)

目录 本地存储简介本地存储分类—— localStorage本地存储分类—— sessionStorage&#xff08;了解&#xff09;存储复杂数据类型问题1&#xff1a;本地只能存储字符串,无法存储复杂数据类型。问题2&#xff1a;因为本地存储里面取出来的是字符串&#xff0c;不是对象&#xf…

react将选中文本自动滑动到容器可视区域内

// 自动滚动到可视区域内useEffect(() > {const target ref;const wrapper wrapperRef?.current;if (target && wrapperRef) {const rect target.getBoundingClientRect();const wrapperRect wrapper.getBoundingClientRect();const isVisible rect.bottom &l…

消息队列MQ 介绍

&#x1f47d;System.out.println(“&#x1f44b;&#x1f3fc;嗨&#xff0c;大家好&#xff0c;我是代码不会敲的小符&#xff0c;双非大四&#xff0c;Java实习中…”); &#x1f4da;System.out.println(“&#x1f388;如果文章中有错误的地方&#xff0c;恳请大家指正&a…

掌握虚拟化与网络配置之道:深入浅出VMware及远程管理技巧

目录 虚拟机介绍 虚拟机的关键字 服务器架构的发展 为什么用虚拟机VMware 虚拟机和阿里云的区别 功能角度 价格因素 应用场景 优势方面 找到windows的服务管理 配置VMware 关于VMware安装的几个服务 vmware如何修改各种网络配置 关于NAT的详细信息(了解) NAT(网…

我的docker随笔43:问答平台answer部署

本文介绍开源问答社区平台Answer的容器化部署。 起因 笔者一直想搭建一个类似stack overflower这样的平台&#xff0c;自使用了Typora&#xff0c;就正式全面用MarkdownTyporagit来积累自己的个人知识库&#xff0c;但没有做到web化&#xff0c;现在也还在探索更好的方法。 无…