補題の証明
$n \geq d$ なる整数 $n$ を任意に固定する。$\lbrack x ^ n\rbrack P \cdot Q$ を定義通りに計算することで次を得る。
$$\lbrack x ^ n\rbrack P \cdot Q = a _ n - \sum _ {i = 1} ^ d c _ i a _ {n - i}.$$
$a$ の定義より $i \geq d$ なる整数 $i$ に対して $\displaystyle a _ i = \sum _ {j = 1} ^ d c _ j a _ {n - j}$ が成り立つので、これを $i = n\geq d$ として適用することで $\lbrack x ^ n\rbrack P \cdot Q = 0$ が従う。$\blacksquare$
補題より $P\cdot Q = (P\cdot Q) \bmod x ^ d = ((P\bmod x ^ d)\cdot Q)\bmod x ^ d$ として計算できます。$P\bmod x ^ d$ および $Q$ は入力から直ちに求まり、$P\cdot Q$ を $\Theta(d \log d)$ 時間で得ることができます。あとは Bostan-Mori のアルゴリズムを適用することで、全体 $\Theta(d\log d \log N)$ 時間で問題を解くことができます。
長さが $L$ より大きく、左端がブロックの境界と一致するような連続部分列 $A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)}\; (k\gt 0)$ の転倒数の計算を考えます。
$A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)}$ を次のように $3$ つに分解します。
$$A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)} = A _ {\lbrack i\cdot L : (i + 1)\cdot L)} A _ {\lbrack (i + 1)\cdot L : (i + 1)\cdot L + k - 1)} A _ {(i + 1)\cdot L + k - 1}.$$
$(1)$ は一般に成り立つのでこれを適用すると次のようになります。ただし、表記の簡単のため $\mathrm{invL}(i, l) := I(A _ {\lbrack i \cdot L: i \cdot L + l)})$ と定めました。
$$\begin{aligned}
\mathrm{invL}(i, L + k) &= \mathrm{invL}(i, L + k - 1) + \mathrm{invL}(i+1, k) - \mathrm{invL}(i + 1, k - 1) \\ &+I(A _ {\lbrack i\cdot L : (i + 1)\cdot L)}, A _ {(i + 1)\cdot L + k - 1}).
\end{aligned}$$
ここで、$c _ {i, k} := I(A _ {\lbrack i\cdot L : (i + 1)\cdot L)}, A _ {(i + 1)\cdot L + k - 1})$ は $A _ {i\cdot L + j} \gt A _ {(i + 1)\cdot L + k - 1}$ なる $0 \leq j \lt L$ の個数と一致します。従って、$A _ {\lbrack i\cdot L : (i + 1)\cdot L)}$ の要素を予めソートしておき、$A _ {(i + 1)\cdot L + k - 1}$ の値が大きい順に $k$ を走査して尺取り法を行うことで、全ての $k$ に対する $c _ {i, k}$ を計算できます。
この方法でネックとなるのは「$A _ {(i + 1)\cdot L + k - 1}$ の値が大きい順に $k$ を走査して」という部分で、ここで毎回ソートしてしまうと全体で $\Theta(N \sqrt{N} \log N)$ 時間掛かってしまいます。そこで、$i$ の降順に計算することにすれば、$i+1$ のときの $A _ {\lbrack (i + 1) \cdot L : KL)}$ のソート結果と $A _ {\lbrack i \cdot L : (i + 1)\cdot L)}$ のソート結果をマージソートの要領で併せることで、$A _ {\lbrack i \cdot L : KL)}$ のソート結果を $O(N)$ 時間で得られます。
点 $p_i = (x_i ,y_i)$ の寄与を考える。$\arg p _ j \in [\arg p _ i, \arg p _ i + \pi)$ なる $j$ の集合を $S$、それ以外の $j$ の集合を $T$ とすれば、点 $p _ i$ の寄与は次のように書ける。
$$\begin{aligned}
\sum _ {j \in S \sqcup T} \vert x _ i y _ j - y _ i x _j \vert &=
x_i \left(\sum _ {j\in S} y _ j \right) - y _ i \left(\sum _ {j\in S} x _ j \right) \\
& - x_i \left(\sum _ {j\in T} y _ j \right) + y _ i \left(\sum _ {j\in T} x _ j \right)
\end{aligned}$$
この場合は、$\mathrm{add}$ クエリで現れる座標を先読みして座標圧縮を行うことで、通常の Fenwick Tree により全体 $O(Q\log Q)$ 時間で解くことができます。
$D\gt 1$ の場合
概要
$D=1$ の場合と同様に $\mathrm{add}$ クエリで現れる座標の $1$ 次元目を座標圧縮しておきます。そして、各ノードに $D-1$ 次元 Fenwick Tree を乗せることで $D$ 次元 Fenwick Tree を構築します。これにより、次で述べるような方法で各種クエリに答えることができます。
$3$ 次元 Fenwick Tree
上図は $D$ 次元 Fenwick Tree のノード $N_i$ が $D-1$ 次元 Fenwick Tree であり、即ち再帰的な構造を持っていることを示しています。
クエリ処理
一旦 $D$ 次元 Fenwick Tree の構築が完了したと思うことにして、$\mathrm{add}, \mathrm{sum}$ クエリの実装イメージを示します。通常のFenwick Treeを知っていれば難しくないと思います。
# 1-indexed# n : ノード数# N[i] := Fenwick Tree の i 番目のノードdefadd((x1, ..., xD), v):
index = compress(x1) # x1 を座標圧縮して得られる添字while index <= n:
N[index].add((x2, ..., xD), v)
index += index & -index
defsum((x1, ..., xD), (y1, ..., yD)):
if x1 >= y1:
return0
result = 0
i = max_index_less_than(y1) # y1未満の最大の座標に対応する添字while i > 0:
result += N[i].sum((x2, ..., xD), (y2, ..., yD))
i -= i & -i
i = max_index_less_than(x1) # x1未満の最大の座標に対応する添字while i > 0:
result -= N[i].sum((x2, ..., xD), (y2, ..., yD))
i -= i & -i
return result
# 1-indexed
points = empty_list()
# クエリ先読みでFenwick Treeに点を登録するdefregister_point((x1, ..., xD)):
points.append((x1, ..., xD))
# p[i] は上で p_i として説明した変数
p = None# 座標圧縮defcompress(x):
l = 0
r = p.size() + 1while r - l > 1:
m = floor_div(l + r, 2)
if p[m] < x:
l = m
else:
r = m
return r
defbuild():
# pointsの1次元目の値のリスト
coordinates = empty_list()
for (x1, ..., xD) in points:
coordinates.append(x1)
# coordinatesの要素を昇順に、重複なしで並べたリスト
p = sorted_unique_list(coordinates)
n = p.size()
# 再帰終端if D == 1:
returnfor (x1, ..., xD) in points:
# p[index]=x1 なるindex
i = compress(x1)
# addクエリと同様にして i の親を辿っていくwhile i <= n:
# N[i]は(D-1)次元Fenwick Tree
N[i].register_point((x2, ..., xD))
i += i & -i
for i in {1, ..., n}:
N[i].build()
ならば、
の大小関係と
の大小関係は一致する
ならば、
の大小関係と
とする。
に対して、
ならば、
とする。
ならば、
とする。
