维护后面的position + 离线 + 线段树 bzoj 3585
2024-09-03 23:31:10
3585: mex
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 918 Solved: 481
[Submit][Status][Discuss]
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
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
2
3
0
3
HINT
数据规模和约定
对于100%的数据:
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据:
1<=n,m<=1000
Source
http://www.lydsy.com/JudgeOnline/problem.php?id=3585
思路:
其实这题的思路和bzoj 3339完全就一样啊,连离散化都不需要。->我的bzoj3339:http://www.cnblogs.com/heimao5027/p/6668367.html
因为对于n个数字,他的mex一定是<=n的,所以就算a[i]=1e9,那么我们就不要放到mex函数里面就好了,然后直接令next[i]=n+1即可,并不需要离散化
于是就这么简单的修改一下3339的代码,一下子就又过了= =
//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
vector<pair<int, int> > ve[maxn];
int tree[maxn << ], lazy[maxn << ];
int n, q;
int a[maxn], mex[maxn];
bool vis[maxn];
int nxt[maxn], pos[maxn]; void build_tree(int l, int r, int o){
lazy[o] = -;
if (l == r){
tree[o] = mex[l]; return ;
}
int mid = (l + r) / ;
build_tree(l, mid, o << );
build_tree(mid + , r, o << | );
tree[o] = min(tree[o << ], tree[o << | ]);
} void push_down(int o){
int lb = o << , rb = o << | ;
if (lazy[lb] == - || lazy[lb] > lazy[o]){
lazy[lb] = lazy[o];
tree[lb] = min(tree[lb], lazy[lb]);
}
if (lazy[rb] == - || lazy[rb] > lazy[o]){
lazy[rb] = lazy[o];
tree[rb] = min(tree[rb], lazy[rb]);
}
tree[o] = -;
} int query(int x, int l, int r, int o){
if (x == l && x == r){
return tree[o];
}
if (lazy[o] != -) push_down(o);
int mid = (l + r) / ;
if (x <= mid) return query(x, l, mid, o << );
if (x > mid) return query(x, mid + , r, o << | );
} void update(int ql, int qr, int l, int r, int o, int val){
if (ql <= l && qr >= r){
if (lazy[o] == -) lazy[o] = val;
lazy[o] = min(lazy[o], val);
tree[o] = min(lazy[o], tree[o]);
return ;
}
if (lazy[o] != -)push_down(o);
int mid = (l + r) / ;
if (ql <= mid) update(ql, qr, l, mid, o << , val);
if (qr > mid) update(ql, qr, mid + , r, o << | , val);
tree[o] = min(tree[o << ], tree[o << | ]);
}
int ans[maxn];
void solve(){
build_tree(, n, );
for (int i = ; i <= n; i++){
for (int j = ; j < ve[i].size(); j++){
int pos = ve[i][j].fi, id = ve[i][j].se;
ans[id] = query(pos, , n, );
}
int lb = i + , rb = nxt[i] - ;
if (lb <= rb) update(lb, rb, , n, , a[i]);
}
for (int i = ; i <= q; i++){
printf("%d\n", ans[i]);
}
} int main(){
cin >> n >> q;
for (int i = ; i <= n; i++) {
scanf("%d", a + i);
if (a[i] <= n + ) vis[a[i]] = true;
mex[i] = mex[i - ];
while (vis[mex[i]]) mex[i]++;
pos[i] = n + ;
}
for (int i = ; i <= n; i++) pos[i] = n + ;
for (int i = n; i >= ; i--){
if (a[i] >= n + ){
nxt[i] = n + ; continue;
}
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
for (int i = ; i <= q; i++){
int l, r; scanf("%d%d", &l, &r);
ve[l].pb(mk(r, i));
}
solve();
return ;
}
最新文章
- charing animation
- MVC中使用js拼接的元素验证问题
- Google Authentication 机制原理
- 浅尝辄止——使用ActiveX装载WPF控件
- OO基本原则
- poj 2063 Investmen 完全背包
- ASP.NET简单验证码
- python杂记-3(购买商品)
- jQuery中的选择器<;思维导图>;
- TSS 任务状态段
- 2014年Facebook的开源成就
- mariaDB安装完成后设置root密码等初始化操作
- [Python] python3 文件操作:从键盘输入、打开关闭文件、读取写入文件、重命名与删除文件等
- Linux - 在Ubuntu下永久修改主机名
- C语言博客作业05——指针
- p76泛函 有限维空间真子空间不可能在全空间稠密
- jquery源码中noConflict(防止$和jQuery的命名冲突)的实现原理
- Intellij-配置JDK版本和编译版本
- Linux&#160;Linux内核参数调优
- python 字符串中‘r’前缀