這題我使用BIT的方式解，不過時間超過1秒(大概原因可能是TOI是為C++使用者設計，而他這題常數也有點大，如果有更好方法可在下面留言!謝謝!)

參考解法:https://r1cky.pixnet.net/blog/post/53033032

這題我使用BIT的方式解，不過時間超過1秒(大概原因可能是TOI是為C++使用者設計，而他這題常數也有點大，如果有更好方法可在下面留言!謝謝!)

參考解法:https://r1cky.pixnet.net/blog/post/53033032

我補充說明這題要怎麼透過 BIT 解決，這邊附上 nevikw39 (牜攵) 提供 StackOverFlow 上述的英文解說(https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n# )。

核心作法是離散查詢( Offline-Process )＋RSQ( Range Sum Query )。
處理 RSQ 的方式可以透過 SegmentTree 或是 FenwickTree( BIT )。
離線處理：根據右邊界由小到大排序(非莫隊算法，不需要考慮左邊界，比較像掃描線)
RSQ : 目前查詢範圍內有多少個１？
通常看到這邊都會有個疑惑，題目要問的是範圍內有多少數字的種類怎麼樣才可以透過 BIT 實現相同於 PrefixSum 的「抵銷」的效果：BIT_Qry(qR)-BIT_Qry(qL-1)？
關鍵的原因在於若「存在多個相同數值」時讓最靠近目前查詢的那個位置的個數設定為１，其餘相同數值但不同位置的個數都設定為０。若要包含這個數字，必須把這個數字中最右邊的位置也涵蓋進去 ... 所以只需要讓該數值最右側位置的個數為１，其餘的位置是否涵蓋不影響到種類的數量是否+1。

這也是為什麼需要一個額外的數值來紀錄每個數值「最後一次出現的位置」，當下的位置設定為１時要把相同數字的前一個位置從１改為０，而掃描線會由左而右，所以只要依序更新就可以保證除了當下最新位置的個數是１，其他位置的個數必定為０。
至於會被視為莫隊算法是因為題目的要求和 b414/ b416/ b417 非常相似，只是該做法無法應用到前述的３題(？)，前兩者多了”範圍”的要求而第三題則是經典的區間眾數。至於 c710 是複合多種解法的有趣題目，提供給想要練習的大神們。