[原创]HDU 5919 Sequence II [主席树]【数据结构】
[原创]HDU 5919 Sequence II [主席树]【数据结构】
2017-03-13 18:16:52 Tabris_ 阅读数：402
博客爬取于 2020-06-14 22:41:16
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61923707
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5919
——————————————————————————————————————
Sequence II
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1654 Accepted Submission(s): 420
Problem Description
Mr. Frog has an integer sequence of length n, which can be denoted as a_1,a_2,⋯,a_n There are m queries.
In the i-th query, you are given two integers l_i and r_i. Consider the subsequence a_{l_{i} },a_{l_{i+1} },a_{l_{i+2} },⋯,a_{r_{i} }.
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×10^5) and m (m≤2×10^5). There are n integers in the next line, which indicate the integers in the sequence(i.e., a_1,a_2,⋯,a_n,0≤a_i≤2×10^5).
There are two integers l_i and r_i 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 ans_1,ans_2,⋯,ans_m. Note that for each test case ans_0=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+ans_{i−1}) \mod n+1,(r‘_i+ans_{i−1}) \mod n+1}
ri=max{(l‘_i+ans_{i−1})\mod n+1,(r‘_i+ans_{i−1}) \mod n+1}
Output
You should output one single line for each test case.
For each test case, output one line “Case #x: p_1,p_2,⋯,p_m”, where x is the case number (starting from 1) and p_1,p_2,⋯,p_m is the answer.
Sample Input
2
5 2
3 3 1 5 4
2 2
4 4
5 2
2 5 2 1 2
2 3
2 4
Sample Output
Case #1: 3 3
Case #2: 3 1
Hint
————————————————————————————————————————————
题目大意：
给定一个长度为 n 的序列，然后有 m 个查询，问你在[l,r]区间中所有不相同元素第一次出现的位置，按这个位置升序以后的中间（向上取整）的那个位置是多少(这个位置指的是原序列)？
解题思路：
因为这个题对l,r的限制，这题强制在线，就不能离线树状数组做了，只能主席树做了，
然后他说在询问区间，不相同元素第一次出现的位置的中间那个，
如果是从正序挂到主席树上的话 确实不好维护，
考虑倒叙插入到主席树上，那么每次都只会记录最左边的数，更新的时候如过当前数出现过就删去之前的那个，
就不需要排序过程了，只需要在区间内找第中间的那个就行了
查询的时候我们只要对 rt[l]进行查找就行了
于是就变成了找区间内不同数的个数，
然后找区间内第 k 大的问题，
这样的话就是主席树的基本操作了，
总体复杂度O(n\log n)
附本题代码
——————————————————————————————————————————————
1 | # include <bits/stdc++.h> |
