No.961 Vibrant Fillumination

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 12
作問者 : koprickykopricky / テスター : PachicobuePachicobue
5 ProblemId : 2539 / 出題時の順位表
問題文最終更新日: 2020-02-01 19:51:03

問題文

ほげちゃんは色のついた長方形のフィルムを $N$ 枚買ってきて, それをすべてガラス板の上にならべました。
各長方形はガラス板を $xy$ 平面とみたときに各辺が $x$ 軸もしくは $y$ 軸に平行になるようにならべられているものとします。
$i$ 番目の長方形の位置は左下の角の座標 $(a_i, b_i)$ および右上の角の座標 $(c_i, d_i)$ を用いて表され, その色は $e_i$ であるとします。
各フィルムは互いに重なっている場合もあります。
フィルムは半透明であるため, ガラス板の下から光を当てるとそのフィルムの色が鮮やかに浮かび上がります。
異なる色のフィルムが重なった部分は 2 つの色のどちらとも異なる新たな色が浮かび上がります。
具体的には座標 $(x, y)$ の色は $(x, y)$ を内部に含むすべてのフィルムの色の重複なし集合として表されるものとします(詳しくはサンプルの例を参照してください)。
ほげちゃんはいざ光を当てて色を浮かび上がらせようと思いましたが、残念ながらライトの電池が切れており光を当てることができず悲しんでいます。
そこであなたはほげちゃんのために下から光を当てたときに $(p + 0.5, q + 0.5)$ が何色になるかという質問に答えるプログラムを書くことにしました。
今 $(p + 0.5, q + 0.5)$ の色を表す重複なし集合を $S = \{ k_1, k_2, \ldots, k_l \}$ としたとき、これをそのまま答えると出力が非常に大きくなる可能性があります。
そのためこの問題では各色に割り当てられたハッシュ値 $h_i$ を用いて計算される値 $h_{k_1}$ $\oplus$ $h_{k_2}$ $\cdots$ $\oplus$ $h_{k_l}$ を答えとして返してください。
ここで $\oplus$ は排他的論理和(xor) の演算を表します。また $S = \emptyset$ のときは $0$ を返してください。

入力

$N$
$h_1$ $h_2$ $\ldots$ $h_N$
$a_1$ $b_1$ $c_1$ $d_1$ $e_1$
$\vdots$
$a_N$ $b_N$ $c_N$ $d_N$ $e_N$
$Q$
$p_1$ $q_1$
$\vdots$
$p_Q$ $q_Q$

1 行目にはフィルムの数 $N$ が与えられます。
2 行目は各色に割り当てられるハッシュ値を表し、色 $i$ のハッシュ値は $h_i$ となります。
3 行目から $N$ 行に渡っては, $i$ 枚目のフィルムの左下の角の座標 $(a_i, b_i)$, 右上の角の座標 $(c_i, d_i)$ およびその色 $e_i$ が与えられます。
$N + 3$ 行目にはクエリの数 $Q$ が与えられます。
$N + 4$ 行目から $Q$ 行に渡っては $i$ 番目のクエリに関する座標 $(p_i, q_i)$ が与えられます。
制約
$1 \le N \le 5 \times 10^4$
$0 \le h_i < 2^{60}$
$0 \le a_i, b_i, c_i, d_i < 2N$
$a_i < c_i$
$b_i < d_i$
$1 \le e_i \le N$
$1 \le Q \le 5 \times 10^4$
$0 \le p_i, q_i < 2N$
入力はすべて整数である。

出力

$Q$ 行出力し、$i$ 行目に $i$ 番目のクエリの答えとして $(p_i + 0.5, q_i + 0.5)$ の色に対応する値 $h_{k_1}$ $\oplus$ $h_{k_2}$ $\cdots$ $\oplus$ $h_{k_l}$ を返してください。
最後に改行してください。

サンプル

サンプル1
入力
 
4
1 2 4 8
3 0 6 5 1
1 3 4 6 2
2 4 5 7 3
0 1 7 2 1
9
1 4
3 4
4 1
6 3
0 1
4 4
2 5
3 3
4 6
出力
2
7
1
0
1
5
6
3
4


例えば、$i = 2$ のクエリの位置は色 $1$, $2$, $3$ のフィルムが重なっているのでハッシュ値は $h_1 \oplus h_2 \oplus h_3 = 7$ となります。
$i = 3$ のクエリの位置は赤色(色 $1$) のフィルムが $2$ 枚重なっていますが, 各座標の色は "重複なし" 集合として表されるため、$i = 5$ のクエリの位置の色と同じになります。
$i = 4$ のクエリの位置はその座標を内部に含むフィルムが存在しないため、対応するハッシュ値は $0$ となります。

サンプル2
入力
6
1122712982464266027 690571985097146340 492323680811811014 422387876601185524 157370045133254199 705415601332626468
0 0 1 1 1
0 0 2 2 2
0 0 3 3 3
2 2 5 5 4
3 3 5 5 5
4 4 5 5 6
5
2 4
4 4
2 2
0 0
1 0
出力
422387876601185524
1025038893234884327
218858125916357682
59918757534908425
1099003965774774050

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。