31998번 - 리스트 가상화

문제

한국정보기술진흥원에서 새로 개발한 모바일 어플리케이션의 화면에는 $N$개의 직사각형 모양 항목이 빈틈없이 세로로 나열되어 있다. 위에서 $i$번째 항목의 높이는 $H_i$이다. 가장 위에 있는 항목의 위쪽 변은 화면의 맨 위와 맞닿아 있다. 여러분은 화면을 조작하는 사용자의 요청 $Q$개를 순서대로 처리해야 한다. 어떤 요청에서도 요청 전에 있던 항목들의 순서가 요청 후에 뒤바뀌는 경우는 없다.

• 1 $i$ $h$: 높이가 $h$인 새로운 직사각형 항목이 위에서 $i$번째에 위치하도록 끼워넣는다. 새로운 항목은 $j \lt i$인 모든 $j$에 대해서 위에서 $j$번째 항목보다 밑에 있게 된다. $j \ge i$인 모든 $j$에 대해서, 항목을 끼워넣기 전 위에서 $j$번째였던 항목들은 새로운 항목보다 밑으로 가게끔 아래로 움직인다. 움직인 이후 모든 항목은 빈틈없이 나열되어야 한다.
• 2 $i$: 위에서 $i$번째 항목을 지운다. $j \gt i$인 모든 $j$에 대해서, 항목을 지우기 전 위에서 $j$번째였던 항목들은 모든 항목이 빈틈없이 나열되도록 위로 움직인다.
• 3 $t$ $b$: 화면의 맨 위로부터 $t$만큼 떨어진 위치부터 $b$만큼 떨어진 위치까지의 범위에, 직사각형의 경계를 제외한 내부의 점이 적어도 하나 포함되는 항목의 수를 한 줄에 출력한다.

입력

첫 번째 줄에 처음 화면에 있는 항목의 수 $N$과 요청의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200,000円)$

두 번째 줄에 각 항목의 높이를 나타내는 정수 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다. $(1 \le h_i \le 1,000円,000円,000円)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 각 요청이 주어진다. 요청은 다음 형식 중 하나를 따른다.

• 1 $i$ $h$ $(1 \le i \le ($요청 직전에 존재하는 항목의 수$)+1;$ 1ドル \le h \le 1,000円,000円,000円)$
• 2 $i$ $(1 \le i \le ($요청 직전에 존재하는 항목의 수$))$
• 3 $t$ $b$ $(0 \le t \lt b \le 400,000円,000円,000円,000円)$

출력

3 $t$ $b$ 요청이 들어올 때마다, 화면의 맨 위로부터 $t$만큼 떨어진 위치부터 $b$만큼 떨어진 위치까지의 범위에, 직사각형의 경계를 제외한 내부의 점이 적어도 하나 포함되는 항목의 수를 한 줄에 출력한다.

제한

힌트