Range Minimum Query

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

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

  • {\rm 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 のとき、{\rm 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. {\rm min}\{X_1, X_2\} = {\rm min}\{8, 11\} = 8
  2. {\rm min}\{X_2, X_3\} = {\rm min}\{11, 9\} = 9
  3. {\rm min}\{X_2\} = {\rm min}\{11\} = 11
  4. X_2 = 7
  5. {\rm min}\{X_1, X_2, X_3\} = {\rm 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つ目の情報は {\rm min}\{X_{100},...,X_{1000}\}=555 となることを示しているが、これは X_{100}=333 であることから矛盾が生じる。


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