题解：P9809 [SHOI2006] 作业 Homework

梦见云月 · 2026-10-24 10:10:09 · 题解

首先是很明显的根号分治吧。

设块长为 B，每次新加入元素时，对于 1\sim B 暴力维护 \min。

查询时小范围可以直接查表，大范围可以用 \texttt{set} 维护分段，对每个段最小值对 x 的模取 \min。

考虑总时间复杂度 O(nB+n \dfrac{V}{B} \log n )

取 B=\sqrt{V\log n} 时有最小值，我比较懒，取了 1500。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int len=1500;
int ans[1505];
set<int>s;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=1500;i++){
        ans[i]=i;
    }
    for (int i=1;i<=n;i++){
        char c;
        int x;
        cin>>c>>x;
        if (c=='A'){
            for (int i=1;i<=len;i++){
                ans[i]=min(ans[i],x%i);
            }
            s.insert(x);
        }
        else{
            if (x<=len){
                cout<<ans[x]<<endl;
                continue;
            }
            int p=x;
            for (int i=0;i<=300000;i+=x){
                auto it=s.lower_bound(i);
                if(it==s.end()){
                    break;
                }
                p=min(p,*it-i);
            }
            cout<<p<<endl;
        }
    }   

    return 0; 
}