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 (
T2 ) denoting the number of test cases.
Each test case starts with two integers n (
n2×105 ) and m (
m2×105 ). There are n integers in the next line, which indicate the integers in the sequence(i.e., 
a1,a2,,an,0ai2×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 
li,ri(1lin,1rin) . 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 
li,ri )by the following formula:
li=min{
(li+ansi1) mod n+1,(ri+ansi1) mod n+1}
ri=max{
(li+ansi1) mod n+1,(ri+ansi1) 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  ,求  pk2  

学完主席树就想过来把这题过了,拖到了现在。
这是我参加的第一场区预赛-长春赛站现场赛的题,当时因为不会这道而没进银牌区。
这题也是类似spoj-dquery(感觉这题是主席树精髓啊==),其实会dquery这道题非常容易。
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define rep(i,a,n) for (int i=a;i
=a;i--)#define pb push_back#define fi first#define se secondtypedef vector
VI;typedef long long ll;typedef pair
PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=2e5+100;struct node{ int l,r,sum;}T[maxn*40];int root[maxn];int cnt;void update(int l,int r,int& x,int y,int pos,int val){ T[++cnt]=T[y],x=cnt,T[x].sum+=val; if(l==r) return; int m=(l+r)/2; if(pos<=m) update(l,m,T[x].l,T[y].l,pos,val); else update(m+1,r,T[x].r,T[y].r,pos,val);}int query(int l,int r,int x,int pos){ if(l==r) return T[x].sum; int m=(l+r)/2; if(pos<=m) return query(l,m,T[x].l,pos); else return T[T[x].l].sum+query(m+1,r,T[x].r,pos);}int query1(int l,int r,int x,int k){ if(l==r) return l; int m=(l+r)/2; if(k>T[T[x].l].sum) return query1(m+1,r,T[x].r,k-T[T[x].l].sum); else return query1(l,m,T[x].l,k);}int a[maxn];map
mp;int main(){ int cas; scanf("%d",&cas); int kase=0; while(cas--) { cnt=0; int n,m; scanf("%d%d",&n,&m); memset(T,0,sizeof(T)); memset(root,0,sizeof(root)); mp.clear(); rep(i,1,n+1) scanf("%d",&a[i]); int ans=0,l,r; per(i,1,n+1) { if(mp.find(a[i])==mp.end()) { mp[a[i]]=i; update(1,n,root[i],root[i+1],i,1); } else { update(1,n,root[i],root[i+1],mp[a[i]],-1); update(1,n,root[i],root[i],i,1); mp[a[i]]=i; } } printf("Case #%d: ",++kase); while(m--) { scanf("%d%d",&l,&r); l=(l+ans)%n+1,r=(r+ans)%n+1; if(l>r) swap(l,r); int k=query(1,n,root[l],r); k=(k+1)/2; ans=query1(1,n,root[l],k); printf("%d",ans); if(m) printf(" "); } puts(""); } return 0;}

转载地址:https://blog.csdn.net/fouzhe/article/details/55803885 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Canada Cup 2016 F. Family Photos(贪心,想法,好题)
下一篇:Codeforces Round #397 E. Tree Fold(bfs,想法题,好题)

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.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
java list二分查找_java中的ArrayList和LinkedList的二分查找速度比 | 学步园 2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21