「Ynoi2018」未来日记

第二道 ynoi ……前前后后不知道写了多久。

Idea:fdy Solution:fdy&lxl Std:lxl&csy Data:lxl

“望月悲叹的最初分块” (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))

这个是这个系列中第一个被出出来的题,当时给了多校(然后的确没人做出来耶),然后被搬到了毛营(然后还是没人做出来耶)

这个是我同学出的,不是我出的(当时问我我也不会这题来着),来源似乎是有个 cdqz 高新校区的小朋友看错了一个 cf 题,然后被加强造出来的

这里就直接挂csy的题解了,和我的不太一样,但是大概思路还是差不多的,我的做法是和T1有点类似的维护方法

对这题的评价:8.5/11

—— lxl 博客

[BZOJ 5145]

bzoj怎么挂了

[Luogu 4119]

[HDU 6079]

我是不是什么时候也该去看看未来日记

题意简述

给定一个长 $n$ 的整数序列, $1\le n,m,a_i\le 100000$ , $m$ 个操作,操作包括:

  1. 把区间 $[l,r]$ 中所有 $x$ 变为 $y$ ;
  2. 查询区间 $[l,r]$ 中的第 $k$ 小值。

没强制在线,然而好像并没有离线做法。

主要思路

首先先分块,对序列与值域都分块。以下均在块长 $O(\sqrt{n})$ 下讨论。

分块无修区间第 k 大

先考虑怎么分块做无修区间第 $k$ 大。可以维护两个数组 $C[val][d]$ 表示前 $d$ 块中值为 $val$ 的数的个数, $B[valid][d]$ 表示前 $d$ 块中值在第 $valid$ 个值域块里的数的个数。

询问时维护两个临时数组 $tc[val]$ 与 $tb[valid]$ ,用来处理零碎块的贡献。

然后枚举答案位于哪一个值域块,再在这一个块里暴力枚举答案就可以 $O(\sqrt{n})$ 求出区间第 $k$ 大。

维护修改操作

如何实现将 $[l,r]$ 中 $x$ 变为 $y$ 的操作?

发现 $x$ 变为 $y$ 的操作类似并查集。维护数组 $rt[val][d]$ 表示第 $d$ 块中某个为 $val$ 的数的位置(即任意时刻保证 $a[\ rt[val][d]\ ] = val$ ,若块中无 $val$ 则将 $rt[val][d]$ 设为 $0$)。

再维护并查集数组与函数 $fth[id],find(id)$ ,将第 $d$ 块的值为 $val$ 的数挂到 $rt[val][d]$ 子树上。

此时再来考虑如何实现修改操作。

对于散块,直接将 $x$ 与 $y$ 两棵子树重置。

对于整块 $bid$ :

  • 如果没有 $x$ ,直接跳了;
  • 如果没有 $y$ ,把 $rt[y][bid]$ 设为 $rt[x][bid]$;
  • 如果有 $y$ ,把 $fth[\ rt[x][bid]\ ]$ 设为 $rt[y][bid]$。

最后把$a[\ rt[x][bid]\ ]$ 设为 $y$ ,把 $rt[x][bid]$ 设为 $0$ ,大概想一下应该可以知道为什么。

还要修改 $C[val][d]$ 与 $B[valid][d]$ ,由于只涉及 $x$ 与 $y$ 这两个值,所以暴力修改这两个数组完全可以承受。

最后修改的时间复杂度就是 $O(\sqrt{n})$ 。

参考代码

内存限制 $\text{500MB}$ ,所以块长不能取 $O(\sqrt{n})$ (会爆空间),要稍微开大一点。

记得判 $x$ 与 $y$ 相等的情况,如果不判会莫名挂。

更多细节参考代码。

至于函数名称和大常数就不要在意了……

又长又丑的代码:
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
161
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define reg register
#define Rint register int
#define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
#define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
#define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
#define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
#define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
#define MEM(x,v) memset(x,v,sizeof(x))
#define fir first
#define sec second
#define pq priority_queue
#define PII pair<int,int>
#define MP make_pair
typedef long long LL;
typedef double DB;
#define Templ(T) template<typename T>
inline int read(){
int ans=0,f=1;char c=getchar();
while(c>'9'||c<'0'){ f^=(c=='-'); c=getchar(); }
for(;c<='9'&&c>='0';c=getchar()) ans=ans*10+c-'0'; return f?ans:-ans;
}
Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
#define using_mod
const int mod = 998244353 , N = 100010 , SN = 260 , Vmax = 100000;
#ifdef using_mod
inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
#endif
Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
#define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
}
using namespace my_std;

int n,m,a[N],B[SN][SN],C[N][SN],rt[N][SN],fth[N],tb[SN],tc[N];
int find(int id){ return fth[id] == id ? id : fth[id] = find(fth[id]) ; }
//B[valid][d] : 前 d 块中在值域第 valid 块的数的数量 ; C[val][d] : 前 d 块中值为 val 数的数量
//rt[val][d] : 第 d 块中第一个为 val 的数的位置 ; fth[id] / find(id) : 序号为 id 的位置的并查集数组/函数

const int vblo = 400, vBcnt = 250;
int blo,bl[N],vbl[N],Bcnt;
//blo , vblo : 块长 / 值域块长 ; Bcnt , vBcnt : 块数 / 值域块数
//bl[i] : 序列中第 i 个数所在块 ; vbl[val] : 权值 val 所在的值域块

#define Blo_L(bk) (((bk) - 1) * blo + 1)//块的开头/结尾
#define Blo_R(bk) (min(n , (bk) * blo))
#define Vblo_L(bk) (((bk) - 1) * vblo + 1)//值域块的开头/结尾
#define Vblo_R(bk) (min(Vmax , (bk) * vblo))
int Q[vblo << 1] , *Qt = Q;//手开队列, Q 存 tc[val] 有值的 val (便于下次使用时更新)
int Tmp[vblo << 1];//Tmp 暂存修改零散块时, a[i] 值为 x 或 y 的位置

inline void a_upd(int id){ return void(a[id] = a[find(id)]); }
//a_upd : 字面意思, 将某个位置的值(可能不是当前值)更新为当前的实际值

inline void SBadd(int val){
if(!tc[val]) *(++Qt) = val;
++tc[val];
++tb[ vbl[val] ];
return;
}//SBadd : 零散块(Scattered Block)求 tc[val] 和 tb[valid] 时加入一个值 val
inline void CBupd(int bid,int x,int y,int res){
C[x][bid] -= res , C[y][bid] += res;
if(vbl[x] != vbl[y]) B[ vbl[x] ][bid] -= res , B[ vbl[y] ][bid] += res;
return;
}//CBupd : 整块(Completed Block)中修改 C[val][bid] 和 B[valid][bid] (x -> y)
inline void SBupd(int bid,int l,int r,int x,int y,int &res){
Rint *top = Tmp;
FOR(i,Blo_L(bid),Blo_R(bid)){
a_upd(i);
if(a[i] == x || a[i] == y) *(top++) = i;
}//改 a[i] 和把 x 与 y 子树上的点拿出来
rt[x][bid] = rt[y][bid] = 0;//将这两棵子树重置
for(Rint *i = Tmp;i != top;++i){
if(l <= *i && *i <= r && a[*i] == x) a[*i] = y , ++res;
if(!rt[ a[*i] ][bid]) rt[ a[*i] ][bid] = *i;
fth[ *i ] = rt[ a[*i] ][bid];
}//更新这两棵子树
CBupd(bid,x,y,res);
return;
}//SBupd : 散块(Scattered Block)修改

inline void update(int l,int r,int x,int y){
if(x == y) return;
Rint lb = bl[l] , rb = bl[r] , res = 0;
if(lb == rb){
SBupd(lb,l,r,x,y,res);
FOR(bid,lb + 1,Bcnt) CBupd(bid,x,y,res);//更新后续的块
return;
}
SBupd(lb,l,Blo_R(lb),x,y,res);
FOR(bid,lb + 1,rb - 1){//改整块
if(!rt[x][bid]){//块里没有 x
CBupd(bid,x,y,res);
continue;
}
if(!rt[y][bid]){//有 x 无 y
a[ rt[y][bid] = rt[x][bid] ] = y;
}
else{//有 x 有 y
fth[ rt[x][bid] ] = rt[y][bid];
}
res += C[x][bid] - (C[x][bid - 1] + res);
rt[x][bid] = 0;
CBupd(bid,x,y,res);
}
SBupd(rb,Blo_L(rb),r,x,y,res);
FOR(i,rb + 1,Bcnt) CBupd(i,x,y,res);//更新后续的块
return;
}

inline int query(int l,int r,int k){
Rint lb = bl[l] , rb = bl[r] , res = 0;
Rint val = 1 , lim = vBcnt;
FOR(i,1,vBcnt) tb[i] = 0;
while(Qt != Q) tc[*(Qt--)] = 0;//清理 tc[val] , tb[valid]
if(lb == rb){
FOR(i,l,r) a_upd(i) , SBadd(a[i]);
while(res + tb[val] < k && val <= lim) res += tb[val++];
lim = Vblo_R(val) , val = Vblo_L(val);
while(res + tc[val] < k && val <= lim) res += tc[val++];
return val;
}
ROF(i,Blo_R(lb),l) a_upd(i) , SBadd(a[i]);
FOR(i,Blo_L(rb),r) a_upd(i) , SBadd(a[i]);
while(res + tb[val] + B[val][rb - 1] - B[val][lb] < k && val <= lim){
res += tb[val] + B[val][rb - 1] - B[val][lb] , val++;
}
lim = Vblo_R(val) , val = Vblo_L(val);
while(res + tc[val] + C[val][rb - 1] - C[val][lb] < k && val <= lim){
res += tc[val] + C[val][rb - 1] - C[val][lb] , val++;
}
return val;
}

int main(){
n = read() , m = read();// , blo = ceil(sqrt(n));
blo = ceil(pow(n,0.5204));
Rint cb = 1;
FOR(i,1,n) a[i] = read() , bl[i] = cb , cb += (!(i % blo));//处理 bl[i]
cb = 1;
FOR(i,1,Vmax) vbl[i] = cb , cb += (!(i % vblo));//处理 vbl[val]
Bcnt = bl[n];
FOR(bid,1,Bcnt){
FOR(val,1,Vmax) C[val][bid] = C[val][bid - 1];
FOR(valid,1,vBcnt) B[valid][bid] = B[valid][bid - 1];
FOR(i,Blo_L(bid),Blo_R(bid)){
if(!rt[ a[i] ][bid]) rt[ a[i] ][bid] = i;
fth[i] = rt[ a[i] ][bid];
++B[ vbl[a[i]] ][bid] , ++C[ a[i] ][bid];
}
}//求出初始 B[valid][d] , C[val][d] , rt[val][d] , fth[id]
Rint sta,ql,qr,qx;
FOR(qry,1,m){
sta = read() - 1 , ql = read() , qr = read() , qx = read();
sta ? (void)(printf("%d\n",query(ql,qr,qx))) : (update(ql,qr,qx,read()));
}
return 0;
}

参考资料

lxl 原博客

fr200110217102 的博客