Chia các giá trị thành $V = \sqrt 10^5$ các nhóm giá trị liên tiếp $\[1, V\], \[V+1,2 \times V\],...$ và chia mảng thành các block $S = \sqrt n$ phần tử liên tiếp.
Gọi $f(b,i)$ là số lượng giá trị $i$ trong $b$ block đầu tiên.
Gọi $g(i,b)$ là số lượng giá trị nằm trong nhóm giá trị thứ $b$ ở $i$ block đầu tiên của mảng.
Dễ thấy ta có thể chuẩn bị hai mảng này trong độ phức tạp $\mathcal{O}(n \sqrt n)$.
Với truy vấn loại $2$, nếu có được hai mảng này, để trả lời được truy vấn, ta xét lần lượt từng nhóm giá trị từ nhỏ đến lớn xem kết quả cần tìm nằm trong nhóm nào. Độ phức tạp của thao tác này là $\mathcal{O}(V)$.
Khi xác định được khoảng giá trị, ta lại xét từng giá trị trong khoảng này. Độ phức tạp thao tác là $\mathcal{O}(V)$. Vậy là trả lời được truy vấn trong độ phức tạp $\mathcal{O}(V)$.
Với truy vấn loại $1$ sẽ phức tạp hơn. Khi cập nhật, ta thường chia làm hai trường hợp, cập nhật nguyên một block và cập nhật phần thừa của hai bên. Việc cập nhật nguyên một block với cả hai mảng $f$ và $g$ tương đối dễ.
Mỗi block ta chỉ cần chuyển số lượng của $x$ sang cho $y$.
Còn với phần cập nhật đoạn thừa ra ở hai bên, ta cần biết ở mỗi vị trí $i$, $A_i$ ở thời điểm đó là giá trị nào. Việc này thực tế là tương đối khó.
Giải pháp là, khi chuyển giá trị $x$ thành $y$, ta sẽ tính lại block chứa phần thừa ở hai bên. Trong các block nguyên vẹn:
- Nếu không có giá trị $x$ tồn tại thì bỏ qua.
- Nếu không có giá trị $y$ tồn tại, ta đổi vai trò của $x$ và $y$. Do có tối đa $S$ phần tử liên tiếp trong mỗi block, có thể tạo $S$ vai trò tương ứng với các giá trị khác nhau.
- Nếu tồn tại cả $x$ và $y$, ta cập nhật lại cả block này.
Thoạt nhìn độ phức tạp của mỗi truy vấn cập nhật là $\mathcal{O}(n)$, nhưng thực tế trong mỗi block chỉ có $V$ giá trị khác nhau, nên việc cập nhật lại cả block chỉ bị thực hiện $V$ lần tối đa cho mỗi block. Ngoài ra với mỗi truy vấn cập nhật chỉ có thể tăng thêm một giá trị khác nhau cho tối đa hai block, nên tổng số lần thực hiện thao tác cập nhật cả đoạn tối đa là $2 \times q + V \times V$. Vậy độ phức tạp của tất cả các truy vấn cập nhật là $\mathcal{O}((n + q) \times V)$.
Độ phức tạp thời gian của cả bài toán là $\mathcal{O}((n + q) \times V)$. Trên thực tế, có thể chỉnh lại giá trị của các hằng số $S$ và $V$ để đạt được thời gian thực thi nhanh hơn.
Code mẫu:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000, maxvs = 316;
const int maxs = 360, maxc = 278;
int cnt;
int a[maxn + 5];
int lp[maxc + 5], rp[maxvs + 5];
int bl[maxn + 5];
int vlp[maxvs + 5];
int vbl[maxn + 5];
int sum[maxc + 5][maxn + 5];
int blsum[maxc + 5][maxvs + 5];
int rep[maxc + 5][maxn + 5];
int col[maxc + 5][maxs + 5];
int id[maxn + 5];
int ccnt[maxc + 5];
void buildUnion(int bid) {
for (int i = 1; i <= ccnt[bid]; i++)
rep[bid][col[bid][i]] = 0;
ccnt[bid] = 0;
for (int i = lp[bid]; i <= rp[bid]; i++) {
if (rep[bid][a[i]] == 0) {
rep[bid][a[i]] = ++ccnt[bid];
col[bid][ccnt[bid]] = a[i];
}
id[i] = rep[bid][a[i]];
}
}
void reset(int bid) {
for (int i = lp[bid]; i <= rp[bid]; i++)
a[i] = col[bid][id[i]];
}
void build(int n) {
int siz = min(n, int(sqrt(1.3 * n)));
cnt = ceil(1. * n / siz);
for (int i = 1; i <= n; i++)
bl[i] = (i - 1) / siz + 1;
for (int i = 1; i <= cnt; i++) {
lp[i] = (i - 1) * siz + 1;
rp[i] = min(n, i * siz);
}
for (int i = 1; i <= maxn; i++)
vbl[i] = (i - 1) / maxvs + 1;
for (int i = 1; i <= maxvs + 1; i++)
vlp[i] = (i - 1) * maxvs + 1;
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= maxn; j++)
sum[i][j] = sum[i - 1][j];
for (int j = 1; j <= maxvs + 1; j++)
blsum[i][j] = blsum[i - 1][j];
for (int j = lp[i]; j <= rp[i]; j++) {
sum[i][a[j]]++;
blsum[i][vbl[a[j]]]++;
}
buildUnion(i);
}
}
int tmp[maxn + 5], bltmp[maxvs + 5];
void add(int l, int r, int delta) {
for (int i = l; i <= r; i++) {
tmp[a[i]] += delta;
bltmp[vbl[a[i]]] += delta;
}
}
int query(int l, int r, int k) {
int lb = bl[l], rb = bl[r];
int res;
if (lb == rb) {
reset(lb);
copy(a + l, a + r + 1, tmp + l);
nth_element(tmp + l, tmp + l + k - 1, tmp + r + 1);
res = tmp[l + k - 1];
fill(tmp + l, tmp + r + 1, 0);
} else {
reset(lb);
reset(rb);
add(l, rp[lb], 1);
add(lp[rb], r, 1);
int i = 1, delta;
for (; k - (delta = bltmp[i] + blsum[rb - 1][i] - blsum[lb][i]) > 0;
i++)
k -= delta;
int j = vlp[i];
for (; k - (delta = tmp[j] + sum[rb - 1][j] - sum[lb][j]) > 0; j++)
k -= delta;
res = j;
add(l, rp[lb], -1);
add(lp[rb], r, -1);
}
return res;
}
void change(int l, int r, int x, int y, int bid) {
int chcnt = 0;
for (int i = l; i <= r; i++) {
if (a[i] == x) {
a[i] = y;
chcnt++;
}
}
sum[bid][x] -= chcnt;
sum[bid][y] += chcnt;
blsum[bid][vbl[x]] -= chcnt;
blsum[bid][vbl[y]] += chcnt;
}
void changeBlock(int l, int r, int x, int y, int bid) {
reset(bid);
change(l, r, x, y, bid);
buildUnion(bid);
}
void modify(int l, int r, int x, int y) {
int lb = bl[l], rb = bl[r];
if (x == y || sum[rb][x] - sum[lb - 1][x] == 0)
return;
for (int i = cnt; i >= lb; i--) {
sum[i][x] -= sum[i - 1][x];
sum[i][y] -= sum[i - 1][y];
blsum[i][vbl[x]] -= blsum[i - 1][vbl[x]];
blsum[i][vbl[y]] -= blsum[i - 1][vbl[y]];
}
if (lb == rb)
changeBlock(l, r, x, y, lb);
else {
changeBlock(l, rp[lb], x, y, lb);
changeBlock(lp[rb], r, x, y, rb);
for (int i = lb + 1; i < rb; i++) {
if (sum[i][x] == 0)
continue;
if (sum[i][y] == 0) {
col[i][rep[i][x]] = y;
swap(rep[i][y], rep[i][x]);
blsum[i][vbl[y]] += sum[i][x];
blsum[i][vbl[x]] -= sum[i][x];
sum[i][y] = sum[i][x];
sum[i][x] = 0;
} else
changeBlock(lp[i], rp[i], x, y, i);
}
}
for (int i = lb; i <= cnt; i++) {
sum[i][x] += sum[i - 1][x];
sum[i][y] += sum[i - 1][y];
blsum[i][vbl[x]] += blsum[i - 1][vbl[x]];
blsum[i][vbl[y]] += blsum[i - 1][vbl[y]];
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(n);
for (int i = 1; i <= m; i++) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
int x, y;
scanf("%d%d", &x, &y);
modify(l, r, x, y);
} else {
int k;
scanf("%d", &k);
printf("%d\n", query(l, r, k));
}
}
}
```
letterc67
Created at
13 likes