Overview

For each possible rest start time \(S\), we manage “the number of customers whose entire stay is completely contained within the rest period,” and answer with the smallest \(S\) that minimizes this number.

For update operations, we only update the range of \(S\) affected by the relevant customer. For query operations, we quickly retrieve the overall minimum value and its position.

Analysis

Let a customer’s stay be \([L, R)\) and the rest period be \([S, S+D)\).

The condition under which this customer’s procedure cannot be completed is that their stay is completely contained within the rest period, so:

\[ S \leq L \]

and

\[ R \leq S + D \]

Rearranging the second condition:

\[ S \geq R - D \]

Therefore, the rest start times \(S\) for which this customer cannot complete their procedure are the integers satisfying:

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

Additionally, the rest start time \(S\) must fit within business hours, so:

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

must also be satisfied.

Thus, the range of \(S\) for which this customer contributes \(1\) to the “failure count” is:

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

If this range is non-empty, we add \(+1\) to the failure count for all \(S\) within this range.

For example, if \(D=5\) and a customer’s stay is \([3,7)\), then:

\[ S \leq 3 \]

and

\[ 7 \leq S+5 \]

so:

\[ 2 \leq S \leq 3 \]

That is, this customer cannot complete their procedure only when \(S=2,3\).

---

Naively, if we try all \(S\) for each query and check all customers, the worst case is:

\[ O(QTN) \]

which is too slow given the constraints.

Instead, we use a data structure that can perform bulk additions over the range of \(S\) affected by each customer and quickly retrieve the overall minimum.

The two required operations are:

• Add a value to an interval \([a,b]\)
• Retrieve the overall minimum and the smallest position achieving that minimum

This can be achieved with a segment tree with lazy propagation.

Algorithm

Since the rest start time \(S\) satisfies:

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

we consider an array of length \(T-D+1\).

Let this array be \(cnt[S]\), where:

\[ cnt[S] = \text{the number of customers who cannot complete their procedure when the rest starts at } S \]

For each customer \([L_i,R_i)\), the affected range is:

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

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

If \(a \leq b\), we add \(+1\) to the interval \([a,b]\).

---

For the update operation 1 i L R, we process as follows:

1. Compute the affected range \([a,b]\) for the \(i\)-th customer’s current interval \([L_i,R_i)\)
2. Add \(-1\) to that range
3. Update the customer’s interval to the new \([L,R)\)
4. Compute the affected range \([a,b]\) for the new interval
5. Add \(+1\) to that range

This ensures that \(cnt[S]\) is always correctly maintained for all current customers.

---

For the query operation 2, we simply look at the root of the segment tree.

In the segment tree, for each node we maintain:

• The minimum value within that interval
• The smallest position achieving that minimum

When merging the left and right children, if the left minimum is less than or equal to the right, we adopt the left:

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

This way, when there are multiple positions with the same minimum value, the smallest \(S\) is chosen.

Complexity

• Time complexity: \(O((N+Q)\log T)\)
  • \(O(N\log T)\) for the initial range addition for each customer
  • \(O(\log T)\) per update operation (two range additions)
  • \(O(1)\) per query operation (just reading the root)
• Space complexity: \(O(T+N)\)
  • \(O(T)\) for the segment tree
  • \(O(N)\) for storing each customer’s current interval

Implementation Notes

Preparing a function to compute the affected range makes the implementation concise:

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};
};

Here, maxS = T - D.

When the range is empty, we return a > b so that the range addition is not performed.

Also, note that the rest start time \(S\) is an integer, and the range \([a,b]\) is inclusive on both ends. This is because the condition:

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

is an inequality that includes both endpoints.

Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.