editorial

---

E

summary:

적들이 왼쪽에서 오른쪽으로 순서대로 $a_1, \dots, a_n$ 있는 상황에서 레벨 1로 시작해서 캐릭터보다 레벨이 같거나 높은 $x$마리를 처치하면 레벨이 1오른다.

$x$마리를 처치하면 레벨이 1 오른다고 할때, $a_i$보다 레벨이 같거나 높은지를 물어보는 $(i,x)$ $m$개의 쿼리에 응답해야 한다.

solution:

ordered_set을 사용해서 풀면 편하다. ordered_set은 set과 비슷한데, key가 몇 번째 원소인지 $log(n)$의 시간복잡도로 알려주는 기능이 들어간 버전이다. 좌표 압축 + segment tree나 fenwick tree와 같은 자료구조로도 같은 기능을 구현할 수 있다.

먼저 $x$를 기준으로 쿼리들을 분류한다. 그리고 같은 $x$를 가진 $i$들을 내림차순 정렬한다.

레벨을 1부터 시작해서 순서대로 진행한다. 이 레벨을 $lev$라고 하자. 그리고 $x$를 1부터 시작해서 순서대로 진행한다.

$x=k$인 쿼리에서 $p$레벨일 때의 경우를 생각해 보자. 레벨이 $p$가 되기 전에 마지막으로 죽인 적(저장되어 있는 상태이고, k가 클수록 이 값은 클 것이다) 이후 레벨이 $p$보다 크거나 같은 적 $k$마리는 죽이기 전까지 레벨이 동일한 상태이다.

그러한 마지막 적의 위치를 ordered_set으로 구해서(ordered_set에는 $lev$보다 크거나 같은 $a_i$ 값을 가진 적의 위치만 가지고 있기 때문에 가능하다) 그 적보다 작은 $i$값을 가진 쿼리들의 레벨과 $lev$와 비교해서 답을 구한다.

그리고 처리된 쿼리들은 삭제하고 $lev$ 레벨에서 마지막으로 죽인 적의 위치를 갱신해준다.

$k$값이 클수록 마지막 적의 위치는 더 뒤에 있게 되기 때문에 어떤 $k$에서 이미 마지막 적이 $n$보다 크거나 같다면 (더 볼 필요가 없다면) 더 큰 $k$값은 고려할 필요가 없다.