[ARC068E] Snuke Line 解题报告

题意

[ARC068E] Snuke Line

给定 $n$ 个区间 $[l_i,r_i]\ (1\le l_i \le r_i \le m)$。
对 $1\sim m$ 中的每一个 $i$，求出存在一个 $i$ 的倍数在其中的区间个数。

解法 1（整除分块）

我们发现，对于一个 $d$ 来说，$[l,r]$ 中有 $d$ 的倍数的充要条件是 $\left \lfloor \dfrac{l-1}{d} \right \rfloor \neq \left \lfloor \dfrac{r}{d} \right \rfloor$。

略证：

（引理）$\left \lceil \dfrac{x}{y} \right \rceil = \left \lfloor \dfrac{x-1}{y} \right \rfloor +1$。

证明：设 $x=ky+b$，其中 $k=\left \lfloor \dfrac{x}{y} \right \rfloor$，然后分类讨论 $b=0$ 和 $b\ne 0$ 时即可证明。

原命题等价命题为，存在 $x\in \mathbb Z$，使得 $l \le d\cdot x \le r$。

$$\begin{aligned} &\iff \left \lceil \dfrac{l}{d} \right \rceil \le x \le \left \lfloor \dfrac{r}{d} \right \rfloor\\ &\iff \left \lfloor \dfrac{l-1}{d} \right \rfloor +1 \le x \le \left \lfloor \dfrac{r}{d} \right \rfloor\ (\text{由引理可得})\\ &\iff \left \lfloor \dfrac{l-1}{d} \right \rfloor < x \le \left \lfloor \dfrac{r}{d} \right \rfloor\\\ &\iff \left \lfloor \dfrac{l-1}{d} \right \rfloor < \left \lfloor \dfrac{r}{d} \right \rfloor \end{aligned}$$

然后只要对 $l-1$ 和 $r$ 进行一个二维整除分块即可，对每次求出的区间差分即可。

如果你不会整除分块，可以参考 OI Wiki 数论分块/N维数论分块

复杂度 $O(n \sqrt m)$。

参考代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 +5;
int ans[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        --x;
        for(int l=1,r;l<=m;l=r+1){
            r = min(l>x ? m : x/(x/l)
                   ,l>y ? m : y/(y/l));
            if(x/l != y/l) ans[l]++,ans[r+1]--;
        }
    }

    for(int i=1;i<=m;i++)ans[i]+=ans[i-1];
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}

解法 2（找性质+树状数组）

由调和级数告诉我们，可以对每个 $d=1\sim m$，枚举出所有的 $d$ 的倍数，总共只有 $O(m \log m)$ 的数。

如果用一个数据结构把区间都加一，然后查询单点查询答案加起来，关键就是如何处理一个区间的贡献会被重复计算的问题。

我们不难发现一个关键性质：如果区间长度 $\ge d$，那么一定包含一个 $d$ 的倍数，否则一个区间最多被算一次。

这样就可以从小到大枚举 $d$，然后每次把长度 $< d$ 的区间加进树状数组，查出所有 $d$ 的倍数之后再加上长度 $\ge d$ 的区间个数就可以得到答案了。

复杂度 $O(m\log^2 m + n\log m)$。

参考代码

#include<bits/stdc++.h>
using namespace std;

template<typename T = int >
struct BIT{
    int n;
    vector<T> t;
    BIT(int _n):n(_n+1),t(_n+2){}
    void add(int i,T x){i++;for(;i<=n;i+=i&-i)t[i]+=x;}
    void add(int l,int r,T x){add(l,x);add(r+1,-x);}
    T query(int i){i++;T da=0;for(;i;i-=i&-i)da+=t[i];return da;}
    T query(int l,int r){return query(r)-query(l-1);}
};


int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    vector<pair<int,int>> seg;
    int n,m;cin>>n>>m;
    BIT t(m);
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        seg.push_back({x,y});
    }
    sort(seg.begin(),seg.end(),
        [](const pair<int,int>& lhs,const pair<int,int>& rhs){
            return lhs.second-lhs.first < rhs.second-rhs.first;
        });

    for(int d=1,now=0;d<=m;d++){
        while(now<seg.size() && seg[now].second-seg[now].first+1<d){
            t.add(seg[now].first, seg[now].second, 1); // 加入较小的区间
            ++now;
        }
        int ans = seg.size()-now; // 比较长的区间
        for(int i=d;i<=m;i+=d)ans+=t.query(i); // 枚举 d 的倍数
        cout<<ans<<'\n';
    }
    return 0;
}

解法 3 （二维数点）

考虑反过来，做没有任何一个倍数的区间个数。

对于一个 $d$ 来说，把 $0$、它的倍数和 $m$ 取出来，也就是 $0,d,2d,\ldots,kd,m$，其中 $kd$ 是小于 $m$ 的最大 $d$ 倍数，记作 $a_1,a_2,\ldots,a_c$。

原问题就可以在转化为对所有 $k$ 计算 $a_k < l_i < r_i < a_{k+1}$ 的二元整数对 $(l_i,r_i)$ 个数。这就是一个经典的二维数点问题。

由调和级数可知，我们要做 $O(m \log m)$ 次二维数点，每次复杂度 $O(\log m)$。

总复杂度 $O(n\log m + m\log^2 m)$。

（下面的是主席树的参考代码，其他算法比如扫描线也可以做，但是我懒得写了）

参考代码

#include<bits/stdc++.h>
using namespace std;


const int M = 1e5+5;

// 主席树
struct Node{
    int s,l,r;
}t[M<<6];
int rt[M];
int tot;
int copy(int o){
    ++tot;
    t[tot]=t[o];
    return tot;
}
int add(int o,int l,int r,int qi){
    o = copy(o);
    if(l==r){
        t[o].s++;
        return o;
    }

    int mid=(l+r)>>1;
    if(qi<=mid)t[o].l=add(t[o].l,l,mid,qi);
    else       t[o].r=add(t[o].r,mid+1,r,qi);
    t[o].s = t[t[o].l].s + t[t[o].r].s;
    return o;
}
int query(int u,int v,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr)return t[u].s-t[v].s;
    int mid=(l+r)>>1;
    if(qr<=mid)return query(t[u].l, t[v].l, l,mid,ql,qr);
    if(ql>mid) return query(t[u].r,t[v].r,mid+1,r,ql,qr);
    return query(t[u].l, t[v].l, l,mid,ql,qr)+query(t[u].r,t[v].r,mid+1,r,ql,qr);
}

vector<int> rs[M];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        rs[x].push_back(y);
    }

    for(int i=1;i<=m;i++){
        rt[i]=rt[i-1];
        for(int x:rs[i])rt[i]=add(rt[i],1,m,x);
    }

    cout << n << '\n'; // d=1直接特判掉
    for(int d=2;d<=m;d++){
        int ans = n;
        for(int now=d;now<=m;now+=d){
            int l = now-d+1;
            int r = now-1;
            ans -= query(rt[r],rt[l-1],1,m,l,r);
        }
        if(m%d!=0){
            int l = m/d*d+1;
            int r = m;
            ans -= query(rt[r],rt[l-1],1,m,l,r);
        }
        cout << ans << '\n';
    }
    return 0;
}

总结

提交记录对比：