求区间种类数——树状数组_求区间内有多少种不同的树-程序员宅基地

一提到求区间种类数….脑子里满是莫队啊啊啊怕不是没救了……..

题意很简单，就是求区间内有多少个不同的数

那怎么做呢qaq 树状数组诶！

把所有询问按右端点排序，然后每次加到这个点

树状数组按位置建哦
那么树状数组上每个点就记录第一个点到此点有多少个数，因为此时查询的右端点是一点定的，所有每个数都记他最后一次出现的位置，这样也可以保证不会重。
而且查询的时候，因为左端点不一定，所以答案是query(tmp)-query(x-1)。记录每个数最后一次出现的位置，会保证不会减重了，而不会减多了

是不是很妙啊！

来一发例题 bzoj1878

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 200020
int mx=0,n,m,b[N],ans[N],tree[N<<1],last[N],h[N<<1];
struct node{
   int x,y,num;}a[M];
bool cmp(node x,node y){
   return x.y<y.y || (x.y==y.y && x.x<y.x);}
void insert(int x,int y){
   for(;x<=n;x+=x&-x) tree[x]+=y;}
int query(int x){
    int y=0;for(;x;x-=x&-x) y+=tree[x];
    return y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]),last[i]=h[b[i]],h[b[i]]=i,mx=max(mx,b[i]);
    scanf("%d",&m);int q=sqrt(n);
    for(int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].num=i;
    sort(a+1,a+m+1,cmp);int tmp=0;
    for(int i=1;i<=m;i++){
        while(tmp<a[i].y){
            tmp++;if(last[tmp]) insert(last[tmp],-1);
            insert(tmp,1);
        }ans[a[i].num]=query(tmp)-query(a[i].x-1);
    }for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

本文链接：https://blog.csdn.net/sunshiness_s/article/details/80429470

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Syntax Error: Error: Node Sass version 6.0.1 is incompatible with ^4.0.0-程序员宅基地

文章浏览阅读1.2k次。Syntax Error: Error: Node Sass version 6.0.1 is incompatible with ^4.0.0，提示：Error: Rule can only have one resource source (provided resource and test + include + exclude)_syntax error: error: node sass version 6.0.1 is incompatible with ^4.0.0.

大数据框架之Hadoop：HDFS（六）DataNode（面试开发重点）-程序员宅基地

文章浏览阅读760次。DataNode（面试开发重点）_datanode

Python 基于 OpenCV 视觉图像处理实战之 OpenCV 简单人脸检测/识别实战案例之七简单进行人脸检测并添加面具特效实现

Python是一种跨平台的计算机程序设计语言。是一种面向对象的动态类型语言，最初被设计用于编写自动化脚本(shell)，随着版本的不断更新和语言新功能的添加，越多被用于独立的、大型项目的开发。Python是一种解释型脚本语言，可以应用于以下领域： Web 和 Internet开发、科学计算和统计、人工智能、教育、桌面界面开发、软件开发、后端开发、网络爬虫。这里使用 Python 基于 OpenCV 进行视觉图像处理，......

使用UmcFramework和unimrcpclient.xml连接多个SIP设置的配置指南及C代码示例

在多媒体通信领域，MRCP（Media Resource Control Protocol）协议被广泛用于控制语音识别和合成等媒体资源。UniMRCP是一个开源的MRCP实现，提供了客户端和服务端的库。UmcFramework是一个基于UniMRCP客户端库的示例应用程序框架，它帮助开发者快速集成和测试MRCP客户端功能。本文将详细介绍如何使用UmcFramework和unimrcpclient.xml配置文件连接到多个SIP设置，以及如何用C代码进行示例说明。

java.net.ProtocolException: Server redirected too many times (20)-程序员宅基地

文章浏览阅读3k次。报错：java.net.ProtocolException: Server redirected too many times (20)1.没有检查到cookie，一直循环重定向。解决：CookieHandler.setDefault(new CookieManager(null, CookiePolicy.ACCEPT_ALL));URL url = new URL(url); ..._java.net.protocolexception: server redirected too many times (20)

springboot启动报错 Failed to scan *****/derbyLocale_ja_JP.jar from classloader hierarchy_failed to scan from classloader hierarchy-程序员宅基地

文章浏览阅读4.1k次。问题这是部分报错信息2019-07-11 14:03:34.283 WARN [restartedMain][DirectJDKLog.java:175] - Failed to scan [file:/D:/repo/org/apache/derby/derby/10.14.2.0/derbyLocale_ja_JP.jar] from classloader hierarchyjava...._failed to scan from classloader hierarchy

随便推点

ZooKeeper实战之ZkClient客户端实现负载均衡_zookeeper实现负载均衡案例-程序员宅基地

文章浏览阅读1.9k次。声明：此博客为学习笔记，学习自极客学院ZooKeeper相关视频；非常感谢众多大牛们的知识分享。相关概念：负载均衡(相关节点)架构图：说明：每当往集群中新增一个工作服务器时，都会再/server节点下创建一个对应的临时节点，该节点中应含有该服务器的连接信息以及均衡标识等。当客户端需要连接worker server时，就会先读取/servers节点下的所..._zookeeper实现负载均衡案例

Android 枚举 VS 枚举注解_android 枚举注解-程序员宅基地

文章浏览阅读448次。枚举注解替换枚举java 虚拟机内存分配java 内存区域可分为方法区存放虚拟机加载的类信息，常量，静态变量等数据。虚拟机栈 java 方法执行的内存模型：每个方法在执行的时候创建的栈帧，包括存储局部变量表，操作数栈，动态链接，方法出口等信息。本地方法栈主要与Native相关堆存放对象实例。程序计数器当前线程执行的字节码行号指示器。java 数据类型占内存大小java 数据类型分为基本数据类型和引用数据类型。在32位系统上基本数据类型，本文中中的所有内存空间大小都在_android 枚举注解