BZOJ 3585：mex——莫隊算法 + 分塊優化

題目描述

數組長度 n，m 次查詢區間 mex（最小非負整數缺失值）。n,m ≤ 200,000。

莫隊算法 + 值域分塊

1. 值域 0..n 分成 √n 塊，維護每塊「出現次數 > 0 的值個數」
2. 莫隊排序查詢，雙指針維護當前區間
3. 添加/移除元素 O(1) 更新計數與塊信息
4. 查詢 mex：掃描塊找第一個未滿塊，塊內暴力掃描，O(√n)

關鍵數據結構

int cnt[MAXV], block_cnt[BLOCKS];
int L[BLOCKS], R[BLOCKS]; // 每塊值域範圍

void add(int x) { if(++cnt[x]==1) ++block_cnt[belong[x]]; }
void del(int x) { if(--cnt[x]==0) --block_cnt[belong[x]]; }

int query_mex() {
    for(int b=0; b

複雜度

莫隊移動：O((n+m)√n)
單次查詢：O(√n)
總：O((n+m)√n) ≈ 1.8×10⁸ 操作，需優化常數