给一个长为n的自然数序列{a}和m个询问, 求区间mex (未出现的最小自然数). (1≤n,m≤2*10^5, 0≤ai≤10^9) 这是一道做法很多的题. 可以离线, 可以在线, 可以带根号, 也可以不带根号. # 离线: 莫队算法 想练习莫队, 找到本题. 一开始我的想法是这样的: 离散化. 用set维护一下没出现的自然数. 于是, 立刻得到一种
瞥了一眼Po姐的题解, 发现修改能做到
时间复杂度
其实并不需要离散化. 长度为n的序列的mex至多为n, 因为mex为k要求0~k-1都出现在序列中.
看到有人用莫队+树状数组+二分通过了本题, 于是实现了一下既带根号又带log的做法. 卡着时限过, bzoj倒数第一 (由于之前的提交没能留名233).
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
const int N = 2e5, M = 2e5, SQRT_N = 448;
int n, b[N], sz = 1, blk;
struct Block {
bool S[N];
int cnt[N], tot[SQRT_N];
void add(int v, int d)
{
if (v >= n) return;
cnt[v] += d;
if ((bool)cnt[v] ^ S[v]) {
S[v] ^= 1;
tot[b[v]] += d;
}
}
int query()
{
Rep (i, 0, blk) {
int s = min(sz, n-i*sz);
if (tot[i] != s) {
int j = i*sz;
while (S[j]) ++j;
return j;
}
}
return n;
}
} B;
struct Query {
int l, r, ans;
} Q[M];
int o[M];
bool cmp(int i, int j)
{
const Query& p = Q[i], & q = Q[j];
return b[p.l] < b[q.l] || (b[p.l] == b[q.l] && p.r < q.r);
}
void init()
{
int k = 0;
while (sz * sz < n) ++sz;
blk = (n+sz-1)/sz;
for (int i = 0; k < n; ++i)
Rep (j, 0, min(sz, n-k))
b[k++] = i;
}
int A[N];
int main()
{
int m;
scanf("%d%d", &n, &m);
init();
Rep (i, 0, n)
scanf("%d", &A[i]);
Rep (i, 0, m) {
scanf("%d%d", &Q[i].l, &Q[i].r);
--Q[i].l;
--Q[i].r;
o[i] = i;
}
sort(o, o+m, cmp);
int l = Q[0].l, r = l - 1;
Rep (i, 0, m) {
Query& q = Q[o[i]];
while (r < q.r)
B.add(A[++r], 1);
while (r > q.r)
B.add(A[r--], -1);
while (l < q.l)
B.add(A[l++], -1);
while (l > q.l)
B.add(A[--l], 1);
q.ans = B.query();
}
Rep (i, 0, m)
printf("%d\n", Q[i].ans);
return 0;
}#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
const int N = 2e5, M = 2e5;
int n, A[N], cnt[N], b[N], ans[M];
set<int> S;
struct Query {
int l, r, k;
bool operator<(const Query& rhs) const
{
return b[l] < b[rhs.l] || (b[l] == b[rhs.l] && r < rhs.r);
}
} Q[M];
void init()
{
int sz = 1;
while (sz * sz < n) ++sz;
for (int i = 0, k = 0; k < n; ++i)
Rep (j, 0, min(sz, n-k))
b[k++] = i;
}
inline void add(int v)
{
if (v >= n) return;
if (!cnt[v]) S.erase(v);
++cnt[v];
}
inline void remove(int v)
{
if (v >= n) return;
--cnt[v];
if (!cnt[v]) S.insert(v);
}
int main()
{
int m;
scanf("%d%d", &n, &m);
init();
Rep (i, 0, n)
scanf("%d", &A[i]);
Rep (i, 0, m) {
scanf("%d%d", &Q[i].l, &Q[i].r);
--Q[i].l;
--Q[i].r;
Q[i].k = i;
}
sort(Q, Q+m);
int l = Q[0].l, r = l - 1;
Rep (i, 0, n)
S.insert(i);
Rep (i, 0, m) {
while (r < Q[i].r)
add(A[++r]);
while (r > Q[i].r)
remove(A[r--]);
while (l < Q[i].l)
remove(A[l++]);
while (l > Q[i].l)
add(A[--l]);
ans[Q[i].k] = *S.begin();
}
Rep (i, 0, m)
printf("%d\n", ans[i]);
return 0;
}离线: 线段树
把询问按左端点排序, 维护M[i]: mex {A[l..i]}.
考虑去掉A[l], 对M数组产生什么影响. 设next[i]为下一个和A[i]相同的数的位置. 对i≥next[l], M[i]不变. 对l≤i<next[l], 它们原来含A[l], 现在不含A[l], M[i]可能会变小: 与A[l]取min, 即为新的mex. 由于只有单点查询, 这里的区间最值操作打个标记就好.
加上A[l]对M数组的影响似乎不是很好考虑. 大概是因为mex的定义 - "没出现的".
在线: 可持久化线段树
黄学长说这题在线不大好搞, 但是发现了一个用可持久化线段树的在线算法: [bzoj3585]mex - 不来也不去的一只失忆蝴蝶 - 博客频道 - CSDN.NET
如果能对每个区间建一棵权值线段树就好了. 但这里需要知道的是存在与否, 而非有多少个, 不满足区间减法. 既然不满足区间减法就别纠结了, 换个思路......
从左往右扫描整个序列, 对每种权值记录最新一次出现的位置pos, 并将线段树可持久化. 要查A[l..r]的mex, 只需要在第r棵线段树中找最小的i, 使得pos[i]<l. 只需维护pos的区间最小值.
cls的论文里说, 可持久化有化离线为在线的神奇功能, 果真如此.
UPDATE: 把离线做法中的线段树可持久化也可以实现在线.