Sequence II
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.
5 2
3 3 1 5 4
2 2
4 4
5 2
2 5 2 1 2
2 3
2 4
Case #2: 3 1
nn，有mm次查询，每次查询一个区间[l,r][l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 2e5 + , M = 1e6, mod = 1e9+, inf = 2e9; int T,n,q,a[N],l[N*],r[N*],v[N*],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)>>;
if(k <= mid) update(l[x], l[y], ll, mid, k,c);
else update(r[x], r[y], mid + , 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 >> , res = ;
if (s <= mid) res += query(l[x], ll, mid, s, t);
if (t > mid) res += query(r[x], mid + , rr, s, t);
return res;
} int finds(int x,int ll,int rr,int k) {
if(ll == rr) return ll;
int mid = ll + rr >> ;
if(v[l[x]] >= k) return finds(l[x],ll,mid,k);
else return finds(r[x],mid+,rr,k-v[l[x]]);
} int main() {
int cas = ;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&q);
sz = ;
memset(last,,sizeof(last));
memset(v,,sizeof(v));
memset(l,,sizeof(l));
memset(r,,sizeof(r));
ans[] = ;
root[n+] = ;
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
for(int i = n; i >= ; --i) {
int x = root[i] = ;
update(root[i+],x,,n,i,);
if(last[a[i]]) {
update(x,root[i],,n,last[a[i]],-);
} else root[i] = x;
last[a[i]] = i;
}
int L,R;
for(int i = ; i <= q; ++i) {
scanf("%d%d",&L,&R);
L = ((L + ans[i-])%n) + ;
R = ((R + ans[i-])%n) + ;
if(L > R) swap(L,R);
int sum = query(root[L],,n,L,R) + >> ;
ans[i] = finds(root[L],,n,sum);
}
printf("Case #%d: ",++cas);
for(int i = ; i < q; ++i) printf("%d ",ans[i]);
cout<<ans[q]<<endl;
}
return ;
}