BZOJ 2821 作詩 —— 區間查詢出現偶數次的數字種類數（分塊 + 預處理）

BZOJ 2821 強制在線查詢：給定長度 n ≤ 10⁵ 的數列，m ≤ 10⁵ 次查詢 [L, R]，求區間內出現次數為正偶數的不同數字個數。查詢需解密：L = (l + ans) % n + 1，R = (r + ans) % n + 1。

一、分塊策略

• 塊大小 B = √n ≈ 316，共 num = n/B 塊。
• pos[i] 記錄位置 i 屬於第幾塊。

二、預處理兩大核心數組

1. 前綴計數 s[block][value]：第 block 塊結束時，數值 value 的累計出現次數。
   構建：s[i][v] = s[i-1][v] + (當前塊內 v 的個數)。
2. 塊間答案 ans[Lblock][Rblock]：從第 Lblock 塊到第 Rblock 塊（整塊覆蓋）的區間內，出現偶數次的數字種類數。
   構建：對每個起始塊 i，掃描到末尾，維護頻率陣列 f[v] 與計數器 cnt，每遇到塊邊界記錄 ans[i][j]。

三、查詢處理

查詢 [l, r]，設 pl = pos[l], pr = pos[r]：

• 同塊：暴力統計 f[v]，直接算答案。
• 跨塊：
  1. 基礎答案 = ans[pl+1][pr-1]（完整中間塊）。
  2. 處理左邊碎塊 [l, pl*B] 與右邊碎塊 [(pr-1)*B+1, r]：
     對每個出現的值 v，計算其在中間完整塊中的出現次數 mid = s[pr-1][v] - s[pl][v]。
     結合碎塊內頻率 f[v]，判斷總頻率奇偶性變化，動態修正答案。

四、關鍵修正邏輯（碎塊處理核心）

// mid: 中間完整塊中 v 的出現次數
// f[v]: 碎塊中目前已掃描到的 v 的次數
// 總次數 = mid + f[v]
// 關注總次數的奇偶性變化

if (mid % 2 == 1) {          // 中間塊貢獻奇數次
    if (f[v] % 2 == 1) ans++; // 奇+奇=偶 → 新增一個偶數種類
    else ans--;               // 奇+偶=奇 → 失去一個偶數種類
} else if (mid > 0) {        // 中間塊貢獻非零偶數次
    if (f[v] % 2 == 1) ans--; // 偶+奇=奇 → 失去
    else ans++;               // 偶+偶=偶 → 新增
} else {                     // 中間塊無貢獻
    if (f[v] > 2 && f[v] % 2 == 1) ans--; // 碎塊內部奇偶翻轉
    if (f[v] % 2 == 0) ans++;
}

五、複雜度分析

• 預處理：O(n√n + c·num)，c ≤ 10⁵ 為顏色種類數。
• 單次查詢：O(√n)（碎塊長度 ≤ 2√n）。
• 總時間：O((n+m)√n) ≈ 3×10⁷ 操作，C++ 優化後可過 2~3 秒時限。

六、工程優化建議

1. 用 static 數組避免棧溢出，maxn = 100005，maxBlock = 320。
2. 快速輸入 read()，避免 cin 慢 IO。
3. 碎塊處理時 f[] 每次查詢 memset 清零，或用時間戳標記優化。
4. 若本機過線上 TLE，嘗試調整塊大小 B = 500~600 減少塊數，或用莫隊算法離線（但本題強制在線）。