首页 > 代码库 > [SDOI2009]HH的项链
[SDOI2009]HH的项链
https://www.luogu.org/problem/show?pid=1972
题目描述
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。
莫队
#include<cmath>#include<cstdio>#include<algorithm>using namespace std;#define N 50001#define M 200001#define K 1000001int n,m,siz,tmp;int key[N],sum[K],bl[N];int ans[M];struct node{ int l,r,id; bool operator < (node p)const { if(bl[l]!=bl[p.l]) return bl[l]<bl[p.l]; return r<p.r; } }e[M];inline void update(int pos,bool w){ if(w) tmp+=(++sum[key[pos]]==1); else tmp-=(!--sum[key[pos]]);}int main(){ scanf("%d",&n); siz=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i-1)/siz+1; for(int i=1;i<=n;i++) scanf("%d",&key[i]); scanf("%d",&m); int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); e[i].l=u; e[i].r=v; e[i].id=i; } sort(e+1,e+m+1); int L=1,R=0; for(int i=1;i<=m;i++) { while(L>e[i].l) update(--L,true); while(L<e[i].l) update(L++,false); while(R>e[i].r) update(R--,false); while(R<e[i].r) update(++R,true); ans[e[i].id]=tmp; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}
[SDOI2009]HH的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。