지울 수 있는 원소 원소 가 길이 이상의 구간에서 최솟값이라면, 그 구간 안에서 와 바로 이웃한 원소 하나가 반드시 존재하고 보다 크다. 반대로 바로 이웃한 원소가 보다 크면 그 둘을 구간으로 골라 를 지울 수 있다. 따라서 현재 왼쪽 또는 오른쪽 이웃 중 더 큰 원소가 존재하는 것이 삭제 가능 조건이다.
남길 위치의 순서 연산은 삭제만 하므로 는 의 부분 수열이어야 한다. 값 의 원래 위치를 라 하면
을 확인한다. 같은 값이 반복되는 경우도 이 검사로 거부된다.
삭제 구간의 조건 남길 원소들은 삭제되지 않으므로, 지울 원소들은 첫 남길 원소 왼쪽, 남길 원소 사이, 마지막 남길 원소 오른쪽의 구간들로 나뉜다. 각 구간은 다른 구간의 원소와 직접 이웃할 수 없다.
비어 있지 않은 삭제 구간의 최댓값을 , 맞닿은 남길 원소 중 큰 값을 라고 하자. 양끝 구간에는 맞닿는 남길 원소가 하나만 있다. 이 구간을 전부 지울 수 있는 필요충분조건은 이다.
필요성: 를 지우는 순간 더 큰 이웃이 있어야 한다. 같은 구간 안에는 그런 원소가 없으므로 그 이웃은 남길 경계 원소이며, 따라서 이다.
충분성: 구간의 원소를 작은 것부터 지운다. 두 개 이상 남아 있으면 가장 작은 원소는 같은 구간의 더 큰 원소 하나와 이웃하므로 지울 수 있다. 마지막으로 만 남으면 인 경계 원소와 이웃하므로 지울 수 있다. 빈 구간은 자동으로 조건을 만족한다.
구현 남길 원소를 순서대로 따라가며 그 앞의 삭제 구간 최댓값을 한 번씩 훑는다. 왼쪽에 남길 원소가 없으면 경계값을 으로 두고, 구간이 비었을 때의 최댓값도 으로 둔다. 모든 실제 값이 양수이므로 같은 비교식을 사용할 수 있다. 마지막 남길 원소 오른쪽도 따로 확인한다.
순서 조건과 모든 구간 조건을 만족하면 YES, 아니면 NO이다. 전역 최댓값 은 절대로 삭제되지 않으므로 에 없으면 반드시 NO가 된다. 이 사실만 확인하거나 부분 수열 여부만 확인하는 것으로는 충분하지 않다. 예를 들어 , 는 최댓값을 포함한 부분 수열이지만 의 양쪽 경계가 라서 불가능하다.
시간은 , 공간은 이다. 위치, 원소, 구간 최댓값은 모두 이하이며 큰 정수 연산이 필요 없다.
서브태스크 1은 현재 남아 있는 위치들을 비트마스크로 나타내고 가능한 모든 연속 구간 연산을 BFS로 탐색한다. 상태 수는 이하이며, 각 상태에서 구간 최솟값을 점진적으로 유지하면 에 모든 연산을 열거한다. 시간은 , 공간은 로 에서 충분하다. 서브태스크 2는 위 선형 검사를 사용한다.
Solution written by GPT6