首页 > 代码库 > bzoj1878
bzoj1878
1878: [SDOI2009]HH的项链
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 3719 Solved: 1848
[Submit][Status][Discuss]
Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步
完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此,
他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同
的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解
决这个问题。
Input
第一行:一个整数N,表示项链的长度。
第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。
第三行:一个整数M,表示HH询问的个数。
接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
Output
M行,每行一个整数,依次表示询问对应的答案。
Sample Input
6
1 2 3 4 3 5
3
1 2
3 5
2 6
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
2
4
2
4
HINT
对于20%的数据,N ≤ 100,M ≤ 1000;
对于40%的数据,N ≤ 3000,M ≤ 200000;
对于100%的数据,N ≤ 50000,M ≤ 200000。
naive的莫队
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define N 1000010 struct data { int l,r,block,id; }q[N]; int n,m,tot; int a[N],ans[N],num[N]; bool cp(data x,data y) { if(x.block!=y.block) return x.block<y.block; return x.r<y.r; } void add(int pos) { if(num[a[pos]]==0) tot++; num[a[pos]]++; } void deltete(int pos) { num[a[pos]]--; if(!num[a[pos]]) tot--; } void solve() { sort(q+1,q+m+1,cp); int l=1,r=1; tot=1; num[a[1]]=1; for(int i=1;i<=m;i++) { while(l<q[i].l) { deltete(l); l++; } while(l>q[i].l) { l--; add(l); } while(r<q[i].r) { r++; add(r); } while(r>q[i].r) { deltete(r); r--; } ans[q[i].id]=tot; } for(int i=1;i<=m;i++) { printf("%d\n",ans[i]); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); int block=(int)(sqrt(n)); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].block=(q[i].l-1)/block; q[i].id=i; } solve(); return 0; }
bzoj1878
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。