概要

休憩開始時刻 \(S\) を選んだとき、各客の滞在区間が休憩区間に完全に含まれるかを判定する問題を、セグメント木による区間加算と全体最小値クエリに帰着して効率的に解く。

考察

重要な気づき：客ごとに「影響を受ける \(S\) の範囲」を求められる

客 \(i\) の滞在区間 \([L_i, R_i)\) が休憩区間 \([S, S+D)\) に完全に含まれる条件は： $\(S \leq L_i \quad \text{かつ} \quad R_i \leq S + D\)$

これを \(S\) について整理すると： $\(R_i - D \leq S \leq L_i\)$

さらに \(S\) の定義域 \([0, T-D]\) と合わせると、客 \(i\) が手続き未完了となる \(S\) の範囲は： $\(\max(0,\ R_i - D) \leq S \leq \min(L_i,\ T - D)\)$

ただし \(R_i - L_i > D\) の場合、客の区間が休憩より長いので、どの \(S\) を選んでも完全には含まれず、影響なし。

素朴なアプローチの問題

各クエリごとに全ての \(S\)（最大 \(2 \times 10^5\) 通り）と全ての客（最大 \(2 \times 10^5\) 人）を試すと \(O(Q \cdot N \cdot T)\) で TLE。

解決方法

\(S\) の各値に対して「手続き未完了の客数」を管理する配列を考える。客 \(i\) を追加するとき、上で求めた \(S\) の範囲に \(+1\) する（区間加算）。全体の最小値とその位置を求めればよい。これはセグメント木で効率的に処理できる。

アルゴリズム

1. セグメント木の構築: サイズ \(T - D + 1\)（\(S\) の取りうる値の数）のセグメント木を用意する。各ノードは「区間内の最小値」と「最小値を達成する最小の位置」を保持する。遅延伝搬により区間加算をサポートする。

2. 初期化: 各客 \(i\) について、影響範囲 \([\max(0, R_i - D),\ \min(L_i, T-D)]\) に \(+1\) を加算。

3. 変更操作 (1 i L R):

   • 古い区間 \((L_i, R_i)\) について影響範囲に \(-1\) を加算（取り消し）
   • 新しい区間 \((L, R)\) について影響範囲に \(+1\) を加算
   • \((L_i, R_i)\) を更新

4. 質問操作 (2): セグメント木の根から全体の最小値（= 最小の未完了客数）とその位置（= 最適な \(S\)）を取得して出力。

計算量

• 時間計算量: \(O((N + Q) \log T)\)
  • 初期化: \(O(N \log T)\)（各客について区間加算）
  • 各操作: \(O(\log T)\)（区間加算 or 最小値取得）
• 空間計算量: \(O(T + N)\)
  • セグメント木: \(O(T)\)
  • 客の情報: \(O(N)\)

実装のポイント

• 影響範囲の計算: sl = max(0, R - D), sr = min(L, T - D) を求め、sl > sr なら何もしない（区間が休憩より長い場合や、条件を満たす \(S\) が存在しない場合）。

• 最小値の位置管理: セグメント木のマージ時、最小値が同じなら左（小さい方の位置）を優先する。これにより「最も小さい \(S\)」の条件を自然に満たせる。

• 遅延伝搬のセグメント木: 区間加算＋区間最小値という典型的な組み合わせ。加算の遅延を子に伝搬するだけでよい。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> mn, pos, lazy;
    
    void build(int sz) {
        n = sz;
        mn.assign(4 * n, 0);
        pos.resize(4 * n);
        lazy.assign(4 * n, 0);
        init(1, 0, n - 1);
    }
    
    void init(int v, int l, int r) {
        if (l == r) { pos[v] = l; return; }
        int mid = (l + r) / 2;
        init(2*v, l, mid);
        init(2*v+1, mid+1, r);
        pos[v] = l;
    }
    
    void push(int v) {
        if (lazy[v]) {
            mn[2*v] += lazy[v]; lazy[2*v] += lazy[v];
            mn[2*v+1] += lazy[v]; lazy[2*v+1] += lazy[v];
            lazy[v] = 0;
        }
    }
    
    void update(int v, int l, int r, int ql, int qr, int val) {
        if (ql > qr || l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            mn[v] += val; lazy[v] += val; return;
        }
        push(v);
        int mid = (l + r) / 2;
        update(2*v, l, mid, ql, qr, val);
        update(2*v+1, mid+1, r, ql, qr, val);
        if (mn[2*v] <= mn[2*v+1]) { mn[v] = mn[2*v]; pos[v] = pos[2*v]; }
        else { mn[v] = mn[2*v+1]; pos[v] = pos[2*v+1]; }
    }
    
    void update(int ql, int qr, int val) {
        if (ql > qr) return;
        update(1, 0, n - 1, ql, qr, val);
    }
    
    pair<int,int> query() { return {pos[1], mn[1]}; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T, N, D, Q;
    cin >> T >> N >> D >> Q;
    
    vector<int> L(N+1), R(N+1);
    
    SegTree seg;
    seg.build(T - D + 1);
    
    auto add = [&](int l, int r, int val) {
        if (r - l > D) return;
        int sl = max(0, r - D);
        int sr = min(l, T - D);
        if (sl > sr) return;
        seg.update(sl, sr, val);
    };
    
    for (int i = 1; i <= N; i++) {
        cin >> L[i] >> R[i];
        add(L[i], R[i], 1);
    }
    
    for (int q = 0; q < Q; q++) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, nl, nr;
            cin >> i >> nl >> nr;
            add(L[i], R[i], -1);
            L[i] = nl; R[i] = nr;
            add(L[i], R[i], 1);
        } else {
            auto [s, cnt] = seg.query();
            cout << s << " " << cnt << "\n";
        }
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。