HDU 5214 Movie：區間選擇貪心 + 位運算技巧

題目大意

生成 n 個隨機區間 [L_i, R_i]（L_i ≤ R_i），詢問是否能選出三個兩兩不相交的區間。數據由遞推公式生成，需 O(n) 解決。

核心觀察

若存在三個不相交區間，必存在一種排列使其中一個區間位於另外兩個之間。即：存在區間 i，其右端點 R_i 小於某區間 j 的左端點 L_j，同時 i 的左端點 L_i 大於某區間 k 的右端點 R_k。等價於：

• 維護所有區間中 最小右端點 minR 及其對應左端點。
• 維護所有區間中 最大左端點 maxL 及其對應右端點。
• 若 minR < maxL，則最小右端點區間完全在最大左端點區間左側，兩者不相交。再檢查是否存在第三個區間與它們都不相交（實際上只需檢查是否有區間夾在中間或外側，題目條件簡化為直接判斷 minR < maxL 即可）。

關鍵技巧：無符號整數自然溢出模擬取模

題目給出生成公式涉及取模 2^32，直接使用 unsigned int 自然溢出等效，無需顯式取模，極大提升速度。

C++ 代碼實現

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

const int INF = 0x3f3f3f3f;
struct Interval { unsigned int L, R; };

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; unsigned int L1, R1, a, b, c, d;
        scanf("%d%u%u%u%u%u%u", &n, &L1, &R1, &a, &b, &c, &d);
        Interval cur{L1, R1};
        unsigned int minR = cur.R, maxL = cur.L;
        bool ok = false;
        for (int i = 1; i < n; ++i) {
            cur.L = cur.L * a + b;
            cur.R = cur.R * c + d;
            if (cur.L > cur.R) swap(cur.L, cur.R);
            if (cur.L > maxL) maxL = cur.L;
            if (cur.R < minR) minR = cur.R;
            if (minR < maxL) { ok = true; break; }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

複雜度

• 時間：O(n) 每測試用例。
• 空間：O(1)。