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

题意：给一个n个数的序列，m个询问，每次询问一个区间内不相同的数的个数。方法：离线+树状数组解析：看完题后的确有段时间没有头绪，想过线段树来搞，不过好像很麻烦，然后听他们说离线下来搞。再推了1节课差不多就明白了。离线和在线差距的确很大。如果离线的话，所有的区间是呈线性的。大体思路是什么呢？就是每个数，我们都可以预处理出他上一次出现是在什么位置。然后对于一个区间的询问[l,r]，我们可以这么去想这个询问：l~r中的数的上一次出现的位置在l左边的数的个数。这样就很好弄了，先把所有的区间按右端点排序。每次添加元素的时候，将它上一次出现的位置+1的地方的值加1，，然后在其本身位置+1的值打上个-1标记，这样就成了线性求值，也就是每次求getsum(a[i].l)。;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]) ;}}

慢慢学会了长大。流转的时光，