概要

営業時間の範囲 \([0, T)\) 内で、長さ \(D\) の休憩時間 \([S, S+D)\) を設定し、その中に滞在時間帯 \([L_i, R_i)\) が完全に含まれてしまう客の人数を最小化する問題です。客の滞在時間の変更（更新）と、最適な \(S\) のクエリに効率的に答える必要があります。

考察

1. 手続きが完了しない条件の言い換え

客 \(i\) の手続きが完了しない条件は、\(S \leq L_i\) かつ \(R_i \leq S+D\) です。これを休憩開始時刻 \(S\) に関する条件に書き換えると以下のようになります。 - \(S \leq L_i\) - \(S \geq R_i - D\)

これらをまとめると、\(R_i - D \leq S \leq L_i\) となります。 また、問題の制約から \(0 \leq S \leq T-D\) である必要があるため、客 \(i\) が原因で「完了しない」人数がカウントされる \(S\) の範囲は： $\([\max(0, R_i - D), \min(L_i, T - D)]\)\( となります。もし \)R_i - L_i > D\( であれば、どのような \)S\( を選んでもこの客の滞在時間は休憩時間（長さ \)D$）に収まりきらないため、この客が原因で人数が増えることはありません。

2. 問題の抽象化

この問題は、以下のように言い換えることができます。 - 各客 \(i\) について、特定の区間 \([s_{start}, s_{end}]\) に含まれるすべての整数 \(S\) に対して「コスト \(1\)」を加算する。 - 変更操作では、古い滞在時間によるコストをマイナスし、新しい滞在時間によるコストをプラスする。 - 質問操作では、コストが最小となっているインデックス \(S\) のうち、最も小さいものとその最小値を答える。

素朴に全 \(S\) について計算すると、質問ごとに \(O(T)\) かかり、全体で \(O(QT)\) となり間に合いません。区間への加算と、全体の最小値（およびその位置）の取得を高速に行うデータ構造が必要です。

アルゴリズム

遅延評価セグメント木

この問題は遅延評価セグメント木（Lazy Segment Tree）を用いることで効率的に解くことができます。

• 管理する範囲: \(0\) から \(T-D\) までの各時刻 \(S\)。
• 保持する情報:
  • min_val: その区間内での「手続きが完了しない客の人数」の最小値。
  • min_idx: 最小値を与える最小のインデックス \(S\)。
  • lazy: 区間加算のための遅延プロパゲーション用の値。
• 操作:
  • 区間加算: 客の条件から導かれた範囲 \([\max(0, R_i - D), \min(L_i, T - D)]\) に対して \(+1\)（追加時）または \(-1\)（変更による削除時）を行う。
  • 全体最小値取得: セグメント木のルート（根）が持つ min_val と min_idx を参照する。

計算量

• 時間計算量: \(O((N + Q) \log T)\)
  • セグメント木の初期構築に \(O(T)\)。
  • 各更新操作（初期状態の \(N\) 人分 ＋ \(Q\) 回の操作）につき \(O(\log T)\)。
  • 質問操作はルートの値を参照するだけなので \(O(1)\)。
• 空間計算量: \(O(T)\)
  • 長さ \(T\) の範囲を管理するセグメント木（通常 \(4T\) 程度のノード数）が必要です。

実装のポイント

• 最小値の更新ルール: セグメント木の push_up（子から親へ情報を上げる際）において、左の子と右の子の min_val が等しい場合は、インデックスが小さい左の子の min_idx を優先するように実装します。これにより「最小の \(S\)」を常に取得できます。

• 範囲の判定: \(R_i - L_i > D\) の場合や、計算した \(s_{start} > s_{end}\) になる場合は、更新を行わないように注意します。

• 高速な入出力: \(N, Q\) が大きいため、C++では cin.tie(nullptr); ios::sync_with_stdio(false); を用いるのが望ましいです。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * The problem asks to find an integer S in [0, T-D] that minimizes the number of customers
 * whose stay [Li, Ri) is completely contained within the break [S, S+D).
 * 
 * Customer i fails to complete their procedure if:
 * S <= Li AND Ri <= S + D
 * which is equivalent to:
 * S <= Li AND S >= Ri - D
 * 
 * Thus, for each customer i such that Ri - Li <= D, they fail if the break start time S
 * is in the range [max(0, Ri - D), min(Li, T - D)].
 * 
 * This is a point coverage problem where we need to find a point S in [0, T-D] covered
 * by the minimum number of these intervals. We use a segment tree with lazy propagation
 * to maintain the coverage counts and query the minimum value and its smallest index.
 */

const int MAXT = 200005;

struct Node {
    int min_val;
    int min_idx;
    int lazy;
} tree[4 * MAXT];

// Propagate the minimum value and its smallest index to parent nodes
void push_up(int node) {
    if (tree[2 * node].min_val <= tree[2 * node + 1].min_val) {
        tree[node].min_val = tree[2 * node].min_val;
        tree[node].min_idx = tree[2 * node].min_idx;
    } else {
        tree[node].min_val = tree[2 * node + 1].min_val;
        tree[node].min_idx = tree[2 * node + 1].min_idx;
    }
}

// Apply an update to a node and mark it for lazy propagation
void apply(int node, int val) {
    tree[node].min_val += val;
    tree[node].lazy += val;
}

// Push the lazy value down to children
void push_down(int node) {
    if (tree[node].lazy != 0) {
        apply(2 * node, tree[node].lazy);
        apply(2 * node + 1, tree[node].lazy);
        tree[node].lazy = 0;
    }
}

// Build the initial segment tree for the range [0, max_s]
void build(int node, int start, int end) {
    tree[node].lazy = 0;
    if (start == end) {
        tree[node].min_val = 0;
        tree[node].min_idx = start;
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    push_up(node);
}

// Range addition update on the segment tree
void update(int node, int start, int end, int l, int r, int val) {
    if (l > r || start > r || end < l) return;
    if (l <= start && end <= r) {
        apply(node, val);
        return;
    }
    push_down(node);
    int mid = (start + end) / 2;
    update(2 * node, start, mid, l, r, val);
    update(2 * node + 1, mid + 1, end, l, r, val);
    push_up(node);
}

int main() {
    // Fast I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, N, D, Q;
    if (!(cin >> T >> N >> D >> Q)) return 0;

    // Current stay intervals for each customer
    vector<int> L(N + 1), R(N + 1);
    int max_s = T - D;
    
    // Initialize segment tree for possible break start times S in [0, T-D]
    build(1, 0, max_s);

    // Helper function to update the coverage count for a customer's fail interval
    auto add_customer_interval = [&](int l, int r, int delta) {
        if (r - l <= D) {
            // Customer fails if S is in [max(0, r-D), min(l, T-D)]
            int s_start = max(0, r - D);
            int s_end = min(l, max_s);
            if (s_start <= s_end) {
                update(1, 0, max_s, s_start, s_end, delta);
            }
        }
    };

    // Read initial customer stays and update segment tree
    for (int i = 1; i <= N; ++i) {
        cin >> L[i] >> R[i];
        add_customer_interval(L[i], R[i], 1);
    }

    // Process Q operations
    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            // Change stay interval for customer i
            int i, newL, newR;
            cin >> i >> newL >> newR;
            // Remove the contribution of the old interval
            add_customer_interval(L[i], R[i], -1);
            L[i] = newL;
            R[i] = newR;
            // Add the contribution of the new interval
            add_customer_interval(L[i], R[i], 1);
        } else {
            // Query: find minimum coverage count and its smallest index S
            // The root of the segment tree always holds the global minimum
            cout << tree[1].min_idx << " " << tree[1].min_val << "\n";
        }
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。