読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

ARC 068 E - Snuke Line

AtCoder programming

問題

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

問題概要

M+1個の駅があり、駅に対して0からMまでの番号が振られている。列車は駅0からd駅ごとに停車する。また、N種類の名産品があり、i番目の名産品は駅l_iから駅r_i区間で売られており、その駅に停まると名産品が買える。d=1,2,3, \ldots ,Mの時に買える名産品の個数をそれぞれ求めよ。

  • 1 \le N \le 300000
  • 1 \le M \le 100000
  • 1 \le l_i \le r_i \le M

イデア

まず間隔dを固定して考えてみる。すると、区間の幅(r_i - l_i +1)がdよりも大きい時は、その区間のどこかしらに必ず訪れることになるので、その名産品を買える。一方で、幅がd以下の時はたかだか1回しか訪れることができないのが分かる。

ここで、幅がdより大きい区間については必ず買えるので無視して、幅d以下の区間についてのみ考えると、この区間についてはたかだか1回しか訪れないことがわかっているから区間の累積和を使ってはじめにその位置に含まれる区間の個数を計算してから、dの倍数の位置を調べていけばよいことになる。これでO(N+M)で実現できる。

問題は、d1からMまで動くので、このままでは間に合わない。ただ、幅d以下の区間dを増加させるごとにその数は単調増加になっているので、1からはじめて、上で行った処理をBIT上で行うことで高速に処理することが出来る。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct BIT{
    // [1,n]
    int n; vector<ll> bit;
    // 初期化
    BIT(int _n){
        n = _n;
        bit = vector<ll>(n+1,0);
    }
    // sum of [1,i]
    ll sum(int i){
        ll s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    // add x in i-th element
    void add(int i, ll x){
        while(i<=n){
            bit[i] += x;
            i += i & -i;
        }
    }
};

typedef pair<int,int> pi;
vector<pi> range[101010];

int main()
{
    int N,M;
    scanf(" %d %d", &N, &M);
    rep(i,N)
    {
        int l,r;
        scanf(" %d %d", &l, &r);
        range[r-l+1].pb(pi(l,r));
    }

    BIT bit(M+1);
    int up_d=N;
    for(int d=1; d<=M; ++d)
    {
        for(pi p:range[d])
        {
            bit.add(p.fi,1);
            bit.add(p.se+1,-1);
            --up_d;
        }

        int ct=0;
        for(int i=d; i<=M; i+=d) ct+=bit.sum(i);

        printf("%d\n", up_d + ct);
    }
    return 0;
}