题解：P5313 [Ynoi2011] WBLT

dyc2022 · 2026-04-14 17:33:22 · 题解

更好的阅读体验

@ForgetOIDuck 让我来做这道题，说这题难写难调还卡常。但是除了 bitset 的部分有点细节以外，其他并不是特别难写；然后拍了若干组只找出一个糖错；最后也没有非常严重地被卡常。

总之是非常小清新的一道题，为出题人点赞！！111

假定序列长度，询问次数，值域同阶。

假设我们手里已经有了区间中出现的数字集合 S，要如何求出最长的 \bmod \space b 同余的前缀？

我们可以将 S 中元素按照值域分组。具体地，S_k 表示 S 中属于 [kb, (k+1) b) 的数字构成的子集。那么答案就是最大的 k 使得 S_0 \cap S_1 \cap S_2 \cdots \cap S_{k-1} 非空的 k。

我们没有什么很好的结构来维护集合，因此考虑 bitset。接下来考虑怎么由 S 分出 S_0, S_1, \cdots。这个过程可以在 O\left(\frac{|S|}{\min(w, b)}\right) 的时间内实现。

那么我们使用一个普通莫队动态维护这个 S。具体地，我们再多维护一个每个数字出现次数的桶，每插入一个数字 x 的时候，如果这个数字未出现过，就将其插入到 S 中；每删除一个数字 x 的时候，如果删掉它之后区间中不存在数字 x 了，那么就将 x 从 S 中删除。

由于 bitset 的 set(x) 操作和 reset(x) 操作都可以做到 O(1)，因此莫队部分可以在 O(n \sqrt n) 的时间内解决。到这里我们做到了 O\left(n \sqrt n + \sum\frac{n}{\min(w, b)}\right)。

这并不好，当 b 很小的时候就接近 O(n^2)。我们对 b 进行阈值分治，如果 b > w 那么我们就跑刚才的过程，这没问题，是 O\left(n \sqrt n + \frac{n^2}{w} \right) 的。对于 b \le w 的情况，我们把询问挂在 b 上，然后对于所有 b 相同的询问分别跑一次莫队。具体地，我们维护 b 个 bitset，对于一个数字 x，它会被储存在第 x \bmod b 的第 x / b 个位置。查询的时候，我们枚举余数 i，那么余数为 i 时的答案就相当于是对第 i 个 bitset 中的元素求 mex。我们知道对一个大小为 k 的 bitset 求 mex 可以做到 O\left(\frac{k}{w} \right) 的复杂度。我们需要遍历 b 个 bitset，每个 bitset 的大小是 \frac{n}{b}，因此对每一个询问，查询的时间可以做到 O\left(b \times \frac{n}{bw}\right) = O\left(\frac{n}{w}\right)。

接下来分析跑 w 次莫队的复杂度，很多题解在这个地方的分析有误。假设 b=i 的询问有 c_i 组，那么跑 w 次莫队的时间应该是 O\left(\sum_{i \le w} n \sqrt {c_i}\right)。容易发现该式在 c_1 = c_2 \cdots = c_w = \frac{n}{w} 的时候取 max。此时的复杂度是 O\left(wn \sqrt {\frac{n}{w}}\right) = O(n \sqrt{wn})。

至此，问题在 O\left(n \sqrt{wn} + \frac{n^2}{w}\right) 的时间内得到解决。

由于需要支持将 S 按照值域划分成若干个子集，因此需要手写 bitset。代码中的 split(l,r) 函数是将原 bitset 的 [l,r] 区间取出来，放到一个新的 bitset 里面的函数。我自认为实现得非常清晰，详见代码。

#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
using namespace std;
using u64=unsigned long long;
u64 all1[65];
struct Bitset {
    int sz,len; vector<u64> b;
    Bitset(int n=0):sz(n) {len=(sz>>6)+1,b.resize(len+5); for(int i=0;i<=len;i++)b[i]=0;}
    inline void set(int i) {b[i>>6]|=1ull<<(i&63);}
    inline void reset(int i) {b[i>>6]&=~(1ull<<(i&63));}
    inline void set() {for(int i=0;i<=len;i++)b[i]=~0ull;}
    inline void reset() {for(int i=0;i<=len;i++)b[i]=0ull;}
    inline bool any() {for(int i=0;i<=len;i++)if(b[i])return 1; return 0;}
    inline void operator &=(Bitset x) {for(int i=0;i<=len&&i<=x.len;i++)b[i]&=x.b[i];}
    inline int mex() {for(int i=0;i<=len;i++)if(~b[i])return (i<<6)|__builtin_ctzll(~b[i]);}
    inline Bitset split(int l,int r)
    {
        int now=0; Bitset res(r-l+1);
        for(int i=l,c=0;i<=r;i+=64,c++)
        {
            int lb=i,rb=min(i+63,r);
            if(!((lb^rb)>>6))
            {
                int bel=lb>>6; lb&=63,rb&=63;
                res.b[c]=(b[bel]<<(63-rb))>>(lb+63-rb);
            } else {
                int bel1=lb>>6,bel2=rb>>6; lb&=63,rb&=63;
                res.b[c]=((b[bel1]>>lb)&all1[63-lb])|((b[bel2]&all1[rb])<<(64-lb));
            }
        }
        return res;
    }
    inline int query(int k)
    {
        Bitset now(k); now.set();
        int ret=0;
        for(int l=0,r;l<=sz;l=r+1,ret++)
        {
            r=l+k-1,now&=split(l,r);
            if(!now.any())break;
        }
        return ret;
    }
};
struct Ask {int l,r,b,id;};
int n,q,Block,a[N],bel[N],ans[N],buc[N];
Bitset bt1(N+N+64),bt2[70];
vector<Ask> ask[70];
inline void add_big(int x) {if(!buc[x]++)bt1.set(x);}
inline void del_big(int x) {if(!--buc[x])bt1.reset(x);}
inline void add_small(int x,int b) {if(!buc[x]++)bt2[x%b].set(x/b);}
inline void del_small(int x,int b) {if(!--buc[x])bt2[x%b].reset(x/b);}
void solve_big()
{
    if(!ask[0].size())return;
    Block=max<int>(1,n/sqrt((int)ask[0].size()));
    for(int i=1;i<=n;i++)bel[i]=(i-1)/Block+1;
    sort(ask[0].begin(),ask[0].end(),[](Ask x,Ask y) {
        if(bel[x.l]!=bel[y.l])return bel[x.l]<bel[y.l];
        return bel[x.l]&1?x.r<y.r:x.r>y.r;
    });
    int lb=1,rb=0;
    for(auto _:ask[0])
    {
        int l=_.l,r=_.r,b=_.b,id=_.id;
        for(;lb>l;add_big(a[--lb]));
        for(;rb<r;add_big(a[++rb]));
        for(;lb<l;del_big(a[lb++]));
        for(;rb>r;del_big(a[rb--]));
        ans[id]=bt1.query(b);
    }
}
void solve_small(int b)
{
    if(!ask[b].size())return;
    Block=max<int>(1,n/sqrt((int)ask[b].size()));
    for(int i=1;i<=n;i++)bel[i]=(i-1)/Block+1;
    for(int i=0;i<N;i++)buc[i]=0;
    for(int i=0;i<b;i++)bt2[i]=Bitset(N/b+1);
    sort(ask[b].begin(),ask[b].end(),[](Ask x,Ask y) {
        if(bel[x.l]!=bel[y.l])return bel[x.l]<bel[y.l];
        return bel[x.l]&1?x.r<y.r:x.r>y.r;
    });
    int lb=1,rb=0;
    for(auto _:ask[b])
    {
        int l=_.l,r=_.r,id=_.id;
        for(;lb>l;add_small(a[--lb],b));
        for(;rb<r;add_small(a[++rb],b));
        for(;lb<l;del_small(a[lb++],b));
        for(;rb>r;del_small(a[rb--],b));
        for(int i=0;i<b;i++)ans[id]=max(ans[id],bt2[i].mex());
    }
}
main()
{
    scanf("%d",&n),all1[0]=1;
    for(int i=1;i<64;i++)all1[i]=all1[i-1]*2+1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&q);
    for(int i=1,l,r,b;i<=q;i++)
    {
        scanf("%d%d%d",&l,&r,&b);
        if(b>64)ask[0].push_back({l,r,b,i});
        else ask[b].push_back({l,r,b,i});
    }
    solve_big();
    for(int i=1;i<=64;i++)solve_small(i);
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
    return 0;
}