https://beta.atcoder.jp/contests/arc068
C
はい。
D
結局2枚捨てるという操作なので。
E
解法2つあります。
dの倍数のdを小さくすると、r - l <= dを満たす区間、つまりl<=x < r の間にdの倍数が1つ以上ある区間の数は増えていきます。
これを利用する方法が1つです。
もうひとつは区間(l,r)を二次元plotすると、長方形領域にある点の数を数える問題になるので平面走査する方法です。
下のコードは2つ目の方法ですが、範囲を±1でミスりまくって結構辛かった。
区間の長さを短くするというのも本質的な考察になるんですね。二次元plotの方は思いついてもよかったなぁ。
int N, M; vi point[MAX_N]; vector<pi> interval[MAX_N]; int ans[MAX_N]; BIT bit; void solve() { cin >> N >> M; bit.init(M + 2); rep(i, 0, N) { int l, r; cin >> l >> r; r++; point[l].pb(r); } rep(i, 1, M + 1) { for(int j = -i; j + i <= M; j += i) { int l = j, r = j + i; if(l >= 0) interval[l + 1].pb(pi(r + 1, -i)); interval[r + 1].pb(pi(r + 1, i)); } } rep(i, 0, M + 2) { rep(j, 0, sz(interval[i])) { pi p = interval[i][j]; int v = abs(p.sec); if(p.sec < 0) { ans[v] -= bit.get(p.fst, M + 2); } else ans[v] += bit.get(p.fst, M + 2); } rep(j, 0, sz(point[i])) { int p = point[i][j]; bit.update(p, p + 1, 1); } } rep(i, 1, M + 1) { cout << ans[i] << "\n"; } }