yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P4119 [Ynoi2018] 未来日记

发表于 分类于

P4119 [Ynoi2018] 未来日记

题面

题目链接

解法

写吐了，网上题解一大堆，实在不想写题解了，就写一下我是怎么卡常的吧。

这道题从 $2$ 月份卡到了 $4$ 月份，并查集和均摊复杂度的方法都写了，最后并查集方法用了各种神奇优化才过掉了。

首先是加 fread，调块长，值域分块的块长就开成 $316$ 不动，序列分块的块长经过三分测出，对于我的程序大约在 $390$ 最为合适。

其次是，如果询问的 $r-l+1 \le \text{块长}$，那么直接将 $a$ 数组复制到 $tmp$ 数组中做 nth_element。

还有一些小的玄学优化，比如说更新散块不要找到一个 $x$ 就更新 $cnt[x]$，而是记录下来块内有多少个 $x$，最后一把头更新 $cnt[x]$，尽量减少不连续内存访问。这样就能卡到 $64 \sim 73$ 分。

如何卡到 $100$ 分呢？就是在处理更新散块的时候不要把整个块都重构，而是只重构 $x$ 和 $y$ 的下标。即先扫描出块内值为 $x$ 或 $y$ 的点存入临时数组，然后重构临时数组的并查集，就卡到了 $100$ 分了。

AC代码

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
/**
 * @file:           P4119.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4119
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
namespace fastio {
const int MAXBUF = 1 << 22;
char buf[MAXBUF], *p1 = buf, *p2 = buf;
char pbuf[MAXBUF], *pp = pbuf;
inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), *p1++; }
inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
};  // namespace fastio
using namespace fastio;
template <class _Tp>
inline void read(_Tp& x) {
    char ch = getc();
    for (; !isdigit(ch); ch = getc()) ;
    for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) write(x / 10);
    putc((x % 10) ^ 48);
}
using ll = long long;
const int MAXN = 1e5 + 10;
const int MAXB = 520;
const int INF = 0x3f3f3f3f;
int n, m, q, a[MAXN], tmp[MAXN], sta[MAXN];
int fa[MAXN], val[MAXN], repr[MAXB][MAXN];
int iblk, bn, ipos[MAXN], ibl[MAXB], ibr[MAXB];
int vblk, bm, vpos[MAXN], vbl[MAXB], vbr[MAXB];
int vcnt[MAXB][MAXN], bcnt[MAXB][MAXB], tvcnt[MAXN], tbcnt[MAXB];
inline int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
signed main() {
    read(n), read(q), m = 1e5;
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    iblk = 390, vblk = 316;
    for (int l = 1; l <= n; l += iblk) {
        int r = min(n, l + iblk - 1);
        ++bn, ibl[bn] = l, ibr[bn] = r;
        for (int i = l; i <= r; ++i)
            ipos[i] = bn;
    }
    for (int l = 1; l <= m; l += vblk) {
        int r = min(m, l + vblk - 1);
        ++bm, vbl[bm] = l, vbr[bm] = r;
        for (int i = l; i <= r; ++i)
            vpos[i] = bm;
    }
    for (int i = 1; i <= n; ++i)
        ++vcnt[ipos[i]][a[i]], ++bcnt[ipos[i]][vpos[a[i]]];
    for (int i = 1; i <= bn; ++i) {
        for (int j = 1; j <= m; ++j)
            vcnt[i][j] += vcnt[i - 1][j];
        for (int j = 1; j <= bm; ++j)
            bcnt[i][j] += bcnt[i - 1][j];
    }
    for (int i = 1; i <= n; ++i)
        fa[i] = i, val[i] = a[i];
    for (int i = 1; i <= bn; ++i) {
        for (int j = ibl[i]; j <= ibr[i]; ++j)
            (repr[i][a[j]]) ? (fa[j] = repr[i][a[j]])
                            : (repr[i][a[j]] = j, val[j] = a[j]);
    }
    while (q--) {
        int op, l, r, x, y;
        read(op), read(l), read(r), read(x);
        if (op == 1) {
            read(y);
            if (x == y) continue;
            int bl = ipos[l], br = ipos[r], lcnt = 0, rcnt = 0;
            auto rebuild = [&](int b) {
                int cnt = 0, ret = 0;
                for (int i = ibl[b]; i <= ibr[b]; ++i) {
                    a[i] = val[getfa(i)];
                    if (a[i] == x || a[i] == y) sta[++cnt] = i;
                }
                repr[b][x] = repr[b][y] = 0;
                while (cnt) {
                    int p = sta[cnt--];
                    if (l <= p && p <= r && a[p] == x) a[p] = y, ++ret;
                    if (repr[b][a[p]])
                        fa[p] = repr[b][a[p]];
                    else
                        repr[b][a[p]] = fa[p] = p, val[p] = a[p];
                }
                vcnt[b][x] -= ret, bcnt[b][vpos[x]] -= ret;
                vcnt[b][y] += ret, bcnt[b][vpos[y]] += ret;
                return ret;
            };
            if (bl == br) {
                lcnt = rebuild(bl);
            } else {
                lcnt = rebuild(bl), rcnt = rebuild(br);
            }
            for (int i = bl + 1; i < br; ++i) {
                lcnt = vcnt[i][x] - vcnt[i - 1][x];
                vcnt[i][x] -= lcnt, bcnt[i][vpos[x]] -= lcnt;
                vcnt[i][y] += lcnt, bcnt[i][vpos[y]] += lcnt;
                if (repr[i][x] && repr[i][y])
                    fa[repr[i][x]] = repr[i][y], repr[i][x] = 0;
                else if (repr[i][x])
                    val[repr[i][y] = repr[i][x]] = y, repr[i][x] = 0;
            }
            if (bl != br) {
                vcnt[br][x] -= lcnt, bcnt[br][vpos[x]] -= lcnt;
                vcnt[br][y] += lcnt, bcnt[br][vpos[y]] += lcnt;
                lcnt += rcnt;
            }
            for (int i = br + 1; i <= bn; ++i) {
                vcnt[i][x] -= lcnt, bcnt[i][vpos[x]] -= lcnt;
                vcnt[i][y] += lcnt, bcnt[i][vpos[y]] += lcnt;
            }
        } else {
            if (r - l + 1 <= iblk) {
                for (int i = l; i <= r; ++i)
                    tmp[i] = val[getfa(i)];
                nth_element(tmp + l, tmp + l + x - 1, tmp + r + 1);
                write(tmp[l + x - 1]), putc('\n');
            } else {
                int bl = ipos[l], br = ipos[r], ans = 1;
                for (int i = l; i <= ibr[bl]; ++i)
                    ++tvcnt[val[getfa(i)]], ++tbcnt[vpos[val[getfa(i)]]];
                for (int i = ibl[br]; i <= r; ++i)
                    ++tvcnt[val[getfa(i)]], ++tbcnt[vpos[val[getfa(i)]]];
                int pl = 1, pr = bm;
                for (int i = pl; i <= pr; ++i) {
                    int sum = tbcnt[i] + ((bl == br) ? 0 : (bcnt[br - 1][i] - bcnt[bl][i]));
                    if (x <= sum) break;
                    x -= sum, ans += vblk;
                }
                int vl = ans, vr = vbr[vpos[ans]];
                for (int i = vl; i <= vr; ++i) {
                    int sum = tvcnt[i] + ((bl == br) ? 0 : (vcnt[br - 1][i] - vcnt[bl][i]));
                    if (x <= sum) break;
                    x -= sum, ++ans;
                }
                for (int i = l; i <= ibr[bl]; ++i)
                    --tvcnt[val[getfa(i)]], --tbcnt[vpos[val[getfa(i)]]];
                for (int i = ibl[br]; i <= r; ++i)
                    --tvcnt[val[getfa(i)]], --tbcnt[vpos[val[getfa(i)]]];
                write(ans), putc('\n');
            }
        }
    }
    return print_final(), 0;
}