BZOJ3585: mex(主席树)

Description

  有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。

Input

  第一行n,m。   第二行为n个数。   从第三行开始,每行一个询问l,r。

Output

  一行一个数,表示每个询问的答案。

Sample Input

5 5 2 1 0 2 1 3 3 2 3 2 4 1 2 3 5

Sample Output

1 2 3 0 3

HINT

数据规模和约定   对于100%的数据:   1<=n,m<=200000   0<=ai<=109   1<=l<=r<=n

  对于30%的数据:

  1<=n,m<=1000

Source

考场上写的cc_hash_table+莫队,成功水到70分233

正解是权值线段树

让线段树中下标为$i$的位置表示权值为$i$的数最后一次出现的位置

同时维护一下区间最小值

再可持久化一下

询问的时候直接在第$r$棵树中找到一个最小的位置,满足这个下标出现的位置$<=l$

#include<cstdio>
#include<algorithm>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
using namespace std;
const int MAXN=4*1e6+10,INF=1e9+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int mn,ls,rs;
}T[MAXN];
int root[MAXN],tot=0;
void update(int k){T[k].mn=min(T[T[k].ls].mn,T[T[k].rs].mn);}
void Insert(int &k,int pre,int l,int r,int pos,int val)
{
    if(!k) k=++tot;
    if(l==r){T[k].mn=val;return ;}
    int mid=l+r>>1;
    if(pos<=mid) T[k].rs=T[pre].rs,Insert(T[k].ls,T[pre].ls,l,mid,pos,val);
    else         T[k].ls=T[pre].ls,Insert(T[k].rs,T[pre].rs,mid+1,r,pos,val);
    update(k);
}
int Query(int k,int l,int r,int val)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(T[T[k].ls].mn<val) return Query(T[k].ls,l,mid,val);
    else                      return Query(T[k].rs,mid+1,r,val);
}
int main()
{
    freopen("a.in","r",stdin);
    int N=read(),M=read();
    for(int i=1;i<=N;i++)
    {
        int val=read();
        Insert(root[i],root[i-1],0,N,val>N?N:val,i);
    }
    for(int i=1;i<=M;i++)
    {
        int l=read(),r=read();
        printf("%d\n",Query(root[r],0,N,l));
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的技术专栏

Java锁机制(一)synchronized

18340
来自专栏Phoenix的Android之旅

动态代理-进阶高级开发必学技能

关于代理模式的话题有很多, 在开发中经常用到的应该是静态代理模式,能很好的去耦合。 动态代理是代理模式的另外一种实现。

9330
来自专栏進无尽的文章

基础篇-ObjectC继承、类别、属性

    在实际的开发过程中,继承和类别都会得到很多用处。对于界面相似度很高的情况下,使用继承可以节省很多代码和设置,只需要在子类中重写父类中的方法,或者增加新的...

8310
来自专栏闪电gogogo的专栏

Python——正则表达式

此篇文章结合小甲鱼的笔记和视频整理。 1 编译 Python 通过 re 模块为正则表达式引擎提供一个接口,同时允许你将正则表达式编译成模式对象,并用它们来进行...

289100
来自专栏Create Sun

python 3.x 爬虫基础---正则表达式(案例:爬取猫眼信息,写入txt,csv,下载图片)

  正则表达式是对字符串的一种逻辑公式,用事先定义好的一些特定字符、及这些特定字符的组合,组成一个“规则的字符串”,此字符串用来表示对字符串的一种“过滤”逻辑。...

53840
来自专栏用户2442861的专栏

JAVA反射机制作用是什么

Java的反射机制是Java特性之一,反射机制是构建框架技术的基础所在。灵活掌握Java反射机制,对大家以后学习框架技术有很大的帮助。

1.6K20
来自专栏小勇DW3

redis中各种数据类型的常用操作方法汇总

string是redis最基本的类型,你可以理解成与Memcached一模一样的类型,一个key对应一个value。 string类型是二进制安全的。意思是re...

17630
来自专栏用户2442861的专栏

Java内存管理(一、内存分配)

关于Java内存分配,很多问题都模模糊糊,不能全面贯通理解。今查阅资料,欲求深入挖掘,彻底理清java内存分配脉络,只因水平有限,没达到预期效果,仅以此文对所...

1K30
来自专栏编程

python的函数(二):作用域

我们在写函数时,时常需要引用全局的变量,或对全局变量赋值。又或者偶尔遇到局部变量与全局变量同名。在处理这些问题时,python语言的游戏规则是怎样的?今天我们就...

20050
来自专栏游戏开发那些事

【小白学C#】浅谈.NET中的IL代码

  前几天群里有位水友提问:”C#中,当一个方法所传入的参数是一个静态字段的时候,程序是直接到静态字段拿数据还是从复制的函数栈中拿数据“。其实很明显,这和方法参...

22520

扫码关注云+社区

领取腾讯云代金券