hdu 5919 Sequence II(主席树)
发布日期:2021-11-12 00:25:47
浏览次数:4
分类:技术文章
本文共 3762 字,大约阅读时间需要 12 分钟。
Sequence II
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1600 Accepted Submission(s): 405 Problem Description
Mr. Frog has an integer sequence of length n, which can be denoted as a1,a2,⋯,an There are m queries. In the i-th query, you are given two integers li and ri . Consider the subsequence ali,ali+1,ali+2,⋯,ari . We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as p(i)1,p(i)2,⋯,p(i)ki (in ascending order, i.e., p(i)1<p(i)2<⋯<p(i)ki ). Note that ki is the number of different integers in this subsequence. You should output p(i)⌈ki2⌉ for the i-th query.
Input
In the first line of input, there is an integer T ( T≤2 ) denoting the number of test cases. Each test case starts with two integers n ( n≤2×105 ) and m ( m≤2×105 ). There are n integers in the next line, which indicate the integers in the sequence(i.e., a1,a2,⋯,an,0≤ai≤2×105 ). There are two integers li and ri in the following m lines. However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to l‘i,r‘i(1≤l‘i≤n,1≤r‘i≤n) . As a result, the problem became more exciting. We can denote the answers as ans1,ans2,⋯,ansm . Note that for each test case ans0=0 . You can get the correct input li,ri from what you read (we denote them as l‘i,r‘i )by the following formula:
li=min{ (l‘i+ansi−1) mod n+1,(r‘i+ansi−1) mod n+1}
ri=max{ (l‘i+ansi−1) mod n+1,(r‘i+ansi−1) mod n+1}
Output
You should output one single line for each test case. For each test case, output one line “Case #x: p1,p2,⋯,pm ”, where x is the case number (starting from 1) and p1,p2,⋯,pm is the answer.
Sample Input
25 23 3 1 5 42 24 45 22 5 2 1 22 32 4
Sample Output
Case #1: 3 3Case #2: 3 1 Hint
Source
题意:有长度为 n 的序列,强制在线询问 [l,r] 这段区间中所有不同数出现的第一个位置,按照位置从小到大排完序以后的中间(向上取整)的那个位置是多少?即把各个数字在这个区间中第一次出现的位置记作 p1,p2,⋯,pk ,满足 p1<p2<⋯<pk ,求 p⌈k2⌉
学完主席树就想过来把这题过了,拖到了现在。
这是我参加的第一场区预赛-长春赛站现场赛的题,当时因为不会这道而没进银牌区。
这题也是类似spoj-dquery(感觉这题是主席树精髓啊==),其实会dquery这道题非常容易。
#include#include #include #include #include #include #include #include
转载地址:https://blog.csdn.net/fouzhe/article/details/55803885 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月27日 09时39分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
python转成c 语言_将Python对象转换为C void类型
2019-04-21
resin mysql_Eclipse+resin+mysql 安装及环境配置
2019-04-21
redis的使用 Java_java中使用redis
2019-04-21
java 数组元素位置_Java – 在数组中获取元素位置
2019-04-21
c 泛型与java泛型_C ++和Java中的“泛型”类型之间有什么区别?
2019-04-21
java 返回实体对象_java 封装返回结果实体类 返回结果以及错误信息
2019-04-21
java web 防止sql注入攻击_JavaWeb防注入知识点(一)
2019-04-21
java ssm 异常分类_SSM项目常见的异常与处理提示(一)
2019-04-21
java定义矩形类_Java定义矩形类
2019-04-21
java变量怎么变常量_Java的常量与变量是什么?怎么学习呀?
2019-04-21
java开发招聘试题_客户化开发招聘试题-Java开发.doc
2019-04-21
java jdk win10 1335_win10下安装java jdk,tomcat
2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么?
2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳
2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3
2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法
2019-04-21