HDU 3333 Turing Tree(樹狀數組 || 線段樹)
題意:給定一個區間,q個查詢,對於每次查詢回答這個區間內所有不重復的數的和。
思路:可以考慮使用樹狀數組來做。
先讀入所有查詢,離線來做,將所有查詢按右端點升序排序。
那麼我們從給定區間的第一個元素開始遍歷這個區間,在此過程中更新每一個元素上一次出現的位置,每次將現在位置加上a[i]並將lastpos位置減去a[i],
也就是說,我們每一步都是保留與當前位置距離最近的重復元素值,其余置零,那麼這樣肯定能保證答案正確,
如果遍歷到的這個位置恰好是一個詢問的右端點,那麼我們輸出修改後的區間值之和。
#include
#include
#include
#include
#include
#include
#include
#include