Overview

When choosing a break start time \(S\), we reduce the problem of determining whether each customer’s stay interval is completely contained within the break interval to range addition and global minimum queries using a segment tree, solving it efficiently.

Analysis

Key Insight: For each customer, we can determine “the range of \(S\) values that are affected”

The condition for customer \(i\)’s stay interval \([L_i, R_i)\) to be completely contained within the break interval \([S, S+D)\) is: $\(S \leq L_i \quad \text{and} \quad R_i \leq S + D\)$

Rearranging this in terms of \(S\): $\(R_i - D \leq S \leq L_i\)$

Combined with the domain of \(S\), which is \([0, T-D]\), the range of \(S\) for which customer \(i\)’s procedure is incomplete is: $\(\max(0,\ R_i - D) \leq S \leq \min(L_i,\ T - D)\)$

However, if \(R_i - L_i > D\), the customer’s interval is longer than the break, so no matter which \(S\) is chosen, it is never completely contained, and there is no effect.

Problem with the Naive Approach

For each query, trying all values of \(S\) (up to \(2 \times 10^5\) possibilities) and all customers (up to \(2 \times 10^5\) people) results in \(O(Q \cdot N \cdot T)\), which causes TLE.

Solution

Consider an array that manages “the number of customers with incomplete procedures” for each value of \(S\). When adding customer \(i\), we add \(+1\) to the range of \(S\) computed above (range addition). We then need to find the global minimum and its position. This can be efficiently processed with a segment tree.

Algorithm

1. Segment Tree Construction: Prepare a segment tree of size \(T - D + 1\) (the number of possible values of \(S\)). Each node holds “the minimum value in the interval” and “the smallest position achieving the minimum.” Support range addition through lazy propagation.

2. Initialization: For each customer \(i\), add \(+1\) to the affected range \([\max(0, R_i - D),\ \min(L_i, T-D)]\).

3. Update Operation (1 i L R):

   • Add \(-1\) to the affected range of the old interval \((L_i, R_i)\) (undo)
   • Add \(+1\) to the affected range of the new interval \((L, R)\)
   • Update \((L_i, R_i)\)

4. Query Operation (2): Retrieve and output the global minimum (= minimum number of incomplete customers) and its position (= optimal \(S\)) from the root of the segment tree.

Complexity

• Time Complexity: \(O((N + Q) \log T)\)
  • Initialization: \(O(N \log T)\) (range addition for each customer)
  • Each operation: \(O(\log T)\) (range addition or minimum query)
• Space Complexity: \(O(T + N)\)
  • Segment tree: \(O(T)\)
  • Customer information: \(O(N)\)

Implementation Details

• Computing the affected range: Calculate sl = max(0, R - D), sr = min(L, T - D), and if sl > sr, do nothing (this handles cases where the interval is longer than the break, or no valid \(S\) exists).

• Tracking the position of the minimum: When merging in the segment tree, if the minimum values are equal, prioritize the left (smaller position). This naturally satisfies the “smallest \(S\)” condition.

• Segment tree with lazy propagation: A typical combination of range addition + range minimum. We only need to propagate the addition lazy value to children.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.