题解：P9809 [SHOI2006] 作业 Homework

· · 题解

提供一个理论上写起来比较快的代码。

首先设置阈值 B，当 Y \le B 的时候我们预处理出 \bmod Y 最小的值即可，这部分时间复杂度 \mathcal O(nB)。

当 Y>B 的时候我们枚举 c=kY(k \in \mathbb N)，则在 [c,c+Y-1] 中要找到一个最小的值 x，并且对所有 x-c 取 \min。这部分时间复杂度为 \mathcal O(\dfrac{mV}{B} \cdot f)，其中 f 表示单次查询的复杂度。

我们设 n,m,V 同阶，取 B = \mathcal O(\sqrt{nf}) 即可做到 \mathcal O(n\sqrt{nf}) 复杂度。这里 f 大概是多少呢？取决于我们的实现方式。

对于 std::set 的维护可能是平凡的，但我们可以三层分块一下，这样我们的查询 f=\mathcal O(1)。

附上查询后继的方式：

u64 L0[4692],L1[76],L2[4];

inline void insert(u32 x){
    L0[x>>6]|=1ull<<(x&63);
    L1[x>>12]|=1ull<<((x>>6)&63);
    L2[x>>18]|=1ull<<((x>>12)&63);
}

inline u32 nxt(u32 x){
    if(x>M)return inf;
    u32 i0=x>>6,b0=x&63;
    if(u64 w=L0[i0]&(~0ull<<b0))return(i0<<6)|countr_zero(w);
    u32 i1=(i0+1)>>6,b1=(i0+1)&63;
    if(u64 w=L1[i1]&(~0ull<<b1)){
        u32 n1=(i1<<6)|countr_zero(w);
        return(n1<<6)|countr_zero(L0[n1]);
    }
    u32 i2=(i1+1)>>6,b2=(i1+1)&63;
    if(u64 w=L2[i2]&(~0ull<<b2)){
        u32 n2=(i2<<6)|countr_zero(w);
        u32 n1=(n2<<6)|countr_zero(L1[n2]);
        return(n1<<6)|countr_zero(L0[n1]);
    }
    return inf;
}