CodeChef The Ball And Cups：翻轉區間後小球位置追蹤

題目大意

N 個杯子排成一行，小球初始在第 C 個。進行 Q 次操作，每次翻轉區間 [L, R]（即對稱交換）。求最終小球位置。N ≤ 10⁵, Q ≤ 10⁴。

核心觀察：單點追蹤

無需模擬整個數組，只需追蹤小球位置 `pos`：

• 若 `pos` 不在 [L, R] → 不變
• 若 `pos` 在 [L, R] → 新位置 = `L + R - pos`（對稱公式）

數學推導

區間 [L, R] 翻轉後，原位置 `x` 映射到 `L + R - x`：

• 中點 `M = (L+R)/2`
• 若 `x ≤ M`：距左端 `d = x - L`，新位置 `R - d = L + R - x`
• 若 `x > M`：距右端 `d = R - x`，新位置 `L + d = L + R - x`

統一公式：`pos = L + R - pos`

快速輸入優化（關鍵）

數據量大（~10⁵ 整數），需 `fread` 緩衝讀取：

class FastInput {
    static const int BUFSIZE = 1<<16;
    char buf[BUFSIZE]; int idx, size;
    inline char nextChar() {
        if (idx >= size) { size = fread(buf,1,BUFSIZE,stdin); idx=0; }
        return buf[idx++];
    }
public:
    int nextInt() {
        char c; int x=0;
        do c = nextChar(); while (c<'0' || c>'9');
        do { x = x*10 + (c-'0'); c = nextChar(); } while (c>='0' && c<='9');
        return x;
    }
};

完整代碼實現

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

struct FastInput {
    static const int SZ = 1<<16;
    char buf[SZ]; int idx=0, len=0;
    inline char nc() {
        if (idx >= len) { len = fread(buf,1,SZ,stdin); idx=0; }
        return idx < len ? buf[idx++] : 0;
    }
    int nextInt() {
        char c; int x=0;
        do c = nc(); while (c && (c<'0' || c>'9'));
        for (; c>='0' && c<='9'; c = nc()) x = x*10 + (c-'0');
        return x;
    }
} In;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T = In.nextInt();
    while (T--) {
        int N = In.nextInt();
        int C = In.nextInt();
        int Q = In.nextInt();
        
        int pos = C;
        while (Q--) {
            int L = In.nextInt(), R = In.nextInt();
            if (pos >= L && pos <= R) pos = L + R - pos;
        }
        cout << pos << '\n';
    }
    return 0;
}

關鍵點總結

1. 單點追蹤：O(Q) 時間，O(1) 空間，避免模擬整個數組
2. 對稱公式：`pos = L + R - pos` 統一處理左右兩側
3. 快速輸入：`fread` 緩衝 + 手寫解析，比 `scanf`/`cin` 快 5-10 倍
4. 邊界處理：`pos` 不在區間時直接跳過

此題展示了「數學規律替代模擬」與「快速 IO」的經典組合，是競賽編程中處理大數據區間翻轉問題的標準範式。