今回のAtCoder Beginner Contestは、最近の中でも特に難易度が高いセットでした。以下、D・E・Fの3問について解法を説明します。

D - Make Target 2

\( \max(|x|,|y|) \) の扱いを簡単にするため、\( |x| > |y| \) の場合と \( |x| \le |y| \) の場合に分けて計算し、最後に合計します。ここでは \( |x| > |y| \) の場合を示します（もう一方も同様です）。

\( |x| > |y| \) のとき、\( \max(|x|,|y|) = |x| \) です。よって \( L \le x \le R \) の範囲で偶数 \( x \) をすべて走査し、各 \( x \) に対し \( |x| > |y| \) かつ \( D \le y \le U \) を満たす \( y \) の個数を求めます。\( |x| > |y| \iff -|x| < y < |x| \) なので、求める \( y \) は \( \max(-|x|+1,\ D) \le y \le \min(|x|-1,\ U) \) の範囲にあり、その個数は \( \max(0,\ \min(|x|-1,U) - \max(-|x|+1,D) + 1) \) です。各 \( x \) での計算は \( O(1) \) で行え、全体で \( O(X) \) (\( X = R-L \)) となります。

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    int L, R, D, U;
    cin >> L >> R >> D >> U;
    ll ans = 0;

    // |x| > |y|
    for (int x = L; x <= R; ++x) {
        if (x % 2 == 0) {
            int low = max(D, -abs(x) + 1);
            int high = min(U, abs(x) - 1);
            if (low <= high) ans += high - low + 1;
        }
    }

    // |x| <= |y|
    for (int y = D; y <= U; ++y) {
        if (y % 2 == 0) {
            int low = max(L, -abs(y));
            int high = min(R, abs(y));
            if (low <= high) ans += high - low + 1;
        }
    }

    cout << ans << '\n';
}

E - A += v

この問題では、操作を繰り返すと各値の出現回数が定期的に変化する性質を利用します。公式解説とは異なるアプローチとして、永続セグメント木を用いて高速にクエリに答える方法を紹介します。

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n, m, q, a[N], cnt[N], mx;
vector<int> pos[N];
int len[N], s[N], root[N];

struct PersistentSegTree {
    struct Node { int ls, rs, sum; } tr[N * 30];
    int idx = 0;

    void update(int &now, int pre, int l, int r, int x) {
        now = ++idx;
        tr[now] = tr[pre];
        tr[now].sum++;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) update(tr[now].ls, tr[pre].ls, l, mid, x);
        else          update(tr[now].rs, tr[pre].rs, mid + 1, r, x);
    }

    int query(int L, int R, int l, int r, int k) {
        if (l == r) return l;
        int left_sum = tr[tr[R].ls].sum - tr[tr[L].ls].sum;
        int mid = (l + r) >> 1;
        if (k <= left_sum) return query(tr[L].ls, tr[R].ls, l, mid, k);
        else               return query(tr[L].rs, tr[R].rs, mid + 1, r, k - left_sum);
    }
} seg;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt[a[i]]++;
        mx = max(mx, cnt[a[i]]);
    }
    for (int i = 1; i <= m; ++i) pos[cnt[i]].push_back(i);

    len[0] = s[0] = pos[0].size();
    for (int i = 1; i <= mx; ++i) {
        len[i] = len[i - 1] + pos[i].size();
        s[i] = s[i - 1] + len[i];
    }

    int cur = 0;
    for (int i = 0; i <= mx; ++i) {
        for (int v : pos[i]) {
            ++cur;
            seg.update(root[cur], root[cur - 1], 1, m, v);
        }
    }

    cin >> q;
    while (q--) {
        long long x; cin >> x;
        if (x <= n) {
            cout << a[x] << "\n";
        } else if (x > 1LL * mx * m) {
            if (x % m == 0) cout << m << "\n";
            else cout << x % m << "\n";
        } else {
            x -= n;
            int lo = 0, hi = mx, mid, tar = mx;
            while (lo <= hi) {
                mid = (lo + hi) >> 1;
                if (x <= s[mid]) { tar = mid; hi = mid - 1; }
                else lo = mid + 1;
            }
            if (tar) x -= s[tar - 1];
            cout << seg.query(root[0], root[len[tar]], 1, m, (int)x) << "\n";
        }
    }
    return 0;
}

F - Grid Clipping

直接数える代わりに、条件を満たさない（クリッピング領域に含まれる）始点の個数を求め、全体から引きます。これは、各障害物によって「その障害物が含まれる矩形」の領域を塗りつぶし、走査線（スイープライン）を用いて重複領域を計算することで効率的に解けます。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 400005;

int H, W, h, w, n;
struct Event {
    int l, r, y, type;
    bool operator < (const Event &o) const {
        if (y != o.y) return y < o.y;
        return type > o.type;
    }
} ev[N * 2];
int X[N * 2];

struct SegTree {
    int sum[N * 4], len[N * 4];
    void push_up(int k, int l, int r) {
        if (sum[k]) len[k] = X[r + 1] - X[l];
        else if (l == r) len[k] = 0;
        else len[k] = len[k * 2] + len[k * 2 + 1];
    }
    void build(int k, int l, int r) {
        if (l == r) { sum[k] = len[k] = 0; return; }
        int mid = (l + r) >> 1;
        build(k * 2, l, mid);
        build(k * 2 + 1, mid + 1, r);
        push_up(k, l, r);
    }
    void update(int k, int l, int r, int ql, int qr, int val) {
        if (X[r + 1] <= ql || X[l] >= qr) return;
        if (ql <= X[l] && X[r + 1] <= qr) {
            sum[k] += val;
            push_up(k, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(k * 2, l, mid, ql, qr, val);
        update(k * 2 + 1, mid + 1, r, ql, qr, val);
        push_up(k, l, r);
    }
} seg;

int main() {
    cin >> H >> W >> h >> w >> n;
    if (n == 0) {
        cout << 1LL * (H - h + 1) * (W - w + 1) << "\n";
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        int u, v; cin >> u >> v;
        int x1 = max(1, u - h + 1);
        int y1 = max(1, v - w + 1);
        int x2 = min(u, H - h + 1) + 1;
        int y2 = min(v, W - w + 1) + 1;
        ev[i * 2]     = {x1, x2, y1, 1};
        ev[i * 2 + 1] = {x1, x2, y2, -1};
        X[i * 2]     = x1;
        X[i * 2 + 1] = x2;
    }
    n *= 2;
    sort(ev, ev + n);
    sort(X, X + n);
    int tot = unique(X, X + n) - X;
    seg.build(1, 0, tot - 2);
    ll area = 0;
    for (int i = 0; i + 1 < n; ++i) {
        seg.update(1, 0, tot - 2, ev[i].l, ev[i].r, ev[i].type);
        area += 1LL * seg.len[1] * (ev[i + 1].y - ev[i].y);
    }
    ll total = 1LL * (H - h + 1) * (W - w + 1);
    cout << total - area << "\n";
    return 0;
}