[ARC068] E - Snuke Line
[Q] https://atcoder.jp/contests/arc068/tasks/arc068_c
解説AC。
級数の項数は、思ったより少ないという感覚が迷子。
M=100000
100000 / 1 +
100000 / 2 +
100000 / 3 +
...
100000 / 100000 = 1166750
項数の総和は、1166750。
たったの！1. dを1からMまで走査する。
2. 級数の項の総数は、せいぜい100*10000くらいとわかっているので、それ全探索。
3. 重複してカウントアップしたくないのが、一番の問題。
4. クエリの幅に注目する。R-L+1 >= dなら、鳩ノ巣原理っぽい考えで、絶対にdの倍数が踏むはず。幅がd以上のクエリは1回と見込めばいい。
5. クエリは幅(D)の小さい順にソートして、d未満のものだけBITに収納していけばいい。
実装
template <ll BT>
struct Bit {
ll dat[BT + 10]{};
void add(ll i, ll x) {
++i;
for (; i < BT; i += i & -i) dat[i] += x;
}
ll sum(ll i) {
++i;
ll res = 0;
for (; i > 0; i -= i & -i) res += dat[i];
return res;
}
ll rangesum(ll L, ll R) { // ??
return sum(R) - sum(L - 1);
}
};
// --------------------------------------------------
ll N, M;
int main() {
cincout();
cin >> N >> M;
vector<tuple<ll, ll, ll>> V(N);
rep(i, N) {
auto &[d, L, R] = V[i];
cin >> L >> R;
d = R - L + 1;
}
sort(all(V));
Bit<100010> bits;
ll pos = 0;
ll add = N;
// 1
cout << N << endl;
for (ll d = 2; d <= M; ++d) {
while (pos < N) {
auto &[D, L, R] = V[pos];
if (D >= d) break;
--add;
bits.add(L, 1);
bits.add(R + 1, -1);
++pos;
}
ll ret = add;
for (ll i = d; i <= M; i += d) {
ret += bits.sum(i);
}
cout << ret << endl;
}
}