首页 > 代码库 > hdu 5919 主席树(区间不同数的个数 + 区间第k大)
hdu 5919 主席树(区间不同数的个数 + 区间第k大)
Sequence II
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 849 Accepted Submission(s): 204
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.
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:
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.
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
/*hdu 5919 主席树(区间不同数的个数 + 区间第k大)problem:给你n个数字,和m个查询.将[l,r]之间数第一次出现的位置信息弄成一个新的数组,然后找出其中k/2大的数.(k为位置的数量)solve:通过主席树能够找出[l,r]之间有多少个不同的数,然后利用再用一个查询找出第k大的即可.(都是类似与线段树的操作, T[i]存的是[1,n]的信息, 尽管说的只是[i,n] ,只是[1,i-1]的还没更新而已. 所以查询的时候出了点问题)hhh-2016-10-07 16:48:19*/#include <algorithm>#include <iostream>#include <cstdlib>#include <stdio.h>#include <cstring>#include <vector>#include <math.h>#include <queue>#include <set>#include <map>//#define lson i<<1//#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn = 200100;const int N = maxn * 100;template<class T> void read(T&num){ char CH; bool F=false; for(CH=getchar(); CH<‘0‘||CH>‘9‘; F= CH==‘-‘,CH=getchar()); for(num=0; CH>=‘0‘&&CH<=‘9‘; num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p){ if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);}int lson[N],rson[N],c[N];int a[maxn],T[maxn];int tot,n,m;int build(int l,int r){ int root = tot++; c[root ] = 0; if(l != r) { int mid = (l+r)>>1; lson[root] = build(l,mid); rson[root] = build(mid+1,r); } return root;}int update(int root,int pos,int val){ int newroot = tot ++ ,tmp= newroot; c[newroot] = c[root] + val; int l = 1,r = n; while(l < r) { int mid = (l + r) >> 1; if(pos <= mid) { lson[newroot] = tot++; rson[newroot] = rson[root]; newroot = lson[newroot] ; root = lson[root]; r = mid; } else { lson[newroot] = lson[root],rson[newroot] = tot++; newroot = rson[newroot],root = rson[root]; l = mid + 1; } c[newroot] = c[root] + val; } return tmp;}int query(int root,int pos){ int cnt = 0; int l = 1,r = n; while(pos < r) { int mid = (l + r) >> 1; if(pos <= mid) { root = lson[root]; r = mid; } else { cnt += c[lson[root]]; root = rson[root]; l = mid + 1; } } return cnt + c[root];}int Find(int root,int k){ int l = 1,r = n; while(l <= r) { int mid = (l + r) >> 1; if(l == r) return l; if(c[lson[root]] >= k) { root = lson[root]; r = mid; } else { k -= c[lson[root]]; root = rson[root]; l = mid +1 ; } }}int main(){ int t,cas = 1;// freopen("in.txt","r",stdin); read(t); while(t--) { tot = 0; read(n),read(m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); T[n + 1] = build(1,n); map<int,int> mp; for(int i = n; i >= 1; i--) { if(mp.find(a[i]) == mp.end()) { T[i] = update(T[i + 1],i,1); } else { int tp = update(T[i+1],mp[a[i]],-1); T[i] = update(tp,i,1); } mp[a[i]] = i; } int ans = 0; int l,r; printf("Case #%d:",cas++); for(int i = 1; i <= m; i++) { read(l),read(r);// cout << l <<" " <<r << endl; l = (l + ans) % n + 1; r = (r + ans)%n + 1; if(l > r) swap(l,r); int num = (query(T[l],r)+1) >> 1;// if(!num) num = 1; ans = Find(T[l],num); printf(" %d",ans); } printf("\n"); } return 0;}
hdu 5919 主席树(区间不同数的个数 + 区间第k大)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。