진행

시간 제한1초메모리 제한1024 MB

요약

N개의 미션 난이도에 등차수열을 더하거나 덮어쓰는 갱신이 있을 때, 질의 구간에서 등차수열을 이루는 가장 긴 연속 구간의 길이를 구합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 배열, 구현
정답자: 아직 제출이 없습니다

문제

다미안은 $N$ 개의 미션으로 이루어진 비디오 게임을 만들고 있다. $i$ 번째 미션의 초기 난이도는 $D_i$ 이다. 이 게임은 앞으로도 뒤로도 플레이할 수 있다. 다미안은 두 종류의 연산을 수행한다. 패치 연산은 $1$ , $L$ , $R$ , $S$ , $C$ 로 주어지며, $L \le i \le R$ 인 모든 미션 $i$ 의 난이도에 $S + (i - L) \times C$ 를 더한다. 재작성 연산은 $2$ , $L$ , $R$ , $S$ , $C$ 로 주어지며, $L \le i \le R$ 인 모든 미션 $i$ 의 난이도를 $S + (i - L) \times C$ 로 바꾼다.

플레이 가능 구간과 조회

미션 $a$ 부터 $b$ 까지( $1 \le a \le b \le N$ )는 모든 $a \le i < b$ 에 대해 $D_{i+1} - D_i = k$ 를 만족하는 정수 $k$ 가 존재하면 플레이 가능 구간이다. $k$ 는 0 이하일 수도 있다. 미션 하나로 이루어진 구간도 길이가 1인 플레이 가능 구간이다. 조회 연산은 $3$ , $L$ , $R$ 로 주어진다. 이때 그 시점의 난이도를 기준으로, $L$ 부터 $R$ 까지의 구간 안에서 가장 긴 플레이 가능 구간의 길이를 구한다.

예제5

예제 1

입력

10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10

예상 출력

예제 2

입력

10 5
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 10 1 2
3 1 10
2 1 10 3 4
3 1 10

예상 출력

5
5
10

예제 3

입력

10 5
1 2 3 4 1 2 3 4 5 5
3 1 4
3 4 5
3 2 4
3 5 9
3 10 10

예상 출력

예제 4

입력

10 5
1 2 3 4 1 2 3 4 5 5
2 10 10 6 1
3 5 10
1 5 5 4 1
3 1 5
3 1 6

예상 출력

6
5
5

예제 5

입력

10 5
1 2 3 4 1 2 3 4 5 5
1 1 4 -1 -1
3 1 5
3 4 5
1 5 10 -1 -1
3 1 10

예상 출력

4
2
9