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