ある人の滞在時間 \(\lbrack L,R\rparen\) に対して、その人の手続きが完了しない条件を整理してみましょう。

手続きが完了しない条件は \(\lbrack L,R\rparen\subseteq\lbrack S,S+D\rparen\) です。 これは、\(R-D\le S\le L\) と変形することができます。

よって、この問題は \(N\) 個の区間 \(\lbrack R _ i-D,L _ i+1\rparen\) に対して、（更新を行いながら）なるべく覆われていない点を求める問題に帰着されます。

これは、遅延セグメント木や通常のセグメント木を使って解くことができます。

• 遅延セグメント木を使う場合、区間に対して \(1\) を足し引きし、最小値とそのインデックスを求めればよいです。
• 通常のセグメント木を使う場合、imos 法のように区間の先頭に \(+1\) 、末尾に \(-1\) をし、\(\bigl(\)区間内の最小値 \(,\) 区間内の最小値のインデックス \(,\) 区間内の合計\(\bigr)\) などを管理すればよいです。

実装例は以下のようになります。

遅延セグメント木を使った実装例と、通常のセグメント木を使った実装例を載せておきます。

#include <iostream>
#include <vector>
#include <atcoder/lazysegtree>
using namespace std;

int main() {
    int T, N, D, Q;
    cin >> T >> N >> D >> Q;
    int max_S = T - D;

    // [L, R) を S の範囲 [R-D, L+1) に読み替える
    vector<pair<int, int>> intervals(N);
    for (auto& [L, R] : intervals) {
        cin >> L >> R;
        R = max(0, R - D);
        L = max(R, min(L, max_S) + 1);
    }

    // 区間加算・区間最小値を求める遅延セグメント木
    atcoder::lazy_segtree<
        pair<int, int>,
        [](pair<int, int> lhs, pair<int, int> rhs) { return min(lhs, rhs); },
        [] { return make_pair(200001, 0); },
        int,
        [](int f, pair<int, int> x) { return make_pair(x.first + f, x.second); },
        plus{},
        [] { return 0; }
    > segment_tree(max_S + 1);

    // はじめ全体を 0 で初期化しておく
    for (int i = 0; i <= max_S; ++i) {
        segment_tree.set(i, make_pair(0, i));
    }

    for (auto [L, R] : intervals) {
        segment_tree.apply(R, L, 1);
    }

    for (int q = 0; q < Q; ++q) {
        int t;
        cin >> t;
        if (t == 1) { // 更新
            int i, L, R;
            cin >> i >> L >> R;
            --i; // 0-indexed にする
            // [L, R) を S の区間に読み替える
            R = max(0, R - D);
            L = max(R, min(L, max_S) + 1);

            // 古い区間の影響を消して
            auto [old_L, old_R] = intervals[i];
            segment_tree.apply(old_R, old_L, -1);
            segment_tree.apply(R, L, 1); // 新しい区間を足す
            intervals[i] = {L, R};
        } else {
            auto [min, index] = segment_tree.all_prod();
            cout << index << " " << min << endl;
        }
    }
    return 0;
}

from atcoder import lazysegtree


T, N, D, Q = map(int, input().split())
max_S = T - D

# [L, R) を S の範囲 [R-D, L+1) に読み替える
intervals = []
for i in range(N):
    L, R = map(int, input().split())
    R = max(0, R - D)
    L = max(R, min(L, max_S) + 1)


# 区間加算・区間最小値を求める遅延セグメント木
def op(lhs, rhs):
    return min(lhs, rhs)

def map(f, x):
    return (x[0] + f, x[1])

def composition(lhs, rhs):
    return lhs + rhs

# 全体を 0 で初期化
segment_tree = lazysegtree.LazySegTree(op, (N + 1, 0), map, composition, 0, [(0, i, 0) for i in range(max_S + 1)])

for L, R in intervals:
    segment_tree.apply(R, L, 1)

for q in range(Q):
    t, *query = map(int, input().split())
    if t == 1: # 更新
        i, L, R = query
        i -= 1 # 0-indexed にする
        # [L, R) を S の区間に読み替える
        R = max(0, R - D)
        L = max(R, min(L, max_S) + 1)

        # 古い区間の影響を消して
        old_L, old_R = intervals[i]
        segment_tree.apply(old_R, old_L, -1)
        segment_tree.apply(R, L, 1)
        intervals[i] = (L, R)
    else:
        m, index = segment_tree.all_prod()
        print(index, min)

#include <iostream>
#include <vector>
#include <atcoder/segtree>
using namespace std;

int main() {
    int T, N, D, Q;
    cin >> T >> N >> D >> Q;
    int max_S = T - D;

    // [L, R) を S の範囲 [R-D, L+1) に読み替える
    vector<pair<int, int>> intervals(N);
    for (auto& [L, R] : intervals) {
        cin >> L >> R;
        R = max(0, R - D);
        L = max(R, min(L, max_S) + 1);
    }

    // 区間加算・区間最小値を求めるセグメント木
    using segtree_v = tuple<int, int, int>;
    atcoder::segtree<
        segtree_v, 
        [](segtree_v lhs, segtree_v rhs) {
            auto [l_min, l_index, l_sum] = lhs;
            auto [r_min, r_index, r_sum] = rhs;
            // 左右どちらに最小値があるかで場合分け
            if (l_min <= r_min + l_sum) {
                return make_tuple(l_min, l_index, l_sum + r_sum);
            }
            return make_tuple(r_min + l_sum, r_index, l_sum + r_sum);
        },
        [] { return make_tuple(200001, 0, 0); }
    > segment_tree(max_S + 1);

    // はじめ全体を 0 で初期化しておく
    for (int i = 0; i <= max_S; ++i) {
        segment_tree.set(i, make_tuple(0, i, 0));
    }

    // 一点加算
    auto add = [max_S, &segment_tree](int i, int v) {
        if (max_S < i) return;
        auto [min, index, sum] = segment_tree.get(i);
        segment_tree.set(i, make_tuple(min + v, index, sum + v));
    };

    // 区間の始点に +1, 終点に -1
    for (auto [L, R] : intervals) {
        add(R, 1);
        add(L, -1);
    }

    for (int q = 0; q < Q; ++q) {
        int t;
        cin >> t;
        if (t == 1) { // 更新
            int i, L, R;
            cin >> i >> L >> R;
            --i; // 0-indexed にする
            // [L, R) を S の区間に読み替える
            R = max(0, R - D);
            L = max(R, min(L, max_S) + 1);

            // 古い区間の影響を消して
            auto [old_L, old_R] = intervals[i];
            add(old_R, -1);
            add(old_L, 1);
            // 新しい区間を足す
            add(R, 1);
            add(L, -1);
            intervals[i] = {L, R};
        } else {
            auto [min, index, sum] = segment_tree.all_prod();
            cout << index << " " << min << endl;
        }
    }
    return 0;
}

from atcoder import segtree


T, N, D, Q = map(int, input().split())
max_S = T - D

# [L, R) を S の範囲 [R-D, L+1) に読み替える
intervals = []
for i in range(N):
    L, R = map(int, input().split())
    R = max(0, R - D)
    L = max(R, min(L, max_S) + 1)
    intervals.append((L, R))


# 区間加算・区間最小値を求める遅延セグメント木
def op(lhs, rhs):
    l_min, l_index, l_sum = lhs
    r_min, r_index, r_sum = rhs
    if l_min <= r_min + l_sum:
        return (l_min, l_index, l_sum + r_sum)
    return (r_min + l_sum, r_index, l_sum + r_sum)

# 全体を 0 で初期化
segment_tree = segtree.SegTree(op, (N + 1, 0, 0), [(0, i, 0) for i in range(max_S + 1)])

def add(i, v):
    if max_S < i:
        return
    m, index, s = segment_tree.get(i)
    segment_tree.set(i, (m + v, index, s + v))

# 区間の始点に +1, 終点に -1
for L, R in intervals:
    add(R, 1)
    add(L, -1)

for q in range(Q):
    t, *query = map(int, input().split())
    if t == 1: # 更新
        i, L, R = query
        i -= 1 # 0-indexed にする
        # [L, R) を S の区間に読み替える
        R = max(0, R - D)
        L = max(R, min(L, max_S) + 1)

        # 古い区間の影響を消して
        old_L, old_R = intervals[i]
        add(old_R, -1)
        add(old_L, 1)
        # 新しい区間を足す
        add(R, 1)
        add(L, -1)
        intervals[i] = (L, R)
    else:
        m, index, s = segment_tree.all_prod()
        print(index, m)