这道题是主席树好题啊……
####### 题目大意：给定一个序列，每次给定一段区间，区间内所有不同的数第一次出现的位置排成一个序列，求这个序列的中位数。
其实求中位数并不是很难，只要我们能把这个序列中不同的数出现的位置都求出，就能很直接的转化为用主席树求静态第k小的问题。首先我们考虑一下如何计算区间内有多少个不同的数，如果离线的话这个问题可以用莫队或者树状数组处理，但是本题因为强制在线，所以需要用主席树处理。具体的方法很巧妙，因为我们要维护的是最左边的第一次出现的值，所以我们倒着插入。因为维护的是位置，所以我们用第(i)棵主席树维护区间(i~r)内所有不同的数出现的次数（也就是主席树以位置为值域），以每个数的位置为权值在树上进行二分。当一个数在一起出现过一次的时候，我们就先找到它原来所在的位置，把它从树上删除，之后再在它的新位置加入这个数，更改这个数原来的位置即可。
至于查询的时候，我们就可以只查询第l棵主席树上的情况了，我们像线段树一样(query)一下这个树上有多少不同的数，之后仿照模板 ，在树上二分求静态第k小即可。
然后还有一道题是它的弱化版here 此题不强制在线不用求第k大，不过数的范围大了一点，所以需要把记录位置的数组稍微开大一点才行。
本题千万要注意一下输出格式！修改的时候一定要按代码中顺序修改，如果倒过来的话，一旦这个数是第一次出现就会出错（没继承上一个根的信息）。
看一下代码。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;
const int M = 200005;
const int N = 2000005;
const int INF = 1000000009;
const double eps = 1e-7;
int read()
{
int ans = 0,op = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') op = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
ans *= 10;
ans += ch - '0';
ch = getchar();
}
return ans * op;
}
struct node
{
int lson,rson,v;
}t[N<<2];
int T,n,m,l,r,a[M],pos[M],idx,root[M],la;
void modify(int old,int &p,int l,int r,int pos,int val)
{
p = ++idx;
t[p].lson = t[old].lson,t[p].rson = t[old].rson,t[p].v = t[old].v + val;
if(l == r) return;
int mid = (l+r) >> 1;
if(pos <= mid) modify(t[old].lson,t[p].lson,l,mid,pos,val);
else modify(t[old].rson,t[p].rson,mid+1,r,pos,val);
}
int query(int p,int l,int r,int kl,int kr)
{
if(l == kl && r == kr) return t[p].v;
int mid = (l+r) >> 1;
if(kr <= mid) return query(t[p].lson,l,mid,kl,kr);
else if(kl > mid) return query(t[p].rson,mid+1,r,kl,kr);
else return query(t[p].lson,l,mid,kl,mid) + query(t[p].rson,mid+1,r,mid+1,kr);
}
int ask(int p,int l,int r,int k)
{
if(l == r) return l;
int mid = (l+r) >> 1;
if(t[t[p].lson].v >= k) return ask(t[p].lson,l,mid,k);
else return ask(t[p].rson,mid+1,r,k - t[t[p].lson].v);
}
void clear()
{
memset(root,0,sizeof(root));
memset(pos,0,sizeof(pos));
idx = la = 0;
}
int main()
{
//freopen("1.out","w",stdout);
T = read();
rep(i,1,T)
{
printf("Case #%d:",i);
n = read(),m = read();
rep(j,1,n) a[j] = read();
per(j,n,1)
{
modify(root[j+1],root[j],1,n,j,1);
if(pos[a[j]]) modify(root[j],root[j],1,n,pos[a[j]],-1); //Accepted
pos[a[j]] = j;
}
rep(j,1,m)
{
l = read(),r = read();
l = (l + la) % n + 1,r = (r + la) % n + 1;
if(l > r) swap(l,r);
//printf("#%d %d
",l,r);
int cur = query(root[l],1,n,l,r);
la = ask(root[l],1,n,(cur+1)>>1);
printf(" %d",la);
}
enter;
clear();
}
return 0;
}