之前只做过分块做法，补一下树状数组做法。
我们先考虑一个问题，如何求从[1,x]这一区间内元素不同的个数？显然我们只要从到到位，遇到一个新的元素，就在对应位置+1，然后使用树状数组求前缀和即可。
这里我们需要去求[x,y]，所求区间的左端点也会发生变化。我们先按照[1,x]的方法预处理出这个前缀和数组。我们考虑对询问区间按照左端点排序。然后对于当前的区间[x0,y0]，query(y0) - query(x0 - 1)与正确答案相比有所区别，是因为有些元素在x0左侧计算过了，而在这段区间中，对应第一次出现的位置没有+1。我们考虑能不能弥补这个错误呢。我们预处理出nxt[i]，表示与位置i元素相同的右侧最近元素的下标。这样子，比如上一个区间为[x1,y1]，下一个区间为[x2,y2]，那么我们就让[x1,x2)这段区间中的每一个i的nxt[i]位置都对应+1。如果nxt[i]在[x1,x2)内，则不会对以后的答案造成影响，如果nxt[i]在[x2,]后，则显然修正了这个错误，并且在[i,x2)这段区间中，不会再有相同的元素了。
忘记了树状数组的lowbit x & (-x)必须有括号。
1 #include2 #include 3 #include 4 using namespace std; 5 struct qry 6 { 7 int l,r,id; 8 friend bool operator < (qry a,qry b) 9 {10 return a.l < b.l;11 }12 } vec[510000];13 int n,m;14 int num[510000],nxt[510000],hav[1100000],res[510000],sum[510000];15 int lowbit(int x)16 {17 return x & (-x);18 }19 void tre_insert(int x,int val)20 {21 for (int i = x;i <= n;i += lowbit(i))22 sum[i] += val;23 }24 int tre_qry(int x)25 {26 int tot = 0;27 for (int i = x;i;i -= lowbit(i))28 tot += sum[i];29 return tot;30 }31 int main()32 {33 scanf("%d",&n);34 for (int i = 1;i <= n;i++) 35 scanf("%d",&num[i]);36 scanf("%d",&m);37 for (int i = 1;i <= m;i++)38 {39 scanf("%d%d",&vec[i].l,&vec[i].r);40 vec[i].id = i;41 }42 sort(vec + 1,vec + m + 1);43 for (int i = 1;i <= n;i++)44 if (hav[num[i]] == 0)45 {46 hav[num[i]] = 1;47 tre_insert(i,1);48 }49 memset(hav,0,sizeof(hav));50 for (int i = n;i >= 1;i--)51 {52 if (hav[num[i]] == 0)53 nxt[i] = n + 1;54 else55 nxt[i] = hav[num[i]];56 hav[num[i]] = i;57 } 58 int t = 1;59 for (int i = 1;i <= m;i++)60 { 61 for (;t <= vec[i].l - 1;t++)62 tre_insert(nxt[t],1);63 res[vec[i].id] = tre_qry(vec[i].r) - tre_qry(vec[i].l - 1);64 }65 for (int i = 1;i <= m;i++)66 printf("%d\n",res[i]);67 return 0;68 }