Range Minimum Query

Time Limit : 1 sec, Memory Limit : 131072 KB

蕶

ϐ $X_1, X_2, ...$ A炩̏lUĂB ꂩ $Q$ ̏񂪏Ԃɗ^B^͈ȉ2ނ̂ꂩłB

• min $\{X_{a_i}, X_{a_i+1}, ..., X_{b_i}\} = y_i$ łB
• ϐ $X_{a_i}, X_{a_i+1}, ..., X_{b_i}$ $y_i$ B

$Q$ ̏񂪖Ȃ悤Ɋeϐ̏lIׂ邩ǂ肹B

͈͂ȉ̌ɏ]B^鐔͑SĐłB

$Q$
$t_1$ $a_1$ $b_1$ $y_1$
$t_2$ $a_2$ $b_2$ $y_2$
$...$
$t_Q$ $a_Q$ $b_Q$ $y_Q$
1. $t_i=0$ ̂ƂAmin$\{X_{a_i}, X_{a_i+1}, ..., X_{b_i}\} = y_i$ ł邱ƂĂB
2. $t_i=1$ ̂ƂA$X_{a_i}, X_{a_i+1}, ..., X_{b_i}$ $y_i$ 邱ƂĂB
• $1 \leq Q \leq 5 \times 10^4$
• $0 \leq t_i \leq 1$
• $1 \leq a_i \leq b_i \leq 10^9$
• $1 \leq y_i \leq 10^9$

o

SĂ̏񂪖Ȃ悤ȏl݂"YES"AłȂ"NO"1sɏo͂B

Sample Input 1

5
0 1 2 8
0 2 3 9
0 2 2 11
1 2 2 7
0 1 3 7

Output for the Sample Input 1

YES

lA$\{X_1, X_2, X_3\} = \{8, 11, 9\}$ ƂB̂ƂA

1. min$\{X_1, X_2\} =$min$\{8, 11\} = 8$
2. min$\{X_2, X_3\} =$min$\{11, 9\} = 9$
3. min$\{X_2\} =$min$\{11\} = 11$
4. $X_2 = 7$
5. min$\{X_1, X_2, X_3\} =$min$\{8, 7, 9\} = 7$

ƂȂSĂ̏ƖȂB

Sample Input 2

2
1 10 100 333
0 100 1000 555

Output for the Sample Input 2

NO`

1ڂ̏ $X_{10}$ $X_{100}$ ̒l $333$ ɂȂƂB 2ڂ̏ min$\{X_{100},...,X_{1000}\}=555$ ƂȂ邱ƂĂ邪A $X_{100}=333$ ł邱Ƃ疵B

Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18