首页 > 代码库 > bzoj3585 mex
bzoj3585 mex
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3585
【题解】
哎好像就是上题啊
怎么权值是1e9了啊
那没关系啊把主席树调成[0,1e9]的就行啦
哎调调空间
过了
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m; int rt[M]; namespace CMT { const int M = 1e7 + 10; int s[M], ch[M][2], siz; inline void change(int &x, int y, int l, int r, int pos, int va) { x = ++siz; ch[x][0] = ch[y][0]; ch[x][1] = ch[y][1]; if(l==r) { s[x] = va; return ; } int mid = l+r>>1; if(pos <= mid) change(ch[x][0], ch[y][0], l, mid, pos, va); else change(ch[x][1], ch[y][1], mid+1, r, pos, va); s[x] = min(s[ch[x][0]], s[ch[x][1]]); } inline int mex(int x, int l, int r, int pos) { if(l == r) return l; int mid = l+r>>1; if(s[ch[x][0]] >= pos) return mex(ch[x][1], mid+1, r, pos); else return mex(ch[x][0], l, mid, pos); } } int main() { scanf("%d%d", &n, &m); for (int i=1, t; i<=n; ++i) { scanf("%d", &t); CMT::change(rt[i], rt[i-1], 0, 1e9, t, i); } while(m--) { int x, y; scanf("%d%d", &x, &y); printf("%d\n", CMT::mex(rt[y], 0, 1e9, x)); } return 0; }
bzoj3585 mex
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。