Maybe a better reading experience
D.
e
the s
c
r
i
p
t
i
o
no
\mathcal{Description}
Description
Give
no
no
n number, this
no
no
n number of all subintervals
l
c
m
lcm
lcm as a set
S
S
S, find the smallest one that does not appear in
S
S
number in S
(
m
e
x
{
S
}
)
(mex\{S\})
(mex{S})
e
g
:
eg:
eg: yes
3
3
3 numbers
1
2
3
1\ 2\ 3
1 2 3, all subintervals
l
c
m
lcm
lcm constitutes a set
{
1
2
3
6
}
\{1\ 2\ 3\ 6\}
{1 2 3 6}, the first non-appearing number is
4
4
4
no
≤
3
?
1
0
5
n\le 3*10^5
n≤3~105,
a
i
≤
1
0
9
a_i\le 10^9
ai?≤109
S
o
l
u
t
i
o
no
\mathcal{Solution}
Solution
Considering a known interval
l
c
m
lcm
lcm, expand the interval to both sides at this time
1
1
1,
l
c
m
lcm
lcm does not drop
After knowing the above, we want to know the
l
c
m
lcm
The smallest non-occurring number in lcm, so we don’t need to know all of them at the beginning
l
c
m
lcm
lcm, consider constructing from small to large
l
c
m
lcm
lcm, and know the interval
l
c
m
lcm
lcm is always increasing as the interval becomes larger
Immediately, you can think of using a small root heap, and initially store the number at each position to indicate that this position is used as the interval
l
c
m
lcm
The starting point of lcm, with
a
no
the s
ans
ans means current consideration
a
no
the s
ans
Is ans the answer, take out the smallest number every time to see if it is equal to
a
no
the s
ans
ans, if equal to
a
no
the s
ans
ans then
a
no
the s
ans
ans cannot be used as an answer,
a
no
the s
ans
ans needs to be increased, and then take out the element at the top of the heap to make its range go one step to the right and re-insert it into the heap, so that it can be guaranteed that when the first element at the top of the heap is not equal to
a
no
the s
ans
found the answer when ans
However, this will time out, because there will be a lot of repeated calculations, such as
1
,
1
,
1
,
1
,
1
,
1
?
1,1,1,1,1,1\cdots
1,1,1,1,1,1? Such a sequence, just want to
a
no
the s
ans
ans becomes 2, you need
no
2
n^2
n2 complexity continues to expand the interval
Consider what kind of situation does not require repeated calculations. When there are several intervals with the same right endpoint and different left endpoints
l
c
m
lcm
When the lcm is the same, only one interval needs to be reserved, for example,
[
1
,
4
]
[1,4]
[1,4]
l
c
m
lcm
lcm is equal to
[
3
,
4
]
[3,4]
[3,4]
l
c
m
lcm
at lcm,
[
1
,
4
]
[1,4]
[1,4] there is no need to continue to the right, because the answer will be exactly the same as
[
3
,
4
]
[3,4]
[3,4] same
Therefore, consider memorizing which values have appeared in each position. When the right end point of a certain interval is expanded, it is found that this position once had an interval.
l
c
m
lcm
lcm is the same as itself, so there is no need to add this range to the heap, use
the s
e
t
set
Set memorizes these values
C
o
d
e
\mathcal{Code}
Code
#include <cstdio>
#include <queue>
#include <set>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 3e5 + 5;
int T, n;
int x[maxn];
set <ll> now[maxn];
priority_queue < pair<ll, int> > q;
ll gcd (ll a, ll b)
{<!-- -->
if (!b) return a;
return gcd(b, a % b);
}
ll lcm (ll a, ll b){<!-- --> return a * b / gcd(a, b); }
int main()
{<!-- -->
scanf("%d", &T);
while (T--) {<!-- -->
scanf("%d", &n);
for (int i = 1; i <= n; + + i) scanf("%d", &x[i]), q.push(mp(-x[i], i)), now[i].clear(), now[i].insert(x[i]);
ll ans = 1;
while (!q.empty() & amp; & amp; q.top().first == -ans) {<!-- -->
while (!q.empty() & amp; & amp; q.top().first == -ans) {<!-- -->
ll l = -q.top().first;
int i = q.top().second;
q. pop();
if ( + + i <= n) {<!-- -->
l = lcm(l, x[i]);
if (now[i].find(l) == now[i].end()) q.push(mp(-l, i)), now[i].insert(l);
}
}
+ + ans;
}
while (!q.empty()) q.pop();
printf("%lld\
", ans);
}
return 0;
}
If there is something unclear or wrong, please correct me
If you like it, please like and collect it