Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：#
给定一个序列 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;
14
15#define MP make_pair
16#define PB push_back
17#define SZ(x) (int((x).size()))
18#define ALL(x) (x).begin(), (x).end()
19#define X first
20#define Y second
21
22typedef long long LL;
23typedef long double LD;
24const int INF = 0x3f3f3f3f;
25
26typedef pair<LL, LL> pii;
27
28const int N = 2e5 + 10;
29const int M = 30 * 2 * N;
30
31int ls[M], rs[M], root[N], tot, data[M];
32inline int new_node(int lst = 0) {
33 ls[++ tot] = ls[lst];
34 rs[tot] = rs[lst];
35 data[tot] = data[lst];
36 return tot;
37}
38void build(int l, int r, int &rt) {
39 rt = new_node();
40 if(l == r) return ;
41 int m = (l + r) >> 1;
42 build(l, m, ls[rt]);
43 build(m + 1, r, rs[rt]);
44}
45void update(int pos, int val, int lst, int l, int r, int &rt) {
46 rt = new_node(lst);
47 data[rt] += val;
48 if(l == r) return ;
49 int m = (l + r) >> 1;
50 if(pos <= m) update(pos, val, ls[lst], l, m, ls[rt]);
51 else update(pos, val, rs[lst], m + 1, r, rs[rt]);
52}
53int query(int L, int R, int l, int r, int rt) {
54 if(L <= l && r <= R) return data[rt];
55 int m = (l + r) >> 1, ret = 0;
56 if(L <= m) ret += query(L, R, l, m, ls[rt]);
57 if(R > m) ret += query(L, R, m + 1, r, rs[rt]);
58 return ret;
59}
60int ask_kth(int k, int l, int r, int rt) {
61 if(l == r) return l;
62 int m = (l + r) >> 1;
63 return data[ls[rt]] >= k ? ask_kth(k, l, m, ls[rt]) : ask_kth(k - data[ls[rt]], m + 1, r, rs[rt]);
64}
65
66
67int a[N], pre[N];
68int main() {
69 int T;
70 int cas = 0;
71 cin >> T;
72 while (T--){
73 int n, m;
74 scanf("%d %d", &n, &m);
75 memset(pre,-1,sizeof(pre));
76 //memset(pre, -1, sizeof(pre[0]) * (n + 5));
77 for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
78 tot = 0;
79 build(1, n, root[n + 1]);
80 for(int i = n; i >= 1; i --) {
81 if(~ pre[a[i]]) update(pre[a[i]], -1, root[i + 1], 1, n, root[i]);
82 update(i, 1, root[~pre[a[i]] ? i : i + 1], 1, n, root[i]);
83 pre[a[i]] = i;
84 }
85 printf("Case #%d:", ++cas);
86 int ans = 0;
87 while(m --) {
88 int l, r;
89 scanf("%d %d", &l, &r);
90 l = (l + ans) % n + 1;
91 r = (r + ans) % n + 1;
92 if(l > r) swap(l, r);
93 int cnt = query(l, r, 1, n, root[l]);
94 ans = ask_kth((cnt + 1) >> 1, 1, n, root[l]);
95 printf(" %d", ans);
96 }
97 puts("");
98 }
99
100}