树状数组（求区间内不同的数的个数）

这个性质我本来是想用线段树写的，但是忽略了每次只是访问该点往前的区间，所以没能写出来

本质上还是一个动态维护前缀和的问题

tr[i], 表示在当前位置上有不同的点 每次我们求当前位置到某一位置的不同的点的数量，只需要保证往前看的序列中重复的点只保留最后一个即可

例题：2019山东省赛 ： BaoBao Loves Reading (金牌题)

思路：每次添加一个点，只需要考虑一下这个点对整个答案序列的贡献即可

算法：树状数组 + 差分

#include  <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N];
int dif[N];
int pre[N];
int tr[N], n;

int lowbit(int x) {
    return x & -x;
}

int add(int x, int v) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; 
}

int sum(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void init() {
    for(int i = 0; i <= n; i ++ ) {
        dif[i] = 0;
        tr[i] = 0;
        pre[i] = 0;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    
    while(T -- ) {
        
        
        scanf("%d", &n);
        
        init();
        
        for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        
        for(int i = 1; i <= n; i ++ ) {
            int j = a[i];
            if(pre[j] == 0) {
                dif[0] ++;
                add(i, 1);
            }
            else {
                add(i, 1);
                add(pre[j], -1);
                int d = sum(i) - sum(pre[j]);
                dif[0] ++, dif[d] --;
                //printf("i : %d d : %d\n", i, d);
            }
            pre[j] = i;
        }
        
        //cout << tr[1].f << '\n';
        
        for(int i = 1; i <= n; i ++ ) {
            dif[i] += dif[i -1];
            printf("%d", dif[i]);
            if(i != n) printf(" ");
        }
        puts("");
    }
    
    return 0;
}