HDU
题意：
给定长度为n的序列和q次询问。每次询问给出一个区间（L，R），求出区间内每个数第一次出现位置的中位数，强制在线。
题解：
用主席树从右向左的插入点。对于当前点i，如果a[i]出现过，则把原位置-1，i处+1。这样保证了每个点只出现1次。
对于询问区间（L，R），求出L节点[L,R]的值即为区间内有多少不同的数。最后就是主席树求k_th的操作。倒着插省去了二分的复杂度。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 2e5+10; int t, n, q, tot; int l, r; int a[N]; int root[N], vis[N]; int ans[N]; struct node { int l, r, sum; }tre[N*40]; void update(int l, int r, int &x, int y, int pos, int val) { tre[++tot] = tre[y]; tre[tot].sum += val; x = tot; if(l==r) return ; int mid = l+r>>1; if(pos<=mid) update(l, mid, tre[x].l, tre[y].l, pos, val); else update(mid+1, r, tre[x].r, tre[y].r, pos, val); } int query(int l, int r, int x, int ql, int qr) { if(ql<=l&&r<=qr) return tre[x].sum; int mid = l+r>>1; int res = 0; if(ql<=mid) res += query(l, mid, tre[x].l, ql, qr); if(qr>mid) res += query(mid+1, r, tre[x].r, ql, qr); return res; } int find_kth(int l, int r, int x, int k) { if(l==r) return l; int mid = l+r>>1; int t = tre[tre[x].l].sum; if(t>=k) return find_kth(l, mid, tre[x].l, k); return find_kth(mid+1, r, tre[x].r, k-t); } int main() { scanf("%d", &t); for(int casee = 1; casee <= t; casee++) { memset(vis, 0, sizeof(vis)); tot = 0; scanf("%d%d", &n, &q); root[n+1] = 0; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = n; i >= 1; i--) { update(1, n, root[i], root[i+1], i, 1); if(vis[a[i]]) update(1, n, root[i], root[i], vis[a[i]], -1); vis[a[i]] = i; } ans[0] = 0; printf("Case #%d: ", casee); for(int i = 1; i <= q; i++) { scanf("%d%d", &l, &r); int tt = l; l = min((l+ans[i-1])%n+1, (r+ans[i-1])%n+1); r = max((tt+ans[i-1])%n+1, (r+ans[i-1])%n+1); int k = query(1, n, root[l], l, r); ans[i] = find_kth(1, n, root[l], (k+1)/2); printf("%d", ans[i]); if(i!=q) printf(" "); } puts(""); } }