Pair - MarisaOJ: Marisa Online Judge

Given an array

A

$A$ of

n

$n$ integers and

q

$q$ queries of either forms: -

1 l r x

$1 l r x$ : increase each element

A_{l}, A_{l + 1}, . . ., A_{r}

$A_l,A_{l+1},...,A_r$ by

x

$x$ . -

2 x

$2 x$ : find the maximum

j - i

$j-i$ that

A_{i} = A_{j} = x

$A_i=A_j=x$ . ### Input - The first line contains two integers

n, q

$n,q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

q

$q$ lines, each line contains a query of the above forms. ### Output - Print an integer, which is the answer for each query of type

2

$2$ . If there is no answer, print

- 1

$-1$ . ### Constraints -

1 \leq n, q \leq 10^{5}

$1 \le n,q \le 10^5$ . -

1 \leq l, r \leq n

$1 \le l, r \le n$ . -

1 \leq A_{i}, x \leq 2 \times 10^{9}

$1 \le A_i,x \le 2 \times 10^9$ . ### Example Input:

231212212324

$2 3 1 2 1 2 2 1 2 3 2 4$

Output:

0 - 1

$0 -1$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Binary search

Data structure

Rating

1700

Source

Codeforces

Solution (0)

Solution