Sequence II(主席树)

题意：

给定一个长度为的序列和次询问，每次询问给定一个区间，求出现的不同数中，第个数的位置

题解：

倒序遍历，对每个位置建一棵树，记录每个数字上次出现的位置并更新，那么每次询问就是对第棵树求区间的和，并求第大即可，理解清楚本质就是主席树裸题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct node
{
    int l, r, sum;
} T[maxn * 50];
int root[maxn], a[maxn], ans[maxn], cnt, pre[maxn];
void init(int rt)
{
    cnt = 1;
    ans[0] = 0;
    memset(root, 0, sizeof(root));
    T[rt].l = T[rt].r = T[rt].sum = 0;
    memset(pre, 0, sizeof(pre));
}
void update(int l, int r, int &rt, int pos, int val)
{
    T[cnt] = T[rt];
    rt = cnt++;
    T[rt].sum += val;
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (pos <= mid)
        update(l, mid, T[rt].l, pos, val);
    else
        update(mid + 1, r, T[rt].r, pos, val);
}
int query(int l, int r, int L, int R, int rt)
{
    if (L <= l && r <= R)
        return T[rt].sum;
    int mid = l + r >> 1;
    int ans = 0;
    if (L <= mid)
        ans += query(l, mid, L, R, T[rt].l);
    if (R > mid)
        ans += query(mid + 1, r, L, R, T[rt].r);
    return ans;
}
int Query(int rt, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = l + r >> 1;
    int sum = T[T[rt].l].sum;
    if (sum >= k)
        return Query(T[rt].l, l, mid, k);
    else
        return Query(T[rt].r, mid + 1, r, k - sum);
}
int main()
{
    int t, caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        int n, q;
        scanf("%d%d", &n, &q);
        init(n + 1);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        init(n + 1);
        for (int i = n; i >= 1; i--)
        {
            root[i] = root[i + 1];
            if (pre[a[i]])
                update(1, n, root[i], pre[a[i]], -1);
            update(1, n, root[i], i, 1);
            pre[a[i]] = i;
        }
        for (int i = 1; i <= q; i++)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            l = (l + ans[i - 1]) % n + 1;
            r = (r + ans[i - 1]) % n + 1;
            if (l > r)
                swap(l, r);
            int k = query(1, n, l, r, root[l]);
            k = (k + 1) / 2;
            ans[i] = Query(root[l], 1, n, k);
        }
        printf("Case #%d: ", ++caseN);
        for (int i = 1; i <= q; i++)
            printf("%d%c", ans[i], i == q ? '\n' : ' ');
    }
    return 0;
}