2016 CCPC 长春 I 题 | hdu 5919 Sequence II （可持久化线段树求区间第k大+可持久化线段树求区间不同数个数）

2017-10-18 · 2 min read · 主席树区间第k大可持久化数据结构

题目链接

题意：

给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

思路：

先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。

对于求区间中不同数的个数，离线可以随便线段树，树状数组，或者莫队也行（观察到数据范围<=2E5)

在线的话，就只能可持久化线段树了。

看到一些题解中说要倒序处理...但是之前写求区间不同数的个数，我都是倒序处理的啊？（回想一下，当时似乎正序处理也行...

倒序处理是为了，处理到第i个的时候，第i个一定是当前后缀区间中，第一个出现的...

然后第二个问题，求区间中第k大的下标，离线做法不少，在线的话，也可以用可持久化线段树求。

所以感觉就是板子题，可持久化线段树的2个应用放在了一起orz

 1#include <cstdio>
 2#include <cstring>
 3#include <algorithm>
 4#include <queue>
 5#include <iostream>
 6#include <string>
 7#include <cmath>
 8#include <vector>
 9#include <set>
10#include <map>
11#include <bitset>
12#include <stack>
13using namespace std;

#define MP make_pair
#define PB push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define X first
#define Y second

1typedef long long LL;
2typedef long double LD;
3const int INF = 0x3f3f3f3f;

typedef pair<LL, LL> pii;

const int N = 2e5 + 10;
const int M = 30 * 2 * N;

 1int ls[M], rs[M], root[N], tot, data[M];
 2inline int new_node(int lst = 0) {
 3    ls[++ tot] = ls[lst];
 4    rs[tot] = rs[lst];
 5    data[tot] = data[lst];
 6    return tot;
 7}
 8void build(int l, int r, int &rt) {
 9    rt = new_node();
10    if(l == r) return ;
11    int m = (l + r) >> 1;
12    build(l, m, ls[rt]);
13    build(m + 1, r, rs[rt]);
14}
15void update(int pos, int val, int lst, int l, int r, int &rt) {
16    rt = new_node(lst);
17    data[rt] += val;
18    if(l == r) return ;
19    int m = (l + r) >> 1;
20    if(pos <= m) update(pos, val, ls[lst], l, m, ls[rt]);
21    else update(pos, val, rs[lst], m + 1, r, rs[rt]);
22}
23int query(int L, int R, int l, int r, int rt) {
24    if(L <= l && r <= R) return data[rt];
25    int m = (l + r) >> 1, ret = 0;
26    if(L <= m) ret += query(L, R, l, m, ls[rt]);
27    if(R > m) ret += query(L, R, m + 1, r, rs[rt]);
28    return ret;
29}
30int ask_kth(int k, int l, int r, int rt) {
31    if(l == r) return l;
32    int m = (l + r) >> 1;
33    return data[ls[rt]] >= k ? ask_kth(k, l, m, ls[rt]) : ask_kth(k - data[ls[rt]], m + 1, r, rs[rt]);
34}

 1int a[N], pre[N];
 2int main() {
 3    int T;
 4    int cas = 0;
 5    cin >> T;
 6    while (T--){
 7        int n, m;
 8        scanf("%d %d", &n, &m);
 9        memset(pre,-1,sizeof(pre));
10        //memset(pre, -1, sizeof(pre[0]) * (n + 5));
11        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
12        tot = 0;
13        build(1, n, root[n + 1]);
14        for(int i = n; i >= 1; i --) {
15            if(~ pre[a[i]]) update(pre[a[i]], -1, root[i + 1], 1, n, root[i]);
16            update(i, 1, root[~pre[a[i]] ? i : i + 1], 1, n, root[i]);
17            pre[a[i]] = i;
18        }
19        printf("Case #%d:", ++cas);
20        int ans = 0;
21        while(m --) {
22            int l, r;
23            scanf("%d %d", &l, &r);
24            l = (l + ans) % n + 1;
25            r = (r + ans) % n + 1;
26            if(l > r) swap(l, r);
27            int cnt = query(l, r, 1, n, root[l]);
28            ans = ask_kth((cnt + 1) >> 1, 1, n, root[l]);
29            printf(" %d", ans);
30        }
31        puts("");
32    }