G - Loneliness
問題文
数直線上に人がいます。
それぞれの人は $1, 2, ... , 60$ のクラスのうち 1 つに属しています。
同じクラスの人は 2 人で 1 つのペアを組むことができます。
$Q$ 個のクエリが与えられるので順に処理してください。各クエリは次の 2 種類のどちらかです。
1 L R l r：区間 $\lbrack L, R \rparen$ 内にクラス $l, l+1, ... , r$ の人がそれぞれ奇数人、それ以外のクラスの人は偶数人いるという情報が与えられる。2 L R：区間 $\lbrack L, R \rparen$ にいる人で可能な限りペアを組んだ場合に、ペアになれずに残る人数を出力する。質問の時点で答えが一通りに定まらない場合は、代わりにAmbiguousと出力する。
なお、人は数直線上の 1 点に存在し、人の大きさは考慮しないものとします。
制約
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq L < R \leq 10^9$
- $1 \leq l \leq r \leq 60$
- 入力は全て整数である。
- 矛盾するような入力は与えられない。
2 L Rのクエリは少なくとも 1 回以上与えられる。
部分点
この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- （20 点） $Q \leq 3000$ を満たす。
- （80 点） 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$Query_1$
$Query_2$
$:$
$Query_Q$
ただし、 $Query_i$ は $i$ 個目のクエリであり、以下のいずれかの形式で与えられる。
出力
2 L R のクエリに対する答えを、1 行に 1 つずつ、順に出力せよ。
7
1 1 3 2 2
2 1 3
1 1 2 1 1
2 1 4
2 2 3
1 2 4 1 2
2 3 4
1
Ambiguous
2
0
1 つ目のクエリでは、区間 $\lbrack 1, 3 \rparen$ にはクラス 2 の人が奇数人、それ以外のクラス 1, 3 の人が偶数人いるという情報が得られます。
3 つ目のクエリでは、区間 $\lbrack 1, 2 \rparen$ にはクラス 1 の人が奇数人、それ以外のクラス 2, 3 の人が偶数人存在するという情報が得られます。
5 つ目のクエリでは、区間 $\lbrack 2, 3 \rparen$ にクラス 1, 2, 3 の人はそれぞれ奇数, 奇数, 偶数人存在することが分かるので、ペアになれずに残る人は 2 人です。
なお、この入力例は小課題 1, 2 の制約を満たします。
9
2 1 2
1 1 3 1 60
1 1 2 1 30
1 2 3 31 60
1 2 3 31 60
2 1 2
2 1 2
2 1 3
2 2 3
Ambiguous
30
30
60
30
1 つ目のクエリでは、区間 $\lbrack 1, 2 \rparen$ の人に関する情報がなく、答えが一通りに定まらないため Ambiguous と出力します。
同じクエリが何度も出現する場合もあるので注意してください。
なお、この入力例は小課題 1, 2 の制約を満たします。