概要

各休憩開始時刻 \(S\) について、「休憩中に完全に滞在時間が含まれてしまう客の人数」を管理し、その人数が最小となる最小の \(S\) を答える問題です。

変更操作では、該当する客が影響する \(S\) の範囲だけを更新し、質問操作では全体の最小値とその位置を高速に取得します。

考察

ある客の滞在時間を \([L, R)\)、休憩時間を \([S, S+D)\) とします。

この客の手続きが完了しない条件は、滞在時間が休憩時間に完全に含まれることなので、

\[ S \leq L \]

かつ

\[ R \leq S + D \]

です。

2つ目の条件を変形すると、

\[ S \geq R - D \]

となります。

したがって、この客が手続きできないような休憩開始時刻 \(S\) は、

\[ R - D \leq S \leq L \]

を満たす整数です。

さらに、休憩開始時刻 \(S\) は営業時間内に収まる必要があるので、

\[ 0 \leq S \leq T - D \]

も満たす必要があります。

よって、この客が「失敗人数」に \(1\) 加算される \(S\) の範囲は、

\[ \max(0, R-D) \leq S \leq \min(T-D, L) \]

です。

この範囲が空でなければ、その範囲内のすべての \(S\) に対して失敗人数を \(+1\) すればよいです。

例えば、\(D=5\)、客の滞在時間が \([3,7)\) の場合、

\[ S \leq 3 \]

かつ

\[ 7 \leq S+5 \]

なので、

\[ 2 \leq S \leq 3 \]

です。

つまり、\(S=2,3\) のときだけ、この客は手続きできません。

---

素朴に、質問ごとにすべての \(S\) を試し、さらにすべての客を確認すると、最悪で

\[ O(QTN) \]

程度かかってしまい、制約上間に合いません。

そこで、各客が影響する \(S\) の範囲に対して一括で加算し、全体の最小値を高速に取得できるデータ構造を使います。

必要な操作は次の2つです。

• 区間 \([a,b]\) に値を加算する
• 全体の最小値と、その最小値を取る最小の位置を取得する

これは遅延伝播付きセグメント木で実現できます。

アルゴリズム

休憩開始時刻 \(S\) は、

\[ 0 \leq S \leq T-D \]

なので、長さ \(T-D+1\) の配列を考えます。

この配列を \(cnt[S]\) とし、

\[ cnt[S] = \text{休憩開始時刻を } S \text{ にしたとき、手続きできない客の人数} \]

とします。

各客 \([L_i,R_i)\) について、影響する範囲は

\[ a = \max(0, R_i-D) \]

\[ b = \min(T-D, L_i) \]

です。

もし \(a \leq b\) なら、区間 \([a,b]\) に \(+1\) します。

---

変更操作 1 i L R では、次のように処理します。

1. 変更前の \(i\) 番目の客の区間 \([L_i,R_i)\) について、影響する範囲 \([a,b]\) を求める
2. その範囲に \(-1\) する
3. 客の区間を新しい \([L,R)\) に更新する
4. 新しい区間について影響する範囲 \([a,b]\) を求める
5. その範囲に \(+1\) する

これにより、常に現在の客全員に対する \(cnt[S]\) が正しく保たれます。

---

質問操作 2 では、セグメント木の根を見ればよいです。

セグメント木では各区間について、

• その区間内の最小値
• その最小値を取る最小の位置

を管理します。

左右の子をマージするとき、左の最小値が右以下なら左を採用します。

if (mn[left] <= mn[right]) {
    mn[v] = mn[left];
    pos[v] = pos[left];
} else {
    mn[v] = mn[right];
    pos[v] = pos[right];
}

こうすることで、最小値が複数ある場合には、より小さい \(S\) が選ばれます。

計算量

• 時間計算量: \(O((N+Q)\log T)\)
  • 初期状態で各客を1回ずつ区間加算するため \(O(N\log T)\)
  • 各変更操作で区間加算を2回行うため \(O(\log T)\)
  • 各質問操作は根を見るだけなので \(O(1)\)
• 空間計算量: \(O(T+N)\)
  • セグメント木に \(O(T)\)
  • 各客の現在の区間を保存するのに \(O(N)\)

実装のポイント

影響範囲を求める関数を用意しておくと実装が簡潔になります。

auto range = [&](int l, int r) -> pair<int, int> {
    int a = max(0, r - D);
    int b = min(maxS, l);
    if (a > b) return {1, 0};
    return {a, b};
};

ここで maxS = T - D です。

範囲が空の場合は、a > b となるようにしておき、区間加算を行わないようにします。

また、休憩開始時刻 \(S\) は整数で、範囲 \([a,b]\) は両端を含むことに注意が必要です。これは条件

\[ R-D \leq S \leq L \]

が両端を含む不等式だからです。

ソースコード

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

struct SegmentTree {
    int n;
    vector<int> mn, lazy, pos;

    SegmentTree(int n_) : n(n_), mn(4 * n_), lazy(4 * n_, 0), pos(4 * n_) {
        build(1, 0, n - 1);
    }

    void build(int v, int l, int r) {
        if (l == r) {
            mn[v] = 0;
            pos[v] = l;
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);
        pull(v);
    }

    void pull(int v) {
        if (mn[v * 2] <= mn[v * 2 + 1]) {
            mn[v] = mn[v * 2];
            pos[v] = pos[v * 2];
        } else {
            mn[v] = mn[v * 2 + 1];
            pos[v] = pos[v * 2 + 1];
        }
    }

    void apply(int v, int x) {
        mn[v] += x;
        lazy[v] += x;
    }

    void push(int v) {
        if (lazy[v] != 0) {
            apply(v * 2, lazy[v]);
            apply(v * 2 + 1, lazy[v]);
            lazy[v] = 0;
        }
    }

    void add(int ql, int qr, int x) {
        if (ql > qr) return;
        add(1, 0, n - 1, ql, qr, x);
    }

    void add(int v, int l, int r, int ql, int qr, int x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(v, x);
            return;
        }
        push(v);
        int m = (l + r) / 2;
        add(v * 2, l, m, ql, qr, x);
        add(v * 2 + 1, m + 1, r, ql, qr, x);
        pull(v);
    }

    pair<int, int> answer() const {
        return {pos[1], mn[1]};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, N, D, Q;
    cin >> T >> N >> D >> Q;

    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> R[i];
    }

    int maxS = T - D;
    SegmentTree seg(maxS + 1);

    auto range = [&](int l, int r) -> pair<int, int> {
        int a = max(0, r - D);
        int b = min(maxS, l);
        if (a > b) return {1, 0};
        return {a, b};
    };

    for (int i = 0; i < N; i++) {
        auto [a, b] = range(L[i], R[i]);
        if (a <= b) seg.add(a, b, 1);
    }

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int i, l, r;
            cin >> i >> l >> r;
            --i;

            auto [a, b] = range(L[i], R[i]);
            if (a <= b) seg.add(a, b, -1);

            L[i] = l;
            R[i] = r;

            tie(a, b) = range(L[i], R[i]);
            if (a <= b) seg.add(a, b, 1);
        } else {
            auto [s, cnt] = seg.answer();
            cout << s << ' ' << cnt << '\n';
        }
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。