【树状数组+离线】[SDOI2009]HH的项链

柔光的暖阳◎ 2024-03-23 16:45 66阅读 0赞

[1033-\[SDOI2009\]HH的项链\_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)][1033-_SDOI2009_HH_2021_ _nowcoder.com]

题意：

![955727e72b08433793524c87a3f31db3.png][]

思路：

每次询问输出该区间内不同的数的个数

相当于对于一个种类的数，只保留一个数

考虑保留位置最靠右边的那个

因此考虑将询问离线处理，将这些区间按右端点排序，然后用树状数组维护一个序列

什么样的序列呢

对于每个种类的数只保留其最右端的那个数的序列

因此我们在遍历询问的时候，如果一个数在之前有被访问过，就将前面那个数从1变成0，然后将该位置置1，这样询问区间内数字种类个数就可以转化成区间加了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define low(x) (x&(-x))
    
    using namespace std;
    
    const int mxn=1e6+10;
    
    struct Query{
    	int l,r,id;
    }Q[mxn];
    
    bool cmp(Query x,Query y){
    	return x.r<y.r;
    }
    
    int N,M,x,y;
    int tree[mxn];
    int a[mxn],vis[mxn],ans[mxn];
    
    void add(int x,int k){
    	for(int i=x;i<=N;i+=low(i)) tree[i]+=k;
    }
    int sum(int x){
    	int res=0;
    	for(int i=x;i;i-=low(i)) res+=tree[i];
    	return res;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	cin>>M;
    	for(int i=1;i<=M;i++){
    		cin>>x>>y;
    		Q[i]={x,y};
    		Q[i].id=i;
    	}
    	sort(Q+1,Q+1+M,cmp);
    	int last=1;
    	for(int i=1;i<=M;i++){
    		for(int j=last;j<=Q[i].r;j++){
    			if(vis[a[j]]){
    				add(vis[a[j]],-1);
    			}
    			add(j,1);
    			vis[a[j]]=j;
    		}
    		last=Q[i].r+1;
    		ans[Q[i].id]=sum(Q[i].r)-sum(Q[i].l-1);
    	}
    	for(int i=1;i<=M;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[1033-_SDOI2009_HH_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26896/1033
[955727e72b08433793524c87a3f31db3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9464b87a6e014bf59d1ab0f714ab7806.png