Progression

Time limit1sMemory limit1024 MB

Summary

Given N mission difficulties with range updates that add or assign arithmetic progressions, find the longest arithmetic run inside a query range.

Level: Hard8 of 10
Topics: Segment tree, Array, Implementation
Solved: No attempts yet

Problem

Damian is making a video game with $N$ missions. The initial difficulty of mission $i$ is $D_i$ . The game can be played both forwards and backwards. Damian performs two kinds of operations. A patch operation is given as $1$ , $L$ , $R$ , $S$ , $C$ , and it increases the difficulty of every mission $i$ with $L \le i \le R$ by $S + (i - L) \times C$ . A rewrite operation is given as $2$ , $L$ , $R$ , $S$ , $C$ , and it sets the difficulty of every mission $i$ with $L \le i \le R$ to $S + (i - L) \times C$ .

Playable segments and queries

Missions $a$ through $b$ (where $1 \le a \le b \le N$ ) form a playable segment if there is an integer $k$ such that $D_{i+1} - D_i = k$ for every $a \le i < b$ . The value $k$ may be zero or negative. A single mission is a playable segment of length $1$ . An evaluate query is given as $3$ , $L$ , $R$ . For that query, find the length of the longest playable segment inside missions $L$ through $R$ , using the difficulties at that moment.

Examples5

Example 1

Input

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

Expected output

Example 2

Input

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

Expected output

5
5
10

Example 3

Input

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

Expected output

Example 4

Input

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

Expected output

6
5
5

Example 5

Input

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

Expected output

4
2
9