http://acm.split.hdu.edu.cn/showproblem.php?pid=5919
题意：
给出一串序列，每次给出区间，求出该区间内不同数的个数k和第一个数出现的位置（将这些位置组成一个新的序列），输出这里面的第ceil（k/2）个数。
思路：
因为每个区间只需要统计第一个数出现的位置，那么从右往左来建树，如果该数没有出现，那么就将该位置+1，否则要将上一次出现的位置-1后再在该位置+1。
统计不同数的个数很简单，就是线段树查询。
查询出第k小的数也很简单，因为我们是从后往前建树的，那么t[l]这棵树里面的元素就是从l开始的数组，直接线段树查询第k个数即可。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = *1e5+; int tot,n,m;
int a[maxn],pre[maxn],rot[maxn]; struct node
{
int l,r,num;
}t[maxn*]; int build(int l, int r)
{
int root=++tot;
t[root].num=;
if(l==r) return root;
int mid=(l+r)>>;
t[root].l=build(l,mid);
t[root].r=build(mid+,r);
return root;
} int update(int root, int pos, int d)
{
int now = ++tot;
int tmp = now;
t[tot].num = t[root].num + d;
int l = , r = n;
while(l<r)
{
int mid = (l+r)>>;
if(pos<=mid)
{
t[now].l = ++tot;
t[now].r = t[root].r;
root = t[root].l;
now = tot;
r = mid;
}
else
{
t[now].l = t[root].l;
t[now].r = ++tot;
root = t[root].r;
now = tot;
l = mid + ;
}
t[now].num = t[root].num + d;
}
return tmp;
} int query(int ql ,int qr, int l, int r, int root)
{
if(ql<=l && qr>=r) return t[root].num;
int mid = (l+r)>>;
int ans = ;
if(ql<=mid) ans+=query(ql,qr,l,mid,t[root].l);
if(qr>mid) ans+=query(ql,qr,mid+,r,t[root].r);
return ans;
} int calc(int l,int r,int k,int root)
{
if(l==r) return l;
int mid = (l+r)>>;
if(t[t[root].l].num>=k) return calc(l,mid,k,t[root].l);
else return calc(mid+,r,k-t[t[root].l].num,t[root].r);
} int main()
{
//freopen("in.txt","r",stdin);
int T;
int kase = ;
scanf("%d",&T);
while(T--)
{
tot=;
int bef=;
memset(pre,-,sizeof(pre));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
rot[n+] = build(,n);
for(int i=n;i>;i--)
{
if(pre[a[i]] == -) rot[i] = update(rot[i+],i,);
else
{
int tmp = update(rot[i+],pre[a[i]],-);
rot[i] = update(tmp,i,);
}
pre[a[i]] = i ;
}
printf("Case #%d:",++kase);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int ll = (l + bef)%n + ;
int rr = (r + bef)%n + ;
l = min(ll, rr);
r = max(ll, rr);
int k = query(l,r,,n,rot[l]);
k = ceil(k/2.0);
int ans = calc(,n,k,rot[l]);
bef = ans;
printf(" %d",ans);
}
puts("");
}
return ;
}