题目链接
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.
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:
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.
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),设区间中有k个不同的数,它们在区间中第一次出现的位置为p1,p2 ,……,pk 并且将它们排序p1<p2<……<pk,现在求p[(k+1)/2]的值?
思路:主席树记录当前数出现的位置,即每次在当前数出现的位置(下标)+1,对于序列数a[1]~a[n]建立主席树时,如果当前这个数之前出现过,那么在当前这个版本线段树上对前一次出现的位置-1,在当前位置+1,这样就可以求出区间不同数的个数。现在要求出区间第k大,那么可以从a[n]~a[1]建立线段树,然后直接求k大就行。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int a[N],ans[N];
int t[N],tot;
map<int,int>mp;
struct Node
{
int l,r;
int num;
}tr[40*N];
void init()
{
tot=0;
mp.clear();
}
int build(int l,int r)
{
int ii=tot++;
tr[ii].num=0;
if(l<r)
{
int mid=(l+r)>>1;
tr[ii].l=build(l,mid);
tr[ii].r=build(mid+1,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)>>1;
if(x<=mid) tr[ii].l=update(tr[now].l,l,mid,x,y);
else tr[ii].r=update(tr[now].r,mid+1,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)>>1;
int sum=0;
if(mid>= |