BZOJ 1878 [SDOI2009]HH的项链 离线+树状数组

题意：

给一个n个数的序列，m个询问，每次询问一个区间内不相同的数的个数。

方法：

离线+树状数组

解析：

看完题后的确有段时间没有头绪，想过线段树来搞，不过好像很麻烦，然后听他们说离线下来搞。再推了1节课差不多就明白了。

离线和在线差距的确很大。

如果离线的话，所有的区间是呈线性的。大体思路是什么呢？就是每个数，我们都可以预处理出他上一次出现是在什么位置。然后对于一个区间的询问[l,r]，我们可以这么去想这个询问：l~r中的数的上一次出现的位置在l左边的数的个数。

这样就很好弄了，先把所有的区间按右端点排序。

每次添加元素的时候，将它上一次出现的位置+1的地方的值加1，然后在其本身位置+1的值打上个-1标记，这样就成了线性求值，也就是每次求getsum(a[i].l)。

#include <stdio.h>
#include <algorithm>
using namespace std ;
struct node
{
    int l ;
    int r ;
    int id ;
};
node a[200100] ;
int pre[200100] ;
int col[200100] ;
int c[200100] ;
int ans[200100] ;
int last[1000100] ;
int n;
int lowbit(int x)
{
    return x&(-x) ;
}
void update(int x , int p)
{
    while(x <= n)
    {
        c[x] += p ;
        x += lowbit(x) ;
    }
}
int getsum(int x)
{
    int sum = 0 ;
    while(x)
    {
        sum += c[x] ;
        x -= lowbit(x) ;
    }
    return sum ;
}
int cmp(node asdf, node b)
{
    return asdf.r < b.r;
}
int main()
{
    scanf("%d" , &n) ;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d" , &col[i]) ;
        pre[i] = last[col[i]] ;
        last[col[i]] = i ;
    }
    int m ;
    scanf("%d" , &m) ;
    for(int i = 1 ; i <= m ;i++)
    {
        scanf("%d%d" , &a[i].l , &a[i].r) ;
        a[i].id = i ;
    }
    sort(a + 1 , a + 1 + m , cmp) ;
    int now = 0 ;
    for(int i = 1 ; i <= m ; i++)
    {
        while(now < a[i].r)
        {
            now ++ ;
            update(pre[now] + 1 , 1) ;
            if(now != n){update(now + 1 ,-1) ;}
        }
        ans[a[i].id] = getsum(a[i].l) ;
    }
    for(int i = 1 ; i <= m ; i++)
    {
        printf("%d\n" , ans[i]) ;
    }
}