BZOJ 3339: Rmq Problem

时间:2022-06-08 12:04:35

3339: Rmq Problem

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1075  Solved: 549
[Submit][Status][Discuss]

Description

BZOJ 3339: Rmq Problem

Input

BZOJ 3339: Rmq Problem

Output

BZOJ 3339: Rmq Problem

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

BZOJ 3339: Rmq Problem

Source

[Submit][Status][Discuss]

3585 mex 一模一样,代码不变,AC依旧。

 #include <bits/stdc++.h>

 const int mxn = ;

 int n, m, num[mxn], nxt[mxn], lst[mxn], mex[mxn], vis[mxn], ans[mxn];

 struct query {
int l, r, t;
}q[mxn]; inline bool cmp(const query &a, const query &b)
{
return a.l < b.l;
} signed main(void)
{
scanf("%d%d", &n, &m); for (int i = ; i <= n; ++i)
{
scanf("%d", num + i);
if (num[i] > n)
num[i] = n;
} for (int i = ; i <= n; ++i)
lst[i] = n + ; for (int i = n; i >= ; --i)
nxt[i] = lst[num[i]], lst[num[i]] = i; for (int i = ; i <= n; ++i)
{
mex[i] = mex[i - ];
vis[num[i]] = true;
while (vis[mex[i]])
++mex[i];
} for (int i = ; i <= m; ++i)
scanf("%d%d", &q[i].l, &q[i].r), q[i].t = i; std::sort(q + , q + m + , cmp); int left = ; for (int i = ; i <= m; ++i)
{
while (left < q[i].l)
{
int t = nxt[left];
int p = num[left];
for (int j = t - ; j > left; --j)
{
if (mex[j] <= p)break;
else mex[j] = p;
}
++left;
} ans[q[i].t] = mex[q[i].r];
} for (int i = ; i <= m; ++i)
printf("%d\n", ans[i]);
}

@Author: YouSiki