P9809 [SHOI2006] 作业 Homework 题解
Zskioaert1106
·
·
题解
题目传送门：P9809 [SHOI2006] 作业 Homework
题目分析
由标签可知，本题考虑根号分治。
视值域与 n 同阶，设一个阈值 \sqrt{n}。
当询问 x 时，若 x < \sqrt{n}，由于只有 \sqrt{n} 种，所以在加入时暴力维护，询问直接回答即可；
若 x \geqslant \sqrt{n}，我们枚举商 k，则 xk \leqslant n 的 k 只有 \sqrt{n} 种。
现在的需求是 O(1) 查询在 [xk,xk+x) 中最小的出现过的元素。
将问题转化为在 [xk,+\infty) 中最小的出现过的元素是否小于 xk+x。
聚集一个点 i，能对其贡献的 x 是所有大于等于 i 的。因此在加入 x 时等价于对 [1,x] 取一个前缀 \min。
分块。由于这个东西肯定是单调不降的，所以一定存在一个块使得左右端点分居 x 两侧。对这个块以及 x 初始的块暴力更新，其他的打个标记就行了。
代码实现
$f_2$：块的标记；
$f_3$：块内部的答案。
```cpp
while(n--){
char opt;
int x;
cin>>opt>>x;
if(opt=='A'){
mn=min(mn,x);
for(int i=1;i<lim;i++)f1[i]=min(f1[i],x%i);
for(int i=L[b[x]];i<=x;i++)f3[i]=min(f3[i],x);
for(int i=b[x]-1;i>=0;i--){
if(f2[i]<=x)break;
f2[i]=x;
}
}
else{
if(x<lim)cout<<f1[x]<<'\n';
else{
int ans=mn;
for(int i=0;i*x<N;i++){
int l=i*x,r=min((i+1)*x,N)-1;
f3[l]=min(f3[l],f2[b[l]]);
if(f3[l]<=r)ans=min(ans,f3[l]-i*x);
}
cout<<ans<<'\n';
}
}
}
```
[AC 记录](https://www.luogu.com.cn/record/275609750)。