題意：
給定長度為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("");} }
?
