HDU【5919】Sequence II(主席树)

题意
给出n(n ≤ 2e5)个数，m(m ≤ 2e5)个询问，每个数的大小(0 < ai ≤ 2e5)。对于每个询问输入l,r,表示al ... ar这个区间得到的每个数第一次出现的位置下标的排列，假设这个区间有k个不同的数，得到的排列是p1 < p2 < p3 < ... < pk，求第(k + 1) / 2个数是多少？

题解
对于给出的数列，我们可以从后往前依次插入主席树(如果该数字之前出现过，则在之前下标处减1)，这样我们可以用O(logn)的时间复杂度在第l棵线段树上求出给定l到r区间有多少个不同的数字(假设有k个)，然后再用O(logn)的时间复杂度在第l棵线段树上求第(k + 1) / 2小的数就好了，总时间复杂度O(nlogn)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct node{
    int ls, rs, val;
}tree[maxn * 40];
int arr[maxn], rot[maxn], pos[maxn], ans[maxn];
int tot, t, n, m;

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(int x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

inline void init(){
    tot = 0;
    memset(pos, 0, sizeof(pos));
}

int Build(int l, int r){
    int root = ++tot;
    if(l == r) return root;
    int mid = (l + r) >> 1;
    tree[root].ls = Build(l, mid);
    tree[root].rs = Build(mid + 1, r);
    return root;
}

int UpDate(int root, int l, int r, int vis, int val){
    int o = ++tot;
    tree[o].ls = tree[root].ls;
    tree[o].rs = tree[root].rs;
    tree[o].val = tree[root].val + val;
    if(l == r) return o;
    int mid = (l + r) >> 1;
    if(vis <= mid) tree[o].ls = UpDate(tree[o].ls, l, mid, vis, val);
    else tree[o].rs = UpDate(tree[o].rs, mid + 1, r, vis, val);
    return o;
}

int Query(int root, int l, int r, int x, int y){
    if(l >= x && r <= y) return tree[root].val;
    int mid = (l + r) >> 1;
    if(y <= mid) return Query(tree[root].ls, l, mid, x, y);
    else if(x > mid) return Query(tree[root].rs, mid + 1, r, x, y);
    else return Query(tree[root].ls, l, mid, x, mid) + Query(tree[root].rs, mid + 1, r, mid + 1, y);
}

int Find(int root, int l, int r, int k){
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int res = tree[tree[root].ls].val;
    if(res >= k) return Find(tree[root].ls, l, mid, k);
    else return Find(tree[root].rs, mid + 1, r, k - res);
}

int main(){
    t = read();
    for(int tt = 1; tt <= t; tt++){
        init();
        n = read(), m = read();
        rot[n + 1] = Build(1, n);
        for(int i = 1; i <= n; i++) arr[i] = read();
        for(int i = n; i >= 1; i--){
            if(pos[arr[i]]){
                rot[i] = UpDate(rot[i + 1], 1, n, pos[arr[i]], -1);
                rot[i] = UpDate(rot[i], 1, n, i, 1);
            }
            else{
                rot[i] = UpDate(rot[i + 1], 1, n, i, 1);
            }
            pos[arr[i]] = i;
        }
        for(int ca = 1; ca <= m; ca++){
            int l, r;
            l = read(), r = read();
            l = (l + ans[ca - 1]) % n + 1;
            r = (r + ans[ca - 1]) % n + 1;
            if(l > r) swap(l, r);
            int k = (Query(rot[l], 1, n, l, r) + 1) / 2;
            ans[ca] = Find(rot[l], 1, n, k);
        }
        printf("Case #%d:", tt);
        for(int i = 1; i <= m; i++) putchar(' '), print(ans[i]);
        putchar('\n');
    }

    return 0;
}