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.
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:
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.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
const int N=2e5+;
int a[N],ans[N];
int t[N],tot;
map<int,int>mp;
struct Node
{
int l,r;
int num;
}tr[*N];
void init()
{
tot=;
mp.clear();
}
int build(int l,int r)
{
int ii=tot++;
tr[ii].num=;
if(l<r)
{
int mid=(l+r)>>;
tr[ii].l=build(l,mid);
tr[ii].r=build(mid+,r);
}
return ii;
}
int update(int now,int l,int r,int x,int y)
{
int ii=tot++;
tr[ii].num=tr[now].num+y;
tr[ii].l=tr[now].l;
tr[ii].r=tr[now].r;
if(l<r)
{
int mid=(l+r)>>;
if(x<=mid) tr[ii].l=update(tr[now].l,l,mid,x,y);
else tr[ii].r=update(tr[now].r,mid+,r,x,y);
}
return ii;
}
int query(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tr[now].num;
int mid=(l+r)>>;
int sum=;
if(mid>=L) sum+=query(tr[now].l,l ,mid,L,R);
if(mid<R) sum+=query(tr[now].r,mid+,r,L,R);
return sum;
}
int finds(int now,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>;
if(tr[tr[now].l].num>=k) return finds(tr[now].l,l,mid,k);
else return finds(tr[now].r,mid+,r,k-tr[tr[now].l].num);
}
int main()
{
int T,Case=; cin>>T;
while(T--)
{
init();
int n,m; scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
t[n+]=build(,n);
for(int i=n;i>=;i--)
{
if(mp.count(a[i]))
{
int tmp=update(t[i+],,n,mp[a[i]],-);
t[i]=update(tmp,,n,i,);
}
else t[i]=update(t[i+],,n,i,);
mp[a[i]]=i;
}
ans[]=;
for(int i=;i<=m;i++)
{
int x,y; scanf("%d%d",&x,&y);
int l=min((x+ans[i-])%n+,(y+ans[i-])%n+);
int r=max((x+ans[i-])%n+,(y+ans[i-])%n+);
int k=(query(t[l],,n,l,r)+)/;
ans[i]=finds(t[l],,n,k);
}
printf("Case #%d:",Case++);
for(int i=;i<=m;i++) printf(" %d",ans[i]);
puts("");
}
return ;
}
/**
10 4
1 1 1 1 1 1 1 1 1 1
3 6
6 8
7 10
2 5
*/