例題：詢問?$n$ 個數中無修改的區間不同數個數，不帶修改（SPOJ的一道題）。

方法1：直接刪

我們嘗試頭鐵地開正常的下標主席樹！

依次插入 $n$ 個數，插入第 $i$ 個數時，我們只要在把第 $i$ 個版本的主席樹的第 $i$ 位 $+1$ 就可以了，表示多出一個數。

但前面與它相同的數怎么處理？

可以記錄每個數上一次出現的位置，在當前版本的主席樹中，給當前位 $+1$ 后，把上一次出現相同數的位置 $-1$，這樣就不會被算重復了。

如果數過大，離散化一下就好了。

然后對于 $[left,right]$ 這樣的區間詢問，在第 $right$ 個版本的線段樹上查詢 $[left,right]$ 的和即可。

方法2：考慮差分思想。

如果我們保守，就換用權值主席樹。

做過 $APIO 2018\space T1$ （的我）即可了解這種思路（那道題讓你用判斷一個區間內是否包含所有顏色，做法有些類似）。

就是你直接把主席樹第 $i$ 個位置的權值 $pre$ 設為這位的數上一次出現的位置。然后查詢一個區間 $[l,r]$ 的顏色數 其實就是查詢區間 $[1,r]$ 有多少個 $pre$ 值 $\lt l$（直接查 $[1,r]$ 是為了方便，答案不變，但不用再寫個數據結構維護）。

重點就是動態查詢前綴中 有多少個數 小于一個給定數，每次在主席樹的第 $r$ 個版本上查權值主席樹中 有多少個數小于 $l$ 就完事了。

這兩個做法都可以直接改成樸素線段樹模擬+離線回答詢問（每達到一個右端點就回答詢問）。也就是說這里強行轉化成主席樹講。

?

例題：一棵樹，每個點都有一種顏色，每次詢問以一個點為根的子樹中的不同顏色數。

用 $dfs$ 序建主席樹的版本 及 使用主席樹的下標，然后只能用上例的方法2維護（一個點要從它的父親的版本轉移過來，定義一個數上一次出現的位置為 它在當前點的祖先中與這個數相等且離這個數所在點最近的點），查詢子樹 轉為 查詢子樹對應的 $dfs$ 序區間 即可。

轉載于:https://www.cnblogs.com/scx2015noip-as-php/p/10003795.html

總結

以上是生活随笔為你收集整理的【基本操作】主席数统计区间不同颜色个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。