脚本宝典收集整理的这篇文章主要介绍了[Ynoi2018] 未来日记 Solution，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
先考虑分块做区间第 (k) 大。
令 (cnt_{i,j}) 表示第 (i) 块中 (j) 的出现次数， (sum1_{i,j}) 表示前 (i) 块中 (j) 的出现次数。
然后我们发现，只用这些信息会多一个 (LOG)。
注意到值域是 (1 times 10^5) ，考虑权值分块。
再记 (sum2_{i,j}) 表示序列分块的前 (i) 块中，权值分块前 (j) 块中的树的出现次数。
询问时散块维护 (s1,s2) 两个数组，(s1_i) 累加权值分块前 (i) 块中的数，(s2_i) 累加 (i) 的出现次数。
利用 (sum2) 以及 (s1) 的信息得到第 (k) 大落在哪个权值块中 ，再利用 (sum1) 与 (s2) 得到答案。
现在来考虑修改，不妨想象一下，(x to y)，(y to z) 的结果是原先的 (x,y to z) 。可以注意到这是一个树形结构，自然可以用并查集维护。
具体的，给序列块 (i) 中每个值 (x) 发一个代表，记作 (rt_{i,x}) ，对于一组修改 ((i) , (x) , (y)) ，若 (rt_{i,y}) 不存在，令 (rt_{i,y} to rt_{i,x}) ，(a_{rt_{i,x}} to y) ，反之令 (fa_{rt_{i,x}} to rt_{i,y})。
散块并不适合套用这个方法，众所周知，边角暴力，直接重构 (x)，(y) 的并查集子树。注意在所有修改后都需更新 (cnt) ， (sum1) ， (sum2)。
取序列块长 (600) ，值域块长 (320)，以下是代码：
#include <cstdio>
#include <iostream>
#include <algorIThm>
inline int read() {
register char c = getchar();
register int x = 0, f = 1;
while(c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
return x * f;
}
const int N = 1e5 + 5;
const int M = 170;
const int S = 320;
int n, m, bl, a[N];
int top = 0, sta[N];
int L[M], R[M], bel[N], s1[S], s2[N];
int cnt[M][N], sumc[M][N], sums[M][S];
int fa[N], rt[M][N];
int find(int x) { return (fa[x] == x ? x : fa[x] = find(fa[x])); }
void Build(int b) {
for (register int i = L[b]; i <= R[b]; i++) {
if (!rt[b][a[i]])
rt[b][a[i]] = i;
else
fa[i] = rt[b][a[i]];
cnt[b][a[i]]++;
}
}
void ReBuild(int b, int l, int r, int x, int y) {
register int tmp = 0;
top = 0;
rt[b][x] = rt[b][y] = 0;
for (register int i = L[b]; i <= R[b]; i++) {
a[i] = a[find(i)];
if (a[i] == x || a[i] == y)
sta[++top] = i;
}
for (register int i = l; i <= r; i++)
if (a[i] == x)
a[i] = y, tmp++;
cnt[b][x] -= tmp, cnt[b][y] += tmp;
for (register int i = 1; i <= top; i++)
fa[sta[i]] = sta[i];
for (register int i = 1; i <= top; i++) {
if (!rt[b][a[sta[i]]])
rt[b][a[sta[i]]] = sta[i];
else
fa[sta[i]] = rt[b][a[sta[i]]];
}
for (register int i = b; i <= bl; i++) {
sumc[i][x] -= tmp, sumc[i][y] += tmp;
if (bel[x] != bel[y])
sums[i][bel[x]] -= tmp, sums[i][bel[y]] += tmp;
}
}
int main() {
scanf("%d%d", &n, &;m);
for (register int i = 1; i <= n; i++) {
// scanf("%d", &a[i]);
a[i] = read();
fa[i] = i;
}
int Siz = 600, Sizv = 317, Mv = 1e5;
bl = (n - 1) / Siz + 1;
for (register int i = 1; i <= Mv; i++)
bel[i] = (i - 1) / Sizv + 1;
for (register int i = 1; i <= bl; i++) {
L[i] = (i - 1) * Siz +1;
R[i] = std :: min(i * Siz, n);
Build(i);
for (register int j = 1; j <= Sizv; j++)
sums[i][j] = sums[i - 1][j];
for (register int j = 1; j <= Mv; j++)
sumc[i][j] = sumc[i - 1][j] + cnt[i][j];
for (register int j = L[i]; j <= R[i]; j++)
sums[i][bel[a[j]]]++;
}
while (m--) {
register int opt, x, y, l, r, k;
// scanf("%d", &opt);
opt = read();
if (opt == 1) {
// scanf("%d%d%d%d", &l, &r, &x, &y);
l = read(), r = read(), x = read(), y = read();
if (x == y)
continue;
register int lb = (l - 1) / Siz + 1;
register int rb = (r - 1) / Siz + 1;
if (lb == rb)
ReBuild(lb, l, r, x, y);
else {
ReBuild(lb, l, R[lb], x, y);
ReBuild(rb, L[rb], r, x, y);
register int tmp = 0, tmps = 0;
for (register int i = lb + 1; i <= rb - 1; 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];
// tmps += tmp = cnt[i][x];
rt[i][x] = 0;
tmp = cnt[i][x];
tmps += tmp;
cnt[i][y] += tmp, cnt[i][x] = 0;
}
sumc[i][x] -= tmps, sumc[i][y] += tmps;
if (bel[x] != bel[y])
sums[i][bel[x]] -= tmps, sums[i][bel[y]] += tmps;
}
for (register int i = rb; i <= bl; i++) {
sumc[i][x] -= tmps, sumc[i][y] += tmps;
if (bel[x] != bel[y])
sums[i][bel[x]] -= tmps, sums[i][bel[y]] += tmps;
}
}
}
else {
// scanf("%d%d%d", &l , &r, &k);
l = read(), r = read(), k = read();
register int lb = (l - 1) / Siz + 1;
register int rb = (r - 1) / Siz + 1;
if (lb == rb) {
for (register int i = l; i <= r; i++) {
a[i] = a[find(i)];
s1[bel[a[i]]]++;
s2[a[i]]++;
}
register int vl, vr, sum = 0;
for (register int i = 1; i <= Sizv; i++) {
sum += s1[i];
if (sum >= k) {
sum -= s1[i];
vl = (i - 1) * Sizv + 1, vr = i * Sizv;
break;
}
}
for (register int i = vl; i <= vr; i++) {
sum += s2[i];
if (sum >= k) {
PRintf("%dn", i);
break;
}
}
for (register int i = l; i <= r; i++)
s2[a[i]]--, s1[bel[a[i]]]--;
}
else {
for (register int i = l; i <= R[lb]; i++) {
a[i] = a[find(i)];
s1[bel[a[i]]]++;
s2[a[i]]++;
}
for(register int i = L[rb]; i <= r; i++) {
a[i] = a[find(i)];
s1[bel[a[i]]]++;
s2[a[i]]++;
}
register int vl, vr, sum = 0;
for (register int i = 1; i <= Sizv; i++) {
sum += s1[i] + sums[rb - 1][i] - sums[lb][i];
if (sum >= k) {
sum -= s1[i] + sums[rb - 1][i] - sums[lb][i];
vl = (i - 1) * Sizv + 1, vr = i * Sizv;
break;
}
}
for (register int i = vl; i <= vr; i++) {
sum += s2[i] + sumc[rb - 1][i] - sumc[lb][i];
if (sum >= k) {
printf("%dn", i);
break;
}
}
for (register int i = l; i <= R[lb]; i++) {
s1[bel[a[i]]]--;
s2[a[i]]--;
}
for (register int i = L[rb]; i <= r; i++) {
s1[bel[a[i]]]--;
s2[a[i]]--;
}
}
}
}
return 0;
}
以上是脚本宝典为你收集整理的[Ynoi2018] 未来日记 Solution全部内容，希望文章能够帮你解决[Ynoi2018] 未来日记 Solution所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。