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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int maxn=2e5+;
int T,n,m,cnt,a[maxn],rt[maxn],pre[maxn],ans[maxn];
struct Node{
int ls,rs;
int sum;
} tr[maxn*]; 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>>;
if(pos<=mid) update(tr[x].ls,tr[y].ls,l,mid,pos,val);
else update(tr[x].rs,tr[y].rs,mid+,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>>,ret=;
if(L<=mid) ret+=Query(tr[t].ls,l,mid,L,R);
if(R>mid) ret+=Query(tr[t].rs,mid+,r,L,R);
return ret;
} int GetKth(int t,int l,int r,int k)
{
if(l==r) return l;
int mid=l+r>>,num=tr[tr[t].ls].sum;
if(k<=num) return GetKth(tr[t].ls,l,mid,k);
else return GetKth(tr[t].rs,mid+,r,k-num);
} int main()
{
T=read();
for(int cas=;cas<=T;++cas)
{
memset(pre,,sizeof(pre));
memset(rt,,sizeof(rt));
n=read();m=read(); cnt=;
for(int i=;i<=n;++i) a[i]=read();
int L,R; ans[]=; for(int i=n;i>=;--i)
{
if(!pre[a[i]]) update(rt[i],rt[i+],,n,i,),pre[a[i]]=i;
else
{
update(rt[i],rt[i+],,n,i,);
update(rt[i],rt[i],,n,pre[a[i]],-);
pre[a[i]]=i;
}
}
for(int i=;i<=m;++i)
{
L=read();R=read();
L=((L+ans[i-])%n)+;
R=((R+ans[i-])%n)+;
if(L>R) swap(L,R);
int num=Query(rt[L],,n,L,R)+>>;
ans[i]=GetKth(rt[L],,n,num);
}
printf("Case #%d:",cas);
for(int i=;i<m;++i) printf(" %d",ans[i]);
printf(" %d\n",ans[m]);
} return ;
}