bzoj 1878: [SDOI2009]HH的项链

秒速五厘米 2022-05-15 23:59 180阅读 0赞

传送门：[点我][Link 1]  
Description  
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一  
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一  
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只  
好求助睿智的你，来解决这个问题。  
Input  
第一行：一个整数N，表示项链的长度。  
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。  
第三行：一个整数M，表示HH询问的个数。  
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。  
N ≤ 50000，M ≤ 200000。  
Output  
M行，每行一个整数，依次表示询问对应的答案。

Sample Input  
6

1 2 3 4 3 5

1 2

3 5

2 6

Sample Output  
2

莫队

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    #include<cstring>
    #define go(i,a,b) for(int i=a;i<=b;i++)
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    const int M=200003;
    const int N=500003;
    struct Mo {
    	int l,r,ID;
    } q[M];
    int n,m,col[N],unit,Be[N];
    int cnt[1000000+10],tot;
    int ans[M];
    bool cmp(Mo a,Mo b) {
    	return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;
    }
    inline void revise(int x,int add){
         if(add==-1){
         	cnt[col[x]]+=add;
         	if(!cnt[col[x]]){ //如果该数的个数已经变为了0，计数减少一个 
         		tot--;
    		 }
    	 }
    	 else{
    	 	if(!cnt[col[x]]){//如果该数尚未开始计数，计数增加一个 
    	 		tot++;
    		 }
    		 cnt[col[x]]+=add;
    	 }
    	
    }
    int main() {
    	scanf("%d",&n);
    	unit=sqrt(n);//分块 ,每一块的大小是unit 
    	go(i,1,n)scanf("%d",&col[i]),Be[i]=i/unit+1;
    	scanf("%d",&m);
    	go(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].ID=i;//询问请求的id 
    
    	sort(q+1,q+m+1,cmp);
    
    	int l=1,r=0;
    	go(i,1,m) {
    		while(l<q[i].l)revise(l,-1),l++;
    		while(l>q[i].l)revise(l-1,1),l--;
    		while(r<q[i].r)revise(r+1,1),r++;
    		while(r>q[i].r)revise(r,-1),r--;
    		ans[q[i].ID]=tot;
    	}
    	go(i,1,m)printf("%d\n",ans[i]);
    	return 0;
    }

在落谷上面莫队算法最后两个点竟然被卡掉了，qwq,后来看 了别人的离线+树状数组的做法，但是wa了后面的三个点，自己也不知道为什么，来往的大佬望指教，

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int M=200003;
    const int N=500003;
    int c[N];
    int a[N];
    int vis[N],nex[N];
    int n,m;
    int ans[M];
    struct query{
    	int l,r;
    	int ind;
    }q[M];
    int cmp(query a,query b){
    	return a.l<b.l;
    }
    int lowbit(int x){
    	return x&(-x);
    }
    void add(int x,int num){
    	while(x<=n){
    		c[x]+=num;
    		x+=lowbit(x);
    	}
    }
    int getsum(int x){
    	int s=0;
    	while(x>0){
    		s+=c[x];
    		x-=lowbit(x);
    	}
    	return s;
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    	}
    	scanf("%d",&m);
    	for(int i=1;i<=m;i++){
    		scanf("%d%d",&q[i].l,&q[i].r);
    		q[i].ind=i;
    	}
    	for(int i=1;i<=n;i++){
    		if(!vis[a[i]]){
    			vis[a[i]]=1;
    			add(i,1);
    		}	
    	}
    	for(int i=1;i<=n;i++){
    		vis[a[i]]=0;
    	}
    	for(int i=n;i;--i){
    		if(!vis[a[i]]){
    			nex[i]=n+1;
    		}
    		else{
    			nex[i]=vis[a[i]];
    		}
    		vis[a[i]]=i;
    	}
    	sort(q+1,q+m+1,cmp);
    	int j=1;
        for(int i=1;i<=m;++i){
            for(;j<q[i].l;j++)add(nex[j],1);
            ans[q[i].ind]=getsum(q[i].r)-getsum(q[i].l-1);
        } 
    
    for(int i=1;i<=m;i++){
    		printf("%d\n",ans[i]);
    	}
    	return 0;
    }

后来又用了主席树， 不怎么会，所以直接套了一个板子，但是只过了前面三个点，其余的都是RE,  
呜呜呜，过往的大牛指点一二

#include<iostream>
    #include<cstdio>
    #include<map>
    using namespace std;
    const int maxn=500000+5;
    const int m=maxn*40;
    int n,q,tot;
    int a[maxn];
    int T[maxn],lson[m],rson[m],c[m];
    int build(int l,int r){
    	int root=tot++;
    	c[root]=0;
    	if(l!=r){
    		int mid=(r+l)>>1;
    		lson[root]=build(1,mid);
    		rson[root]=build(mid+1,r);
    		
    	}
    	return root;
    }
    int update(int root,int pos,int val){
    	int newroot=tot++,tmp=newroot;
    	c[newroot]=c[root]+val;
    	int l=1,r=n;
    	while(l<r){
    		int mid=(l+r)>>1;
    		if(pos<=mid){
    			lson[newroot]=tot++;rson[newroot]=rson[root];
    			newroot=lson[newroot];root=lson[root];
    			r=mid;
    			
    		}
    		else{
    			rson[newroot]=tot++;lson[newroot]=lson[root];
    			newroot=rson[newroot];root=rson[root];
    			l=mid+1;
    			
    		}
    		c[newroot]=c[root]+val;
    		
    	}
    	return tmp;
    	
    }
    int query(int root,int pos){
    	int ret=0;
    	int l=1,r=n;
    	while(pos<r){
    		int mid=(l+r)>>1;
    		if(pos<=mid){
    			r=mid;
    			root=lson[root];
    			
    		}
    		else{
    			ret+=c[lson[root]];
    			root=rson[root];
    			l=mid+1;
    			
    		}
    	}
    	return ret+c[root];
    	
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		tot=0;
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    			
    		}
    		T[n+1]=build(1,n);
    		map<int,int>mp;
    		for(int i=n;i>=1;i--){
    			if(mp.find(a[i])==mp.end()){
    				T[i]=update(T[i+1],i,1);
    			}
    			else{
    				int tmp=update(T[i+1],mp[a[i]],-1);
    				T[i]=update(tmp,i,1);
    				
    			}
    			mp[a[i]]=i;
    		}
    		scanf("%d",&q);
    		while(q--){
    			int l,r;
    			scanf("%d%d",&l,&r);
    			printf("%d\n",query(T[l],r));
    		}
    	}
    	return 0;
    }

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1878