[BZOJ3585][BZOJ3339]mex
2024-09-02 06:34:17
[BZOJ3585][BZOJ3339]mex
试题描述
有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。
输入
第一行n,m。
第二行为n个数。
从第三行开始,每行一个询问l,r。
输出
一行一个数,表示每个询问的答案。
输入示例
输出示例
数据规模及约定
对于100%的数据:
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
题解
首先离线,将询问按右端点排序。然后我们就可以从左到右一个个添加序列中的数了。现在我们可以认为右端点固定为 R 了,考虑一个数 i,我们只关心左边离它最近的位置,不妨称为 lstp[i],那么 mex{ A[L..R] } = k 等价于 min{ lstp[0..k-1] } ≥ L,即小于 k 的数上一次出现的位置在 L 及之后,即 [L, R] 中包含了所有 0 到 k-1 中的数字。这样,我们维护一个权值线段树,支持点修改,在查询时可以直接在线段树上二分。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 200010
#define maxnode 6000010
#define maxv 1000000000 int n, q, A[maxn], num[maxn]; struct Que {
int l, r, id;
Que() {}
Que(int _1, int _2, int _3): l(_1), r(_2), id(_3) {}
bool operator < (const Que& t) const { return r < t.r; }
} qs[maxn]; int ToT, mnv[maxnode], lc[maxnode], rc[maxnode], rt;
void update(int& o, int l, int r, int val, int npos) {
if(!o) o = ++ToT;
if(l == r) mnv[o] = npos;
else {
int mid = l + r >> 1;
if(val <= mid) update(lc[o], l, mid, val, npos);
else update(rc[o], mid + 1, r, val, npos);
mnv[o] = min(mnv[lc[o]], mnv[rc[o]]);
}
return ;
}
int query(int lim) {
int l = 0, r = maxv, o = rt;
while(l < r) {
if(!o) return l;
int mid = l + r >> 1;
if((lc[o] ? mnv[lc[o]] : 0) >= lim) l = mid + 1, o = rc[o];
else r = mid, o = lc[o];
}
return l;
} int Ans[maxn]; int main() {
n = read(); q = read();
for(int i = 1; i <= n; i++) A[i] = read();
for(int i = 1; i <= q; i++) {
int l = read(), r = read();
qs[i] = Que(l, r, i);
} sort(num + 1, num + n + 1);
sort(qs + 1, qs + q + 1);
for(int i = 1, j = 1; i <= q; i++) {
while(j <= qs[i].r) update(rt, 0, maxv, A[j], j), j++;
Ans[qs[i].id] = query(qs[i].l);
} for(int i = 1; i <= q; i++) printf("%d\n", Ans[i]); return 0;
}
最新文章
- CI Weekly #8 | CI/CD 技能进阶路线
- # 20145334赵文豪 《Java程序设计》第7周学习总结
- Python 迭代dict 效率
- Wormholes(Bellman-ford)
- servlet--页面自刷新
- PS之火焰铁锈字
- 一封给&ldquo;X教授&rdquo;的回信(讨论Socket通信)
- Oracle RAC中的投票算法
- 一段JAVA签名算法的PHP改写
- 201521123017 《Java程序设计》第13周学习总结
- LeetCode Javascript实现 344. Reverse String 292. Nim Game 371. Sum of Two Integers
- SpringBoot进阶教程(二十四)整合Redis
- 恢复oracle中误删除drop掉的表 闪回的方法
- 【斐波那契数列】java探究
- C# 在Word中添加表格的方法
- python基础-小练习
- C语言学习及应用笔记之四:C语言volatile关键字及其使用
- C#大型电商项目优化(二)——嫌弃EF与抛弃EF
- AssemblyVersion,AssemblyFileVersion解释以及获取
- log.debug(e.getMessage());
热门文章
- Ubuntu18.04如何从英文界面更改为中文界面
- mysql中的空值问题
- 谈谈TCP的四次挥手
- java基础—java读取properties文件
- java中插入myslq的datetime类型的
- 解决升级mac os X EI Capitan后遇到LibclangError: dlopen(libclang.dylib, 6): image not found.的问题
- vscode的eslint插件不起作用
- 洛谷 P2568 GCD
- [bzoj]3436 小K的农场
- 【线段树分治 01背包】loj#6515. 「雅礼集训 2018 Day10」贪玩蓝月