考點：在線+主席樹（或稱為可持久化線段樹）

暴力解法：

對於一個範圍[0, r)的數據（我喜歡用0-based編號和左閉右開區間），我們開一個清單last_occurrence，其中last_occurrence[i] = i在[0, r)範圍內，最後一次出現的位子，若i未在此範圍內出現，則將其定為一個足夠小的值（事實上-1已足夠小），而詢問[l, r)的答案即是last_occurrence中前綴最大值比l小的第一個位子。當然，因為一個有n個數的數列，其mex值絕對不會超過n，所以last_occurrence長度開n就夠了。

優化：

上方的last_occurrence陣列可以開最小值線段樹，這樣一來找出前綴最大值比l小的第一個位子，就可以用線段樹上全域二分搜。線段樹可以選擇每次詢問重蓋一個（TLE）或是r從1到n各蓋一個數據範圍是[0, r)的線段樹（又TLE又MLE，但單次查詢複雜度O(log n)）。

再優化：

事實上上方所說數據範圍是[0, r)的線段樹，和數據範圍是[0, r + 1)的線段樹，最多只會有O(log n)個節點的值不同，所以此二個線段樹的其他節點可以共用，只需將有差異的節點複製一次即可，而這就是主席樹的精神所在。對於詢問[l, r)，對數據範圍是[0, r)的那個線段樹做二分搜即可。然後要好好記錄各個線段樹的根節點，不能因為一開始給的數列的某個數值太大，就在讀入那個數值之後未將線段樹做對應處理（此時下一個線段樹和前一個線段樹完全相同，如果資料大小開得適當的話）。

複雜度分析：

預處理n個線段樹時間：O(n log n)
詢問時間：O(log n)/次
總時間：O((n + q) log n)
空間：O(n log n)（就是主席樹所用的空間，每個版本線段樹會新增O(log n)個節點，共有n個版本）
AC（實測0.3s, 97.3MB）

常數優化：

1. 使用C++快讀快寫（網路上容易找到相關資料，我有使用）

2. 不能用迭代式線段樹，因為要做主席樹（但迭代式線段樹的常數較小）

註1：

我在實作此題時，一度因為讀入數列的某些數值過大，未將線段樹做對應處理，導致評測時一度WA和RE。幸好在本機端產生了二組測資之後，就被RE卡掉而得以成功debug。

註2：

這提供了區間mex（離線）的又一作法。就是先將詢問按右界由小而大排序，然後開上面所說的線段樹（一個即可）。將右界是r的詢問都處理完後，可以很快的加入數列第r項（注意編號是0-based）的資料到線段樹中（O(log n)，直接修改線段樹），然後就可以接著處理右界是r + 1的詢問。

註3：

本題解若有不清楚的部分，請隨時留言。

考點：在線+主席樹（或稱為可持久化線段樹）

 

暴力解法：

對於一個範圍[0, r)的數據（我喜歡用0-based編號和左閉右開區間），我們開一個清單last_occurrence，其中last_occurrence[i] = i在[0, r)範圍內，最後一次出現的位子，若i未在此範圍內出現，則將其定為一個足夠小的值（事實上-1已足夠小），而詢問[l, r)的答案即是last_occurrence中前綴最大值比l小的第一個位子。當然，因為一個有n個數的數列，其mex值絕對不會超過n，所以last_occurrence長度開n就夠了。

 

優化：

上方的last_occurrence陣列可以開最小值線段樹，這樣一來找出前綴最大值比l小的第一個位子，就可以用線段樹上全域二分搜。線段樹可以選擇每次詢問重蓋一個（TLE）或是r從1到n各蓋一個數據範圍是[0, r)的線段樹（又TLE又MLE，但單次查詢複雜度O(log n)）。

 

再優化：

事實上上方所說數據範圍是[0, r)的線段樹，和數據範圍是[0, r + 1)的線段樹，最多只會有O(log n)個節點的值不同，所以此二個線段樹的其他節點可以共用，只需將有差異的節點複製一次即可，而這就是主席樹的精神所在。對於詢問[l, r)，對數據範圍是[0, r)的那個線段樹做二分搜即可。然後要好好記錄各個線段樹的根節點，不能因為一開始給的數列的某個數值太大，就在讀入那個數值之後未將線段樹做對應處理（此時下一個線段樹和前一個線段樹完全相同，如果資料大小開得適當的話）。

 

複雜度分析：

預處理n個線段樹時間：O(n log n)
詢問時間：O(log n)/次
總時間：O((n + q) log n)
空間：O(n log n)（就是主席樹所用的空間，每個版本線段樹會新增O(log n)個節點，共有n個版本）
AC（實測0.3s, 97.3MB）

 

常數優化：

1. 使用C++快讀快寫（網路上容易找到相關資料，我有使用）

2. 不能用迭代式線段樹，因為要做主席樹（但迭代式線段樹的常數較小）

 

註1：

我在實作此題時，一度因為讀入數列的某些數值過大，未將線段樹做對應處理，導致評測時一度WA和RE。幸好在本機端產生了二組測資之後，就被RE卡掉而得以成功debug。

 

註2：

這提供了區間mex（離線）的又一作法。就是先將詢問按右界由小而大排序，然後開上面所說的線段樹（一個即可）。將右界是r的詢問都處理完後，可以很快的加入數列第r項（注意編號是0-based）的資料到線段樹中（O(log n)，直接修改線段樹），然後就可以接著處理右界是r + 1的詢問。

 

註3：

本題解若有不清楚的部分，請隨時留言。

上面常數優化少打了一點，補充如下：

3. 本題中主席樹只需使用建構、修改（即新建一個版本的線段樹，需複製O(log n)個節點）、複製前一版本的線段樹，以及不同版本線段樹上二分搜，所以只需實作那些功能。然後可以使用堆疊（stack）來取代遞迴。