HDU 5172 GTY's gay friends：線段樹優化與前綴和+離線查詢的雙重解法

題目大意

給定長度為 n 的數組，m 次查詢 [l, r]，判斷該區間是否為 1..len 的全排列（len = r-l+1）。
全排列條件：
1. 區間和等於 len*(len+1)/2
2. 區間內無重複元素

初始思路：線段樹維護區間最大「前一次出現位置」

預處理 pre[i] 表示 a[i] 上一次出現的位置（不存在則 0）。
區間 [l, r] 無重複 ⇔ max(pre[l..r]) < l。
線段樹維護區間最大值，查詢 O(log n)。
但 n, m ≤ 10^6 時，線段樹常數過大導致 TLE。

優化方案：前綴和 + 離線處理（O(n + m)）

1. 前綴和 O(1) 判斷區間和是否符合全排列和。
2. 離線查詢 + BIT/樹狀數組：按右端點 r 排序查詢，掃描數組維護每個值最後出現位置，用 BIT 標記「最後出現」，查詢區間和即為不同元素個數。

核心代碼（C++）

const int MAXN = 1e6 + 5;
int a[MAXN], last[MAXN], bit[MAXN];
struct Query { int l, r, id; } q[MAXN];
bool ans[MAXN];

void add(int x, int v) { for (; x < MAXN; x += x & -x) bit[x] += v; }
int sum(int x) { int r = 0; for (; x; x -= x & -x) r += bit[x]; return r; }

int main() {
    int n, m; while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].id = i;
        }
        sort(q + 1, q + m + 1, [](Query a, Query b) { return a.r < b.r; });
        memset(last, 0, sizeof(last));
        memset(bit, 0, sizeof(bit));
        int cur = 1;
        for (int i = 1; i <= m; ++i) {
            while (cur <= q[i].r) {
                if (last[a[cur]]) add(last[a[cur]], -1);
                add(cur, 1);
                last[a[cur]] = cur;
                ++cur;
            }
            int distinct = sum(q[i].r) - sum(q[i].l - 1);
            int len = q[i].r - q[i].l + 1;
            long long expected = 1LL * len * (len + 1) / 2;
            long long actual = prefixSum[q[i].r] - prefixSum[q[i].l - 1];
            ans[q[i].id] = (distinct == len && actual == expected);
        }
        for (int i = 1; i <= m; ++i) puts(ans[i] ? "YES" : "NO");
    }
    return 0;
}

關鍵點總結

• 全排列雙重條件：和正確 + 無重複（異或和不可靠，因 1^2^3 = 0 但非全排列）。
• 離線 + BIT 是處理「區間不同元素個數」的經典模板。
• 數據範圍 10^6 強制 O(n log n) 或 O(n) 算法，線段樹常數過大需避開。