第一个重复出现的数 HRBUST - 1830

2024-02-22 18:38
文章标签 第一个 重复 hrbust 1830

本文主要是介绍第一个重复出现的数 HRBUST - 1830,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1830

开个数组记录每个数右边第一个相同数的位置 线段树维护这个数组的区间最小值 这样可以把问题转换为判定性问题 即右树是否存在符合条件的某个位置 有则返回 无则查左树

但是这里的query写起来稍微有点不太一样 因为我们不是从根节点开始查 要查询的区间会被划分成很多不太规则的小区间 但是遍历这些小区间的先后顺序是一定的 比如对于1-8 我要查2-7 区间划分如下

1-8

1-4 5-8

1-2 [3-4] [5-6] 7-8

1 [2] 3 4 5 6 [7] 8

如果query先递归左树 那遍历顺序为[2] [3-4] [5-6] [7] 这里要先递归右树 遍历顺序为[7] [5-6] [3-4] [2]

进入[7]后 如果最小值小于等于查询区间右边界 说明当前区间内有符合条件的数 从当前区间继续递归肯定能找到答案且找到答案后立即返回 若大于查询区间右边界 说明[7]内没有要找的数 返回 等到递归至[5-6]时再做判断 总体复杂度还是logn

当然可以logn*logn无脑二分 做法就不说了

#include <bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;map <int,int> mp;
int ary[500010],rgt[500010],minn[2000010];
int n,q;void pushup(int cur)
{minn[cur]=min(minn[2*cur],minn[2*cur+1]);
}void build(int l,int r,int cur)
{int m;if(l==r){minn[cur]=rgt[l];return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}int query(int pl,int pr,int l,int r,int cur)
{int res,m;if(pl<=l&&r<=pr){if(minn[cur]<=pr){if(l==r) return l;else{res=-1,m=(l+r)/2;if(pr>m) res=query(pl,pr,m+1,r,2*cur+1);if(pl<=m&&res==-1) res=query(pl,pr,l,m,2*cur);return res;}}else return -1;}else{res=-1,m=(l+r)/2;if(pr>m) res=query(pl,pr,m+1,r,2*cur+1);if(pl<=m&&res==-1) res=query(pl,pr,l,m,2*cur);}return res;
}int main()
{int i,l,r,res;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++) scanf("%d",&ary[i]);mp.clear();for(i=n;i>=1;i--){if(mp[ary[i]]==0) rgt[i]=N;else rgt[i]=mp[ary[i]];mp[ary[i]]=i;}build(1,n,1);scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);res=query(l,r,1,n,1);if(res==-1) printf("jiong\n");else printf("%d\n",ary[res]);}printf("\n");}return 0;
}

 

这篇关于第一个重复出现的数 HRBUST - 1830的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep

SQL常用操作精华之复制表、跨库查询、删除重复数据

《SQL常用操作精华之复制表、跨库查询、删除重复数据》:本文主要介绍SQL常用操作精华之复制表、跨库查询、删除重复数据,这些SQL操作涵盖了数据库开发中最常用的技术点,包括表操作、数据查询、数据管... 目录SQL常用操作精华总结表结构与数据操作高级查询技巧SQL常用操作精华总结表结构与数据操作复制表结

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行