Editorial

---

D

summary:

학생 $n$명이 주제 $m$개 중 일정 구간을 안다.

질문을 하면 아는 학생은 손을 1 올리고, 모르는 학생은 손을 1 내린다. (0 이하로 내릴수있음)

질문을 중복되지 않게 한 뒤, 최대 손 과 최소 손 높이의 차이는 몇인지 구하는 문제이다.

solution:

일단 가장 손을 높이 든 학생을 고정한다. (학생 $i$)

그러면 그 구간에서 최댓값은 학생 2 * (학생 $i$가 아는 주제 개수 - 학생 $i$와 다른 어떤 학생과 가장 적게 겹치는 아는 문제 개수 최솟값 )이다.

모든 학생은 구간 단위로 주제를 알고 있으므로, $i$가 $j$를 포함하거나, $i$가 $j$ 가 왼쪽 혹은 오른쪽에서 겹치거나, 겹치지 않거나이다.

만약 $i$와 $j$가 왼쪽 혹은 오른쪽에서 겹친다면 왼쪽에서 겹치는 경우는 가장 오른쪽에서 시작하는 구간($l_x$가 최대인 $x$학생의 구간)과 비교해야 최적이다. (마찬가지로 오른쪽은 $r_x$가 최소인 $x$학생과 비교시 최적) 이렇게 하면 안겹치는 경우도 체크할수 있다.

그리고 포함하는 경우는 가장 길이가 짧은 구간 ($r_i-l_i$가 최소인 구간)과 비교하면 최적이다.

따라서 학생 한 명당 3명의 학생과만 비교하면 된다.

E

summary:

주어진 array의 subsegment의 원소들의 lcm들의 집합을 $S$라고 할때, $S$에 등장하지 않는 최솟값을 찾는 문제이다.

solution:

먼저 중복을 포함한 모든 subsegment의 lcm 개수는 $n^2$개이다. 그러므로 mex(답)은 $n^2+1$을 넘지 못한다. $n^2+1$를 limit라고 하자.

$[1,i]$, $[2,i]$, $\dots$, $[i,i]$ 의 수들로 만들어진 lcm들의 집합을 $L_i$라고 하자. limit를 넘는 lcm은 필요가 없으니 고려하지 않는다.

$L_i$는 $L_{i-1}$의 모든 원소와 $a_i$와 lcm 연산을 하고, $a_i$가 추가된 집합이다.

lcm 연산을 하면 그대로이거나, 2 이상의 수가 곱해진다.

$L_i$의 원소는 다음과 같은데, $L_{i_0}< L_{i_1}< L_{i_2} < \dots $

$2 \cdot L_{i_{j-1}} <= L_{i_j}(1\leq j)$이고, lim보다 큰 원소는 제외시키므로 $L_i$의 원소는 n이 $3 \cdot 10^5$일 때 $lim = 9 \cdot 10^{10}, lim < 2^{37}$이므로 최대 37개 있으므로 set으로 조건에 맞게 $L$과 모든 lcm들을 저장하고 mex를 구하면 시간 복잡도 내에 해결이 가능하다.