洛谷 P1972 [SDOI2009]HH的项链

2023-10-09 05:18
文章标签 洛谷 sdoi2009 hh 项链 p1972

本文主要是介绍洛谷 P1972 [SDOI2009]HH的项链,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。
输入输出格式
输入格式:

第一行:一个整数N,表示项链的长度。
第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。
第三行:一个整数M,表示HH 询问的个数。
接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式:

M 行,每行一个整数,依次表示询问对应的答案。

输入输出样例
输入样例#1:
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出样例#1:
2
2
4
说明
数据范围:
对于100%的数据,N <= 50000,M <= 200000。


运用莫队算法。
算法核心:离线,将询问重新排序,将复杂度降低到O(x*sqrt(x)。


#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,t,res,a[50005],ans[200005],sum[200005];
struct que
{int l,r,num;
}ask[200005];
bool cmp1(que c,que d)
{return c.l<d.l;
}
bool cmp2(que c,que d)
{if(c.r==d.r)return c.l<d.l;return c.r<d.r;
}
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",&ask[i].l,&ask[i].r);ask[i].num=i;}sort(ask+1,ask+m+1,cmp1);//按左端点排序 t=sqrt(n);//每块大小为t int x=1,y=0,z;while(x<=m){y++;//第y块 z=x;while(ask[x].l<=t*y&&x<=m)x++;//统计第y个块中有哪些询问 sort(ask+z,ask+x,cmp2);if(y==t)break;}int ll=1,rr=0;for(int i=1;i<=m;i++)//暴力扫 {if(ask[i].l<ll)for(int j=ask[i].l;j<ll;j++){if(!sum[a[j]])res++;sum[a[j]]++;}elsefor(int j=ll;j<ask[i].l;j++){sum[a[j]]--;if(!sum[a[j]])res--;}ll=ask[i].l;if(ask[i].r>rr)for(int j=rr+1;j<=ask[i].r;j++){if(!sum[a[j]])res++;sum[a[j]]++;}elsefor(int j=ask[i].r+1;j<=rr;j++){sum[a[j]]--;if(!sum[a[j]])res--;}rr=ask[i].r;ans[ask[i].num]=res;}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}

这篇关于洛谷 P1972 [SDOI2009]HH的项链的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/170609

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

【COGS】421 [SDOI2009] HH的项链 树状数组

传送门:【COGS】421 [SDOI2009] HH的项链 题目分析:将区间以右端点为关键字降序排序,然后从左到右依次遍历每个数并插入到树状数组中,如果遍历到一个数的时候在他的前面已经有一个相同的数时,将之前位置上的数从树状数组中删除。然后我们每处理完一个位置上的数后,看这个位置上是否有右端点,如果有则做一次求和,这个右端点属于的区间【L,R】的值即sum(R)-sum(L-1)。

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

【hh大神的】Tarjan + 缩点 模板

此模板来自 notonlysuccess 原文链接: http://www.notonlysuccess.com/index.php/tarjan/ 大神就是吊啊。 不多说了,想学tarjan ,资料网上是有一堆的 怎么说。。我现在理解的还不算太透彻,但用模板总行吧 这里只存一下模板 使用时注意清空和存图! (基于个人习惯,稍微有些小改动) #define

洛谷刷题(7)

P8738 [蓝桥杯 2020 国 C] 天干地支 题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊 (wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。 地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、

C++ 洛谷 哈希表(对应题库:哈希,hash)习题集及代码

马上就开学了,又一个卷季,不写点东西怎么行呢?辣么,我不准备写那些dalao们都懂得,熟练的,想来想去,最终还是写哈希表吧!提供讲解&题目&代码解析哦! 奉上题目链接: 洛谷题目 - 哈希,hash 1、哈希、哈希表(hash)简介 哈希(Hash)是一种将任意长度的输入映射为固定长度输出的算法。哈希函数的输出值称为哈希值或散列值。哈希函数具有以下特性: 确定性:对于相同的输入

洛谷p2236彩票题解

题目描述 某地发行一套彩票。彩票上写有 1 到 M 这 M 个自然数。彩民可以在这 M 个数中任意选取 N 个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。 每次抽奖将抽出两个自然数 X 和 Y。如果某人拿到的彩票上,所选 N 个自然数的倒数和,恰好等于 X/Y,则他将获得一个纪念品。 已知抽奖结果 X 和 Y。现在的问题是,必须准备多少纪念品,才能保证支付所有获奖者的