前言
感觉 HH 的项链这道题的思路具有启发性，故记录在此。
题目
对于一个序列 \(a\)，给定 \(m\) 次询问，每次询问求 \([l,r]\) 内有多少个数，相同的数只记一次。
对于样例：
1 2 3 4 3 5
很显然，如果我们询问区间满足 \(3\le l\le r\le 5\)，则对于 \(3\) 这个数，有用的贡献仅有第 \(5\) 位。
所以我们可以将询问的区间按照右端点排序，从左向右处理序列 \(a\)，当处理到第 \(i\) 位时，我们回答所有右端点为 \(i\) 的询问。
然后我们便可以维护一个树状数组，维护的信息是当前有多少个位置产生着贡献，值为 \(1\)。当我们处理到 \(i\) 位时，\([1,i]\) 的和即为现在不同的数的个数。
至于怎么维护，我们注意到值域为 \([1,10^6]\)，因此直接开一个数组对每个数维护上一次出现的位置，当这个数再次出现时把上一次出现位置 \(-1\)，把当前位置 \(+1\) 再回答询问。
代码主要部分：
int j = 0;
for (int i = 1; i <= m; i++) {
if (z[i].r != j) {
for (int k = j + 1; k <= z[i].r; k++) {
if (pos[a[k]]) {
modify(pos[a[k]],-1);
modify(k,1);
pos[a[k]] = k;
}else{
modify(k,1);
pos[a[k]] = k;
}
}
j = z[i].r;
}
z[i].ans = query(z[i].r) - query(z[i].l-1);
}
类似题目
P4113 [HEOI2012] 采花
一句话：用两个树状数组分别维护倒一次和倒二次出现的位置有无贡献。
与上一题不同之处仅在于要求区间内每个数至少出现 \(2\) 次，因此我们维护两个树状数组和两个存放最后一次或倒数第二次出现下标的数组。当一个数出现第 \(2\) 次或更多时，将第一个树状数组该数最后出现的位置 \(+1\)，第二个树状数组该数倒数第二次出现的位置 \(+1\)。如果位置更新，取消原贡献再加上新贡献。
为什么维护了两个树状数组？因为如果一个数在树状数组两个位置都有 \(1\) 的贡献，则最后询问会导致重复。
其实也可以只用一个，但是我当时没想出来