考察
値域が10^6以下なので頻度とprefix和を作る。各pairを小値dと大値xへ向けると寄与はfloor(x/d)。同値はC(freq[d],2)として別計算し、異値は商qごとの正確なbucket [qd,(q+1)d−1]をx>dで切って数える。例えばd=2ではx=3の商1とx=4の商2は別bucketであり、d+1から幅dで区切る方法は誤る。q=1..floor(V/d)を列挙し、bucketの頻度をfreq[d]q倍して合計する。全dのbucket数は調和級数でO(V log V)。
典型の発動条件
整数商が一定の区間[qd,(q+1)d−1]を頻度prefix和で数える。最小値を固定してunordered pairの向きを一意にし、同値pairを組合せで分離する。
問題固有の要素
自己pairと同値要素の重複を避けるためx>dだけをbucket側で数え、x=dはC(freq[d],2)へ分ける。
正当性
各unordered pairは小値dと大値xで一意に向きを決められる。同値はC(freq[d],2)で別に数える。異値では商qの正確な区間[qd,(q+1)d−1]をx>dで切り、freq[d]·区間個数·qを足す。頻度prefix和は各bucketの個数を正確に返すので全pairのfloor(max/min)を一度数える。
実装上の注意
bucket lower=max(d+1,qd)、upper=min(V,(q+1)d−1)とする。lower>upperならskip。q=1の区間をd+1から始める場合でも上端は2d−1であり2dを含めない。答えは64bit。
復習の核
d=2,x=3,4の寄与が1,2へ分かれることを確認する。A=(2,4,4)の正答5と同値pairを一度だけ数える境界を復習する。
計算量と制約
時間
O(V log V+N)、V=max A≤10^6。調和級数個の商bucketを走査する。
空間
O(V)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1 \leq A_i \leq 10^6; All input values are integers.
出典