In the i-th query, you are given two integers lili and riri. Consider the subsequence ali,ali+1,ali+2,⋯,ariali,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)kip1(i),p2(i),⋯,pki(i) (in ascending order, i.e.,p(i)1<p(i)2<⋯<p(i)kip1(i)<p2(i)<⋯<pki(i)).
Note that kiki is the number of different integers in this subsequence. You should output p(i)⌈ki2⌉p⌈ki2⌉(i)for the i-th query.
InputIn the first line of input, there is an integer T (T≤2T≤2) denoting the number of test cases.
Each test case starts with two integers n (n≤2×105n≤2×105) and m (m≤2×105m≤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×105a1,a2,⋯,an,0≤ai≤2×105).
There are two integers lili and riri 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)li‘,ri‘(1≤li‘≤n,1≤ri‘≤n). As a result, the problem became more exciting.
We can denote the answers as ans1,ans2,⋯,ansmans1,ans2,⋯,ansm. Note that for each test case ans0=0ans0=0.
You can get the correct input li,rili,ri from what you read (we denote them as l‘i,r‘ili‘,ri‘)by the following formula:
OutputYou should output one single line for each test case.
For each test case, output one line “Case #x: p1,p2,⋯,pmp1,p2,⋯,pm”, where x is the case number (starting from 1) and p1,p2,⋯,pmp1,p2,⋯,pm 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区间内的去重后的中位数所在的位置。
思路：考虑使用主席树来倒着将数组里面的数字插入主席树，每次插入一个数字a[i]，在该树的位置 i 加一，然后判断其是否前面出现过，如果出现过，则在前一棵树的pre[a[i]]的位置减一；
然后只要查询root[L]的L到R区间得和就是L到R区间的数字的种类，然后再去查找root[L]中的第K小的数字在那个位置即可。
参考代码：
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second #define mkp make_pair typedef long long ll; const int INF=0x3f3f3f3f; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=2e5+10; int T,n,m,cnt,a[maxn],rt[maxn],pre[maxn],ans[maxn]; struct Node{ int ls,rs; int sum; } tr[maxn*40]; void update(int &x,int y,int l,int r,int pos,int val) { tr[++cnt]=tr[y];tr[cnt].sum+=val;x=cnt; if(l==r) return ; int mid=l+r>>1; if(pos<=mid) update(tr[x].ls,tr[y].ls,l,mid,pos,val); else update(tr[x].rs,tr[y].rs,mid+1,r,pos,val); } int Query(int t,int l,int r,int L,int R) { if(L<=l&&r<=R) return tr[t].sum; int mid=l+r>>1,ret=0; if(L<=mid) ret+=Query(tr[t].ls,l,mid,L,R); if(R>mid) ret+=Query(tr[t].rs,mid+1,r,L,R); return ret; } int GetKth(int t,int l,int r,int k) { if(l==r) return l; int mid=l+r>>1,num=tr[tr[t].ls].sum; if(k<=num) return GetKth(tr[t].ls,l,mid,k); else return GetKth(tr[t].rs,mid+1,r,k-num); } int main() { T=read(); for(int cas=1;cas<=T;++cas) { memset(pre,0,sizeof(pre)); memset(rt,0,sizeof(rt)); n=read();m=read(); cnt=0; for(int i=1;i<=n;++i) a[i]=read(); int L,R; ans[0]=0; for(int i=n;i>=1;--i) { if(!pre[a[i]]) update(rt[i],rt[i+1],1,n,i,1),pre[a[i]]=i; else { update(rt[i],rt[i+1],1,n,i,1); update(rt[i],rt[i],1,n,pre[a[i]],-1); pre[a[i]]=i; } } for(int i=1;i<=m;++i) { L=read();R=read(); L=((L+ans[i-1])%n)+1; R=((R+ans[i-1])%n)+1; if(L>R) swap(L,R); int num=Query(rt[L],1,n,L,R)+1>>1; ans[i]=GetKth(rt[L],1,n,num); } printf("Case #%d:",cas); for(int i=1;i<m;++i) printf(" %d",ans[i]); printf(" %d ",ans[m]); } return 0; }