洛谷4119 [Ynoi2018]未来日记

题意

长度为 $n$ 的序列 $a$,有 $m$ 次操作

  1. 把区间 $[l,r]$ 内所有 $x$ 变成 $y$
  2. 查询区间 $[l,r]$ 内 $k$ 小值

$1 \leq n,m,a_i \leq 100000$

分析

动态区间第 $k$ 小。

第一道分块题,看着别人的题解抄抄改改总算搞出来了。

首先考虑静态的怎么做。

首先对序列分块,再对值域分块。

  • $sumVal[i][j]$ 表示 $i$ 块中,值为 $j$ 的数量。
  • $sumBlock[i][j]$ 表示 $i$ 块中,值域在第 $j$ 块的数量。
  • $cnt[i][j]$ 表示 $i$ 块中,值为 $j$ 的数量。

考虑询问 $(l,r,k)$

设 $bl$ 表示 $l$ 所在块,$br$ 表示 $r$ 所在块。如果 $bl=br$,那么直接块内暴力。不然的话这两块是要单独暴力处理的。

我们可以用两个辅助数组来记录 $bl$ 和 $br$ 这两个块的信息。

  • $c[i]$ 表示 $[l,r]$ 区间内,值为 $j$ 的数量。
  • $s[i]$ 表示 $[l,r]$ 区间内,值域在第 $j$ 块的数量。

然后我们从小到大枚举值域块,用 $sum$ 来记录数量。

$sum += s[i] + sumBlock[br-1][i] - sumBlock[bl][i]$

如果 $sum \geq k$,则说明答案当前块内,然后我们在当前块内暴力就可以了。


现在我们考虑动态的情况。

首先考虑对于 $bl$ 和 $br$ 所在的块:这两个块是要暴力修改的。我们应该把这个块内的 $x$ 都变成 $y$ 后再去修改后续的 $sumVal$ 和 $sumBlock$。

然后就是那些中间的块:中间的块肯定不能再暴力了,必须通过打标记的方式来降低复杂度。我们所作的操作是将区间中所有的 $x$ 都变成 $y$。考虑并查集维护每个块中同一个值的所有位置,我们可以把块内的该值出现的第一个位置当作根节点。这样我们在打标记的时候,实际上做的是:找到 $x$ 出现的第一个位置 $pos$,然后使 $a[pos] = y$(合并两个并查集)。

  • $rt[i][j]$ 表示第 $i$ 块中,值为 $j$ 的第一次出现的位置。

暴力修改块内元素的时候不要忘了更新 $rt$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, sqrt_maxn = 350;

int n, m, K, sz, vsz, a[maxn];
int L[sqrt_maxn], R[sqrt_maxn];
int fa[maxn];
int vblock[maxn]; // 每个值所属的值域块
int sumBlock[sqrt_maxn][sqrt_maxn];
int sumVal[sqrt_maxn][maxn];
int rt[sqrt_maxn][maxn]; // 第i块中,值为j的第一次出现的位置
int cnt[sqrt_maxn][maxn]; // 第i块中,值为j的个数
int c[maxn], s[sqrt_maxn];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int stk[maxn];
void update(int id, int l, int r, int x, int y) { // 暴力更新块内
int tmp = 0, top = 0;
rt[id][x] = rt[id][y] = 0;
for (int i = L[id]; i <= R[id]; i++) {
a[i] = a[find(i)];
if (a[i] == x || a[i] == y) stk[++top] = i;
}
// 不能合并到上面,因为 find() 会改变
for (int i = l; i <= r; i++)
if (a[i] == x) a[i] = y, ++tmp;
for (int i = 1, t, w; i <= top; i++) {
fa[stk[i]] = stk[i];
t = stk[i], w = a[t];
if (!rt[id][w])
rt[id][w] = t;
else
fa[t] = rt[id][w];
}

cnt[id][x] -= tmp, cnt[id][y] += tmp;
for (int i = id; i <= K; i++) {
sumVal[i][x] -= tmp;
sumVal[i][y] += tmp;
if (vblock[x] != vblock[y])
sumBlock[i][vblock[x]] -= tmp, sumBlock[i][vblock[y]] += tmp;
}
}

inline void count(int l, int r, int w) {
for (int i = l; i <= r; i++) {
a[i] = a[find(i)];
c[a[i]] += w;
s[vblock[a[i]]] += w;
}
}
int main() {
int T;
scanf("%d", &T);
sz = 600;
vsz = 400;
for (int i = 1; i < maxn; i++) vblock[i] = (i + vsz - 1) / vsz;
while (T--) {
scanf("%d%d", &n, &m);
memset(cnt, 0, sizeof(cnt));
memset(rt, 0, sizeof(rt));

K = (n + sz - 1) / sz;
for (int i = 1; i <= n; i++) scanf("%d", a + i), fa[i] = i;
for (int i = 1; i <= K; i++) {
L[i] = (i - 1) * sz + 1, R[i] = min(n, i * sz);
for (int j = 1; j <= vsz; j++) sumBlock[i][j] = sumBlock[i - 1][j];
for (int j = 1; j < maxn; j++) sumVal[i][j] = sumVal[i - 1][j];
for (int j = L[i]; j <= R[i]; j++) {
if (!rt[i][a[j]])
rt[i][a[j]] = j;
else
fa[j] = rt[i][a[j]];
++sumBlock[i][vblock[a[j]]];
++sumVal[i][a[j]];
++cnt[i][a[j]];
}
}
for (int _ = 0, op, l, r, x, y; _ < m; _++) {
scanf("%d%d%d", &op, &l, &r);
int lb = (l + sz - 1) / sz, rb = (r + sz - 1) / sz;
if (op == 1) {
scanf("%d%d", &x, &y);
if (x == y) continue;
if (lb == rb)
update(lb, l, r, x, y);
else {
update(lb, l, R[lb], x, y);
update(rb, L[rb], r, x, y);
int pre = 0;
for (int i = lb + 1; i < rb; i++) {
if (rt[i][x]) {
if (!rt[i][y])
rt[i][y] = rt[i][x], a[rt[i][x]] = y;
else
fa[rt[i][x]] = rt[i][y];
rt[i][x] = 0;
pre += cnt[i][x];
cnt[i][y] += cnt[i][x];
cnt[i][x] = 0;
}
sumVal[i][x] -= pre, sumVal[i][y] += pre;
if (vblock[x] != vblock[y])
sumBlock[i][vblock[x]] -= pre, sumBlock[i][vblock[y]] += pre;
}
for (int i = rb; i <= K; i++) {
sumVal[i][x] -= pre, sumVal[i][y] += pre;
if (vblock[x] != vblock[y])
sumBlock[i][vblock[x]] -= pre, sumBlock[i][vblock[y]] += pre;
}
}
} else {
scanf("%d", &x);
int sum = 0, ll, rr;
if (lb == rb) {
count(l, r, 1);
for (int i = 1; i <= vsz; i++) {
sum += s[i];
if (sum >= x) {
sum -= s[i];
ll = (i - 1) * vsz + 1, rr = i * vsz;
break;
}
}
for (int i = ll; i <= rr; i++) {
sum += c[i];
if (sum >= x) {
printf("%d\n", i);
break;
}
}
count(l, r, -1);
continue;
}
count(l, R[lb], 1);
count(L[rb], r, 1);
for (int i = 1; i <= vsz; i++) {
sum += s[i] + sumBlock[rb - 1][i] - sumBlock[lb][i];
if (sum >= x) {
sum -= s[i] + sumBlock[rb - 1][i] - sumBlock[lb][i];
ll = (i - 1) * vsz + 1;
rr = i * vsz;
break;
}
}
for (int i = ll; i <= rr; i++) {
sum += c[i] + sumVal[rb - 1][i] - sumVal[lb][i];
if (sum >= x) {
printf("%d\n", i);
break;
}
}
count(l, R[lb], -1);
count(L[rb], r, -1);
}
}
}
}