首页 > 代码库 > HDU 5919 Sequence II 主席树
HDU 5919 Sequence II 主席树
Sequence II
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
题意：
给定一个序列
nn，有mm次查询，每次查询一个区间[l,r][l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。题解：
强制在线
利用主席树求区间不同数的个数
这里有个技巧
倒着插入主席树
在寻找位置的中位数上就可以一个log解决了
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;typedef long long LL;const int N = 2e5 + 10, M = 1e6, mod = 1e9+7, inf = 2e9;int T,n,q,a[N],l[N*36],r[N*36],v[N*36],sz,root[N],ans[N],last[N];void update(int x, int &y, int ll, int rr, int k,int c) { y = ++sz; v[y] = v[x] + c; r[y] = r[x]; l[y] = l[x]; if(ll == rr) return ; int mid = (ll+rr)>>1; if(k <= mid) update(l[x], l[y], ll, mid, k,c); else update(r[x], r[y], mid + 1, rr, k,c);}int query(int x,int ll,int rr,int s,int t) { if (s <= ll && rr <= t) return v[x]; int mid = ll + rr >> 1, res = 0; if (s <= mid) res += query(l[x], ll, mid, s, t); if (t > mid) res += query(r[x], mid + 1, rr, s, t); return res;}int finds(int x,int ll,int rr,int k) { if(ll == rr) return ll; int mid = ll + rr >> 1; if(v[l[x]] >= k) return finds(l[x],ll,mid,k); else return finds(r[x],mid+1,rr,k-v[l[x]]);}int main() { int cas = 0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); sz = 0; memset(last,0,sizeof(last)); memset(v,0,sizeof(v)); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); ans[0] = 0; root[n+1] = 0; for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); for(int i = n; i >= 1; --i) { int x = root[i] = 0; update(root[i+1],x,1,n,i,1); if(last[a[i]]) { update(x,root[i],1,n,last[a[i]],-1); } else root[i] = x; last[a[i]] = i; } int L,R; for(int i = 1; i <= q; ++i) { scanf("%d%d",&L,&R); L = ((L + ans[i-1])%n) + 1; R = ((R + ans[i-1])%n) + 1; if(L > R) swap(L,R); int sum = query(root[L],1,n,L,R) + 1 >> 1; ans[i] = finds(root[L],1,n,sum); } printf("Case #%d: ",++cas); for(int i = 1; i < q; ++i) printf("%d ",ans[i]); cout<<ans[q]<<endl; } return 0;}
HDU 5919 Sequence II 主席树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。