洛谷 4119.「Ynoi 2018」未来日记

「望月悲叹的最初分块」。

区间第 \(k\) 小考虑值域分块。
那么问题变成了维护每个位置的值,每一块内属于每一权值块的值的个数,每一块内每一权值的个数,并且后两个还要维护前缀和。

然后考虑修改操作。
后两种信息的维护是平凡的,包括前缀和也可以暴力去做。
但是如何维护每个位置的值?

考虑并查集。
冷静分析一下这个并查集其实是 \(O(1)\) 的。
只不过有一定常数影响。
说实话并不难写……但是我咋写挂这么多次(

另外,不难发现这个东西改一改就可以做隔壁第二分块了(

代码:

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}

const int N = 1e5;
const int BLK = 633;
const int CNT = N / BLK + 1;
const int WBLK = 233;
const int WCNT = N / WBLK + 1;
int n,m,block,wblock;
int a[N + 5],pos[N + 5],wpos[N + 5],fa[N + 5];
int cnt[CNT + 5][WCNT + 5],wcnt[CNT + 5][N + 5];
int sum[CNT + 5][WCNT + 5],wsum[CNT + 5][N + 5];
int tcnt[WCNT + 5],tmp[N + 5];
int fir[CNT + 5][N + 5];
inline int get(int x)
{
return !fa[x] ? x : (fa[x] = get(fa[x]));
}
void update(int l,int r,int x,int y)
{
if(x == y)
return ;
for(register int p = pos[l] + 1;p < pos[r];++p)
if(fir[p][x])
{
a[fir[p][x]] = y;
if(wcnt[p][x] > wcnt[p][y] || !fir[p][y])
fir[p][y] && (fa[fir[p][y]] = fir[p][x]),
fir[p][y] = fir[p][x];
else
fa[fir[p][x]] = fir[p][y];
cnt[p][wpos[x]] -= wcnt[p][x],cnt[p][wpos[y]] += wcnt[p][x],
wcnt[p][y] += wcnt[p][x],wcnt[p][x] = 0,
fir[p][x] = 0;
}
for(register int i = (pos[l] - 1) * block + 1;i <= min(pos[l] * block,n);++i)
a[i] = a[get(i)];
for(register int i = l;i <= min(pos[l] * block,r);++i)
a[i] == x && (a[i] = y,--cnt[pos[l]][wpos[x]],++cnt[pos[l]][wpos[y]],--wcnt[pos[l]][x],++wcnt[pos[l]][y]);
fir[pos[l]][x] = fir[pos[l]][y] = 0;
for(register int i = (pos[l] - 1) * block + 1;i <= min(pos[l] * block,n);++i)
if(a[i] == x || a[i] == y)
!fir[pos[l]][a[i]] ? (fa[i] = 0,fir[pos[l]][a[i]] = i) : (fa[i] = fir[pos[l]][a[i]]);
if(pos[l] ^ pos[r])
{
for(register int i = (pos[r] - 1) * block + 1;i <= min(pos[r] * block,n);++i)
a[i] = a[get(i)];
for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
a[i] == x && (a[i] = y,--cnt[pos[r]][wpos[x]],++cnt[pos[r]][wpos[y]],--wcnt[pos[r]][x],++wcnt[pos[r]][y]);
fir[pos[r]][x] = fir[pos[r]][y] = 0;
for(register int i = (pos[r] - 1) * block + 1;i <= min(pos[r] * block,n);++i)
if(a[i] == x || a[i] == y)
!fir[pos[r]][a[i]] ? (fa[i] = 0,fir[pos[r]][a[i]] = i) : (fa[i] = fir[pos[r]][a[i]]);
}
for(register int i = 1;i <= pos[n];++i)
sum[i][wpos[x]] = sum[i - 1][wpos[x]] + cnt[i][wpos[x]],
sum[i][wpos[y]] = sum[i - 1][wpos[y]] + cnt[i][wpos[y]],
wsum[i][x] = wsum[i - 1][x] + wcnt[i][x],
wsum[i][y] = wsum[i - 1][y] + wcnt[i][y];
}
int query(int l,int r,int k)
{
for(register int i = l;i <= min(pos[l] * block,r);++i)
++tcnt[wpos[a[get(i)]]],++tmp[a[get(i)]];
if(pos[l] ^ pos[r])
for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
++tcnt[wpos[a[get(i)]]],++tmp[a[get(i)]];
int s = 0,ret;
int L = pos[l],R = pos[r] - 1;
L > R && (L = R = 0);
for(register int i = 1;i <= wpos[N];++i)
if(s + tcnt[i] + sum[R][i] - sum[L][i] >= k)
{
for(register int j = (i - 1) * wblock + 1;j <= min(i * wblock,N);++j)
if((s += tmp[j] + wsum[R][j] - wsum[L][j]) >= k)
{
ret = j;
break;
}
break;
}
else
s += tcnt[i] + sum[R][i] - sum[L][i];
for(register int i = l;i <= min(pos[l] * block,r);++i)
--tcnt[wpos[a[get(i)]]],--tmp[a[get(i)]];
if(pos[l] ^ pos[r])
for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
--tcnt[wpos[a[get(i)]]],--tmp[a[get(i)]];
return ret;
}
int main()
{
read(n),read(m),block = BLK,wblock = WBLK;
for(register int i = 1;i <= N;++i)
wpos[i] = (i - 1) / wblock + 1;
for(register int i = 1;i <= n;++i)
read(a[i]),pos[i] = (i - 1) / block + 1,
!fir[pos[i]][a[i]] ? (fir[pos[i]][a[i]] = i) : (fa[i] = fir[pos[i]][a[i]]),
++cnt[pos[i]][wpos[a[i]]],++wcnt[pos[i]][a[i]];
for(register int i = 1;i <= wpos[N];++i)
for(register int j = 1;j <= pos[n];++j)
sum[j][i] = sum[j - 1][i] + cnt[j][i];
for(register int i = 1;i <= N;++i)
for(register int j = 1;j <= pos[n];++j)
wsum[j][i] = wsum[j - 1][i] + wcnt[j][i];
for(int op,l,r,x,y;m;--m)
read(op),read(l),read(r),read(x),op == 1 ? (read(y),update(l,r,x,y),1) : printf("%d\n",query(l,r,x));
}