解题思路

2016 CCPC 长春的一道银牌题，要求强制在线。用过主席树求区间第 K 大以及区间不同数个数的话基本就是一眼题了，比以前不会主席树的时候用的分块做法不知道高到哪里去了。

按照求区间不同数的做法建树，查询时先查出区间内不同数的个数，除以 2 得到一个数 k，用这个 k 在区间 [l, n] 内查询第 k 大即是题目中询问的中位数。

参考代码

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const int MAXN = 200002;

struct node {
    int sum, l, r;
} hjt[MAXN*40];

int a[MAXN], root[MAXN];
int cnt;
map<int, int> mp;

void Init() {
    cnt = 0;
    mp.clear();
}

inline int CreateNode(int sum, int l, int r) {
    int idx = ++cnt;
    hjt[idx].sum = sum;
    hjt[idx].l = l;
    hjt[idx].r = r;

    return idx;
}

void Insert(int &root, int pre_rt, int pos, int v, int l, int r) {
    root = CreateNode(hjt[pre_rt].sum+v, hjt[pre_rt].l, hjt[pre_rt].r);
    if(l == r) return;
    int m = (l+r) >> 1;
    if(pos <= m)
        Insert(hjt[root].l, hjt[pre_rt].l, pos, v, l, m);
    else Insert(hjt[root].r, hjt[pre_rt].r, pos, v, m+1, r);
}

int QueryNum(int s, int R, int l, int r) {
    if(r <= R) return hjt[s].sum;
    int m = (l+r) >> 1;
    if(R <= m)
        return QueryNum(hjt[s].l, R, l, m);
    else return hjt[hjt[s].l].sum + QueryNum(hjt[s].r, R, m+1, r);
}

int QueryKth(int s, int k, int l, int r) {
    if(l == r) return l;
    int m = (l+r) >> 1;
    int sum = hjt[hjt[s].l].sum;
    if(k <= sum)
        return QueryKth(hjt[s].l, k, l, m);
    else return QueryKth(hjt[s].r, k-sum, m+1, r);
}

int main(int argc, char const *argv[]) {
    int t, n, m, l, r, tmp;
    scanf("%d", &t);
    for(int cs=1; cs<=t; ++cs) {
        Init();
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
        }
        for(int i=n; i>=1; --i) {
            if(!mp[a[i]])
                Insert(root[i], root[i+1], i, 1, 1, n);
            else {
                Insert(tmp, root[i+1], mp[a[i]], -1, 1, n);
                Insert(root[i], tmp, i, 1, 1, n);
            }
            mp[a[i]] = i;
        }
        printf("Case #%d:", cs);
        int ans = 0;
        for(int i=0; i<m; ++i) {
            scanf("%d %d", &l, &r);
            l = (l+ans)%n + 1;
            r = (r+ans)%n + 1;
            if(r < l) swap(l, r);
            int k = (QueryNum(root[l], r, 1, n)+1) / 2;
            ans = QueryKth(root[l], k, 1, n);
            printf(" %d", ans);
        }
        printf("\n");
    }
    
    return 0;
}