Range Minimum Query

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

実数変数 $X_1, X_2, ...$ があり、何らかの初期値が割り振られている。 これから $Q$ 個の情報が順番に与えられる。与えられる情報は以下の2種類のいずれかである。

  • min $\{X_{a_i}, X_{a_i+1}, ..., X_{b_i}\} = y_i$ である。
  • 変数 $X_{a_i}, X_{a_i+1}, ..., X_{b_i}$ に $y_i$ を代入する。

これら $Q$ 個の情報が矛盾しないように各変数の初期値を選べるかどうか判定せよ。

入力

入力は以下の形式に従う。与えられる数は全て整数である。

$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$ のとき、min$\{X_{a_i}, X_{a_i+1}, ..., X_{b_i}\} = y_i$ であることを示している。
  2. $t_i=1$ のとき、$X_{a_i}, X_{a_i+1}, ..., X_{b_i}$ に $y_i$ を代入することを示している。

制約

  • $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$

出力

全ての情報が矛盾しないような初期値が存在すれば"YES"を、そうでなければ"NO"を1行に出力せよ。

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

初期値を、$\{X_1, X_2, X_3\} = \{8, 11, 9\}$ とする。このとき、

  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$

となり全ての情報と矛盾しない。

Sample Input 2

2
1 10 100 333
0 100 1000 555

Output for the Sample Input 2

NO

1つ目の情報で $X_{10}$ から $X_{100}$ の値が $333$ になったことが分かる。 2つ目の情報は min$\{X_{100},...,X_{1000}\}=555$ となることを示しているが、これは $X_{100}=333$ であることから矛盾が生じる。


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