首页 > 代码库 > P1972 [SDOI2009]HH的项链
P1972 [SDOI2009]HH的项链
题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入样例#1：
61 2 3 4 3 531 23 52 6
输出样例#1：
224
说明
数据范围：
对于100%的数据，N <= 50000，M <= 200000。
裸地莫队调了一个小时发现数组开小了。。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=2000001; 8 void read(int & n) 9 {10 char c=‘+‘;int x=0;bool flag=0;11 while(c<‘0‘||c>‘9‘)12 {c=getchar();if(c==‘-‘)flag=1;}13 while(c>=‘0‘&&c<=‘9‘)14 {x=x*10+(c-48),c=getchar();}15 flag==1?n=-x:n=x;16 }17 int n,m,kuai,x,y,ans=0;18 int a[MAXN],pos[MAXN],out[MAXN],happen[MAXN];19 struct node20 {21 int x,y,id;22 }q[MAXN];23 int comp(const node & a,const node & b)24 {25 if(pos[a.x]==pos[b.x])26 return a.y<b.y;27 else return pos[a.x]<pos[b.x];28 }29 void add(int p)30 {31 happen[a[p]]++;32 if(happen[a[p]]==1)33 ans++;34 }35 void dele(int p)36 {37 happen[a[p]]--;38 if(happen[a[p]]==0)39 ans--;40 }41 void modui()42 {43 int l=2,r=1;44 for(int i=1;i<=m;i++)45 {46 for(;l<q[i].x;++l)47 dele(l);48 for(;l>q[i].x;--l)49 add(l-1);50 for(;r<q[i].y;++r)51 add(r+1);52 for(;r>q[i].y;--r)53 dele(r);54 out[q[i].id]=ans;55 }56 for(int i=1;i<=m;i++)57 {58 printf("%d\n",out[i]);59 }60 }61 int main()62 {63 //freopen("diff.in","r",stdin);64 //freopen("diff.out","w",stdout);65 read(n);66 for(int i=1;i<=n;i++)67 read(a[i]);68 kuai=sqrt(n);69 for(int i=1;i<=n;i++)70 pos[i]=(i-1)/kuai+1;71 read(m);72 for(int i=1;i<=m;i++)73 {read(q[i].x);read(q[i].y);q[i].id=i;}74 sort(q+1,q+m+1,comp);75 modui();76 return 0;}77 /*int comp(const Q & a ,const Q & b)78 {79 if(pos[a.l]==pos[b.l])80 return a.r<b.r;81 else return pos[a.l]<pos[b.l];82 }*/
P1972 [SDOI2009]HH的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。