前者:https://www.lydsy.com/JudgeOnline/problem.php?id=3339

后者:

https://www.lydsy.com/JudgeOnline/problem.php?id=3585

https://www.luogu.org/problemnew/show/P4137

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

题解大部分都是莫队分块,但是复杂度为O(n*sqrt(n))=5e2*2e5=1e8摸着良心说能过吗?

(莫队都是n=1e5的……然而慢点评测机也过不去,可能需要更小。)

参考:网上貌似就三篇的数据结构做法。

考虑数据结构吧,选择权值建主席树,每个节点记录当前区间的值在序列中出现位置的最小值。

这样查询的时候可以在r这棵树上找节点小于l的就行啦。

(如果小于,说明这段值域区间内有值不在序列区间内,否则全在,就需要考虑更大值。)

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=4e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int l,r,min;
}tr[N*];
int rt[N],pool,n,m,q,b[N],a[N];
inline void LSH(){
sort(b+,b+m+);
m=unique(b+,b+m+)-b-;
for(int i=;i<=n;i++)
a[i]=lower_bound(b+,b+m+,a[i])-b;
}
void insert(int y,int &x,int l,int r,int p,int v){
tr[x=++pool]=tr[y];
if(l==r){
tr[x].min=v;
return;
}
int mid=(l+r)>>;
if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,v);
else insert(tr[y].r,tr[x].r,mid+,r,p,v);
tr[x].min=min(tr[tr[x].l].min,tr[tr[x].r].min);
}
int query(int x,int l,int r,int v){
if(l==r)return l;
int mid=(l+r)>>;
if(tr[tr[x].l].min<v)return query(tr[x].l,l,mid,v);
else return query(tr[x].r,mid+,r,v);
}
int main(){
n=read(),q=read();
b[++m]=;
for(int i=;i<=n;i++){
a[i]=b[++m]=read();
b[++m]=a[i]+;
}
LSH();
for(int i=;i<=n;i++)insert(rt[i-],rt[i],,m,a[i],i);
for(int i=;i<=q;i++){
int l=read(),r=read();
printf("%d\n",b[query(rt[r],,m,l)]);
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

最新文章

  1. 如何利用BI实现人力资源可视化管理
  2. js实现页面局部弹窗打印
  3. CSS导航的魔力——源自温谦老师《CSS彻底研究设计》
  4. Entity Framework搜索指定字段解决方案
  5. 谷歌(Chrome)浏览器调试JavaScript小技巧
  6. linux常见问题集锦
  7. hibernate.cfg.xml讲解
  8. 【转】 iOS开发数据库篇—SQLite简单介绍
  9. 高速排序-c++(分别用数组和容器实现)
  10. Java中遍历Map对象的方法
  11. UICollection无法下拉刷新的问题
  12. java易混淆知识小结
  13. [Swift]LeetCode318. 最大单词长度乘积 | Maximum Product of Word Lengths
  14. spring boot 的maven设置阿里云仓库
  15. BJWC2018上学路线
  16. arp绑定IP
  17. Derek解读Bytom源码-孤块管理
  18. codeforces982A
  19. IntelliJ IDEA快捷键:F12
  20. 如何通过Fiddler模拟弱网进行测试

热门文章

  1. C#调用大漠插件,发送QQ和微信消息
  2. 引领技术变革,腾讯云、腾讯WeTest和英特尔,合作布局云游戏
  3. 在Android上运用Anko和Kotlin开发数据库:SQLite从来不是一件轻松的事(KAD25)
  4. mysql bin log配置及查看
  5. 【Random】-随机数字-jmeter
  6. 深入理解eos账户体系 active和action
  7. [C++] OOP - Base and Derived Classes
  8. 嵌入式码农的10年Bug调试经验,值得一看
  9. Daily Scrum 9
  10. 深入理解Java对象序列化(转载)