HH的项链(树状数组)区间内不同的数量

2023-12-28 07:38

本文主要是介绍HH的项链(树状数组)区间内不同的数量,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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
3
1 2 
3 5
2 6
Sample Output
2
2
4
Hint


题意:

有一串项链,每点有个颜色,给你个区间。查询这个区间内有几种不同的颜色?

思路:

预处理出上一个与i颜色相同的点pre[i],将询问按右端点排序,然后一边往树状数组进入点一边处理询,注意其中一些小技巧。

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,sum;
const int maxn=1000010;
int pre[maxn],s[maxn],p[maxn],head[maxn],ans[maxn];
struct Q
{int l,r,id;
}q[maxn];
bool cmp(Q a,Q b)
{return a.r<b.r;
}
int lowbit(int i){return i&-i;
}
void updata(int x,int v)   //单点更新
{if(!x)  return ;sum+=v;                //记录的更新的次数//  cout<<sum<<"......"<<endl;while(x<=n){s[x]+=v;x+=lowbit(x);
}}
int query(int x) //查询0-x和
{int i,res=0;while(x>0){res+=s[x];x-=lowbit(x);
}return res;
}
int main()
{scanf("%d",&n);int i,j;for(i=1;i<=n;i++){scanf("%d",&p[i]);pre[i]=head[p[i]];  //仔细理解head[p[i]]=i;}scanf("%d",&m);for(i=1;i<=m;i++)    scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+m+1,cmp);for(i=j=1;i<=m;i++){for(;j<=q[i].r;j++) updata(pre[j],-1),updata(j,1);  //核心处ans[q[i].id]=sum-query(q[i].l-1);}for(i=1;i<=m;i++)    printf("%d\n",ans[i]);return 0;
}

多看 多学 多想

这篇关于HH的项链(树状数组)区间内不同的数量的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术(如Docker)、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术(如 docker)1. 创

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

java中不同版本JSONObject区别小结

《java中不同版本JSONObject区别小结》本文主要介绍了java中不同版本JSONObject区别小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1. FastjsON2. Jackson3. Gson4. org.json6. 总结在Jav