ARC 068 E - Snuke Line

問題

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

問題概要

個の駅があり、駅に対してからまでの番号が振られている。列車は駅から駅ごとに停車する。また、種類の名産品があり、番目の名産品は駅から駅の区間で売られており、その駅に停まると名産品が買える。の時に買える名産品の個数をそれぞれ求めよ。

• 
• 
• 

アイデア

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

ここで、幅がより大きい区間については必ず買えるので無視して、幅以下の区間についてのみ考えると、この区間についてはたかだか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;
}