2016 CCPC 长春 I 题 | hdu 5919 Sequence II (可持久化线段树求区间第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 }
}