G - Many Common Segment Problems Editorial
by 
PCTprobability
部分点 1 $(L_i,R_i \ge 1)$
\(R_1 \le R_2 \le \dots \le R_N\) となるように予め区間をソートしておきます。ここで、選ぶ区間の index の最小値を \(k\) とします。すると、「選んだ区間の共通部分が空でない」と「選んだ区間の \(L\) は全て \(R_k\) 以下」が同値になります。よって、BIT 等を使って \(L\) の分布を管理しつつ \(k\) の降順に上記を満たす \(L\) の個数を求めて数え上げることでこの問題を解くことが出来ます。計算量は \(\mathrm{O}(N \log N)\) です。
部分点 2 $(N,M \le 2000)$
以降、\(N\) 個の区間集合として空集合を選んでもよいものとします。この補正については、最終的に答えから元のテストケースとしてあり得るものの個数を引けばよいです。
\(k\) 個の区間 \([l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\) に対して、以下で定義される点数の総和をスコアと呼ぶこととします。
- \(x\) が \(k\) 個の区間全てに含まれるならば \(1\) 点
- \(x,x+1\) が共に \(k\) 個の区間全てに含まれるならば \(-1\) 点
さて、\(x\) について \(1\) 点を獲得できる部分集合の個数の総和を考えます。このとき、元の入力の \([L_i,R_i]\) としてあり得るものの個数を \(P_i\)、そのうち \(x\) を含むものの個数を \(Q_i\) とすると求めたい値は \(\prod_{i=1}^{N} (P_i+Q_i)\) となります。\(x,x+1\) の条件についても同様です。よって、上記を実装することでこの問題を \(\mathrm{O}(NM)\) で解くことが出来ます。
満点
上記を高速化することを考えます。まず、\((L_i,R_i) = (-1,-1)\) のケースと \(L_i,R_i \neq -1\) のケースは簡単に処理できます。 \((L_i,R_i) = (-1,k)\) のケースを処理することを考えます。このとき、\(x \le k\) ならば \(P_i + Q_i = k + (k - x +1)\)、\(x > k\) ならば \(P_i + Q_i = k\) となります。
後者については簡単に処理出来ます。前者についてはもし \(x \le k\) という条件がなければ全ての \(i\) に対して \(k + (k - x + 1)\) の総積を取り、multipoint evaluation を行うことで \(\mathrm{O}(N\log^2 N + M \log^2 M)\) で処理することが出来ます。ただし、今回は \(x \le k\) という条件が付いています。この条件をセグ木上に分解してセグ木上の区間それぞれで multipoint evaluation を行うことで \(\mathrm{O}(N\log^2 N \log M+ M\log^3 M)\) で処理出来ます。
ですが、multipoint evaluation は定数倍の重いアルゴリズムであるため上記で通らない可能性が高いです。そこで、\(\log\) を \(3\) 個から \(2\) 個に減らしましょう。\(1\) 回だけ multipoint evaluation を行い、その内部で区間の条件を処理することにします。予め、\(x < k\) を満たす \(x\) に対して \(ax + b\) をかけるという条件に対する \(ax + b\) の総積を \(k\) 番目の葉に持たせておきます。multipoint evaluation をする際、通常は頂点 \(v\) から子 \(l,r\) に対してそれぞれ適切な多項式 \(\bmod\) を取った後その結果を渡して再帰しますが、このタイミングで \(r\) の部分木に含まれる葉の持っている多項式の総積を \(l\) に渡す多項式にかけるとしましょう。すると、計算量は変わらず \(\mathrm{O}(N\log^2 N + M \log^2 M)\) のまま区間の条件を処理することが出来ました。
\((L_i,R_i) = (k,-1)\) のケースに対しても \(x,x+1\) の条件に対しても同様に処理を行うことでこの問題を \(\mathrm{O}(N\log^2 N + M \log^2 M)\) で解くことが出来ます。
posted:
last update: