2016-10-06

HDU 5919 Sequence II【主席树】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5919

题意：

给定长度为$n$的序列，$m$个询问，对于每个询问中的区间，统计该区间内第一次出现的数的位置的中位数。
数据范围：$n \le 2e5, m \le 2e5$

分析：

在计算区间内不同数个数时，我们是记录每个元素最后一次出现的位置，访问到这个元素时就在上一次-1，现在的位置+1，正着插入倒着插入都一样，显然这题依然是这个套路。
但是对于求中位数，由于我们记录的是每个元素最后出现的位置，倒着插入处理起来更方便一些，直接在以$t[l]$为根的树中找第几个元素即可。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 2e5 + 5, maxm = 50 * maxn;
int lson[maxm], rson[maxm], t[maxm], tree[maxm];
int last[maxn];
int tot;
int build(int l, int r)
{
    int root = tot++;
    tree[root] = 0;
    if(l == r) return root;
    int mid = l + r >> 1;
    lson[root] = build(l, mid);
    rson[root] = build(mid + 1, r);
    return root;
}
int update(int root, int l, int r, int num, int val)
{
    int newroot = tot++;
    tree[newroot] = tree[root] + val;
    if(l == r) return newroot;
    int mid = l + r >> 1;
    if(num <= mid){
        lson[newroot] = update(lson[root], l, mid, num, val);
        rson[newroot] = rson[root];
    }else{
        rson[newroot] = update(rson[root], mid + 1, r, num, val);
        lson[newroot] = lson[root];
    }
    return newroot;
}
int query(int L, int R, int l, int r, int i)
{
    if(l == L && R == r) return tree[i];
    int mid = l + r >> 1;
    if(R <= mid) return query(L, R, l, mid, lson[i]);
    else if(L > mid) return query(L, R, mid + 1, r, rson[i]);
    else return query(L, mid, l, mid, lson[i]) + query(mid + 1, R, mid + 1, r, rson[i]);
}
int Query(int i, int k, int l, int r)
{
    if(l == r) return l;
    int mid = l + r >> 1;
    if(tree[lson[i]] >= k) return Query(lson[i], k, l, mid);
    else return Query(rson[i], k - tree[lson[i]], mid + 1, r);
}
int a[maxn];
int main (void)
{
    int T;scanf("%d", &T);
    for(int tt = 1; tt <= T; ++tt){
        int n, m; scanf("%d%d", &n, &m);
        tot = 0;
        t[n + 1] = build(1, n);
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a[i]);
            last[a[i]] = -1;
        }
        for(int i = n; i >= 1; --i){
			if(last[a[i]] == -1){
				t[i] = update(t[i + 1], 1, n, i, 1);
			}else{
				t[i] = update(t[i + 1], 1, n, last[a[i]], -1);
				t[i] = update(t[i], 1, n, i, 1);
			}
			last[a[i]] = i;
        }
        int l, r;
        int ans = 0;
        int tmp;
        printf("Case #%d:", tt);
        while(m--){
            scanf("%d%d", &l, &r);
            l = (l + ans) % n + 1;
            r = (r + ans) % n + 1;
            if(l > r) swap(l, r);
            tmp = query(l, r, 1, n, t[l]);
            ans = Query(t[l], tmp + 1 >> 1, 1,n);
            printf(" %d", ans);
        }
        puts("");
    }
    return 0;
}