E - Snuke Line

E - Snuke Line

d毎に行ける駅をm log nで見れる
累積和を使えば各駅に置かれる名産品の数がわかる
ここで、dで行ける駅について名産品の数を加算していくと名産品が重複してしまう

なので、区間の長さがd以上の名産品は必ず取れることと、区間の長さがd未満の名産品は高々1回しか取れないことを利用する
具体的にはdを見るとき長さがd未満のものだけ累積和をとり、d以上の物は答えに加算する
E - Snuke Line
Submission #4180714 - AtCoder Regular Contest 068

vp p;

signed main() {
    cin >> n >> m;
    addn(p, n);
    sort(all(p), [](P a, P b) { return a.se - a.fi < b.se - b.fi; });
    vi ls(n);
    rep(i, n)ls[i] = p[i].second - p[i].first;
    BIT<> bt(m + 5);
    for (int i = 1, pi = 0; i < m + 1; i++) {
        if (pi < n) {
            int ti = lowerIndex(ls, i) - 1;
            for (; pi <= ti; pi++) {
                bt.add(p[pi].F, 1);
                bt.add(p[pi].S + 1, -1);
            }
        }
        cou = 0;
        for (int v = 0; v < m + 1; v += i) {
            cou += bt.sum(v + 1);
        }
        cout << n - pi + cou << endl;
    }

    return 0;
}