non-singular な場合の解法

まずは易しい問題を考えるために問題の仮定に加えて次のことを仮定します。

• \(N\) 点の \(X\) 座標がすべて相異なる
• \(N ( N - 1 ) / 2\) 個の点対の傾きと、 \(Q\) 個のクエリの傾きがすべて相異なる（\(X\) 座標が相異なることから傾きが定義できる）

公式解説と同様に、はじめは辞書順（non-singular 性の仮定よりここでは \(X\) 座標の昇順と等しい）であるような点集合の順列 \(P\) を管理し、点対・クエリを昇順に訪問していきます。

• 点対 \((p, q)\) を訪問したときに、順列 \(P\) における点 \(p, q\) の位置を入れ替えます。（これは隣接スワップであることが保証されます）
• クエリ \(ax + b\) を訪問したときに、\((x, y) \mapsto y - ax - b\) をキーに順列 \(P\) を二分探索し、キーが \(0\) 以上であるものをカウントします。（このキーはこの時点でソート済みであることが保証されます）

なお解法には関係ないのですが、全ての点対を処理したあとには \(P\) は逆順にソートされている状態になっています。

singular な場合を含む解法

まず \(X\) 座標が等しいような点対は無視することにします。そして点対とクエリの間のタイブレーキング、クエリ同士のタイブレーキングは任意で構いません。問題は点対同士のタイブレーキングです。（有限な傾きを持つ）同一直線上にある \(3\) 点以上の集合は、対応するスワップ群の前には \(X\) 座標でソートされており、そしてそのスワップ群のあとにはちょうど逆順になっている必要があります。しかしスワップの適用順によっては逆順になるとは限りあせん。より組合せ論的に言うと、順列 \([0, \dots , K - 1]\) にすべての組 　\(0 ≤ x < y < K\) に関して値 \(x\) と値 \(y\) のスワップを任意の順に適用したからと言って、その順列は逆順になるとは限りません。結局 \(\mathcal{S} _ K\) の要素の任意順の総積が最長元になるとは限らないことを示せば反例になりますね。たとえば \(K = 4, (0, 1) (2, 3) (0, 2) (1, 3) (0, 3) (1, 2) = \mathrm{id}\) が反例になります。

脱線してしまいましたが要するに点対同士の一貫性のあるうまいタイブレーキングをすることが求められます。そこで活躍するのが「記号摂動法」です。記号摂動法は点集合\(\left (x _ i, y _ i \right ) _ { i = 0 } ^ { n - 1 }\) を \(\left (x _ i + \varepsilon^ { M ^ i }, y _ i + \varepsilon^ { M ^ { N + i } } \right )\)（ただし \(\varepsilon\) は非常に小さい正の実数、\(M\) は非常に大きい整数の役割を果たす不定元）に摂動することで、一貫性のあるタイブレーキングをするテクニックで、特に偏角ソートなど一貫性を持って三角形の面積の正負を決める必要があるときに使うことが多いです。今回は傾きの大小関係の比較に使いましょう。

まずは点対 \(\left (x _ 0, y _ 0 \right ), \left (x _ 1, y _ 1 \right )\) と点対 \(\left (x _ 2, y _ 2 \right ), \left (x _ 3, y _ 3 \right )\) の傾きを記号摂動法を使わずに普通に比較しましょう。まず適宜入れ替えることで \(x _ 0 < x _ 1, x _ 2 < x _ 3\) を仮定してよく、分母を払うことができるので \(\left (y _ 1 - y _ 0 \right ) \left (x _ 3 - x _ 2 \right) - \left (y _ 3 - y _ 2 \right ) \left (x _ 1 - x _ 0 \right )\) の符号で決まることがわかりますね。しかし \(0\) 担った場合はタイブレーキングが必要になります。

さてここで記号摂動法を使いましょう。そのためにこれらの点の番号を \(i _ 0, i _ 1, i _ 2, i _ 3\) とおいておきます。素直にやると

\[ \left (y _ 1 + \varepsilon ^ { M ^ { n + i _ 1 } } - y _ 0 - \varepsilon ^ { M ^ { n + i _ 0 } } \right ) \left (x _ 3+ \varepsilon ^ { M ^ { i _ 3 } } - x _ 2 - \varepsilon ^ { M ^ { i _ 2 } } \right ) - \left (x _ 1 + \varepsilon ^ { M ^ { i _ 1 } } - x _ 0 - \varepsilon ^ { M ^ {i _ 0 } } \right ) \left (y_ 3+ \varepsilon ^ { M ^ {n + i _ 3 } } - y _ 2 - \varepsilon ^ { M ^ { n + i _ 2 } } \right ) \]

を展開して \(i _ 0, i _ 1, i _ 2, i _ 3\) の順序（しかも等しい場合もある）で場合分け（もしくはこの形式的な多項式自体を実装）する羽目になって大変なことになります。（一応それでも解けるとは思いますけれども、大変そうですし、TLE しそうでもあります。）

さてこれを簡単にしていきましょう。まず点対を予め \(X\) 座標でソートしておき、さらに点対に属する \(2\) 点は常に番号の小さい方、大きい方の順に並べるとすると、仮定 \(i _ 0 < i _ 1, i _ 2 < i _ 3, x _ 0 < x _ 1, x _ 2 < x _ 3\) を足すことができます。このとき影響度の多い順に次のように分解することができます。

1. \(\left (y _ 1 - y _ 0 \right ) \left ( x _ 3 - x _ 2 \right ) - \left (y _ 3 - y _ 2 \right ) \left (x _ 1 - x _ 0 \right )\)
2. \(\varepsilon ^ { M ^ { i _ 0 } } \left (y _ 3 - y _ 2 \right ) + \varepsilon ^ { M ^ { i _ 2 } } \left (y _ 0 - y _ 1 \right )\)
3. \(\varepsilon ^ { M ^ { n + i _ 0 } } \left ( x _ 2 - x _ 3 \right ) + \varepsilon ^ { M ^ { n + i _ 2 } } \left ( x _ 1 - x _ 0 \right )\)

より正確には 2 の下に \(\varepsilon ^ { M ^ { i _ 1 } }, \varepsilon ^ { M ^ { i _ 3 } }\) と \(Y\) 座標のクロスタームがあるのですが、\(Y\) 座標成分が等しいため 2 が \(0\) のときはこれも \(0\) になり、支配項になることはありません。3 の下にある \(\varepsilon ^ { M ^ { n + i _ 1 } }, \varepsilon ^ { M ^ { n + i _ 3 } }\) と \(X\) 座標のクロスタームも同様です。またさらに下に \(\varepsilon\) 冪のみからなるさらに小さい項があるのですが、これが寄与するのは同一の点が複数存在するときだけなので、この問題では制約で排除されています。（なお排除されていることの証明は省略していますが \(i _ 0\) と \(i _ 2\) の大小関係で場合分けしたりなどちょっと大変なはず）

以上より、点対同士の傾きの比較は次のように書くことができまることがわかりました。

((y0 - y1) * (x2 - x3))
    .cmp(&((x0 - x1) * (y2 - y3)))
    .then_with(|| (i64::from(i0 <= i2) * (y3 - y2)).cmp(&(i64::from(i2 <= i0) * (y0 - y1))))
    .then_with(|| (i64::from(i0 <= i2) * (x2 - x3)).cmp(&(i64::from(i2 <= i0) * (x1 - x0))))
    .then_with(|| unreachable!())

参考文献

https://seiya-kumada.blogspot.com/2013/06/blog-post.html

実装

提出：https://atcoder.jp/contests/abc344/submissions/52038270

• Point 型のフィールドは x, i, y と奇妙な順番で書かれていますが、これは辞書手記順序の定義に関わるので非常に重要です。（最初の points.sort_unstable()）
• 実行コストは掛かりますが、点対とクエリの比較は Itertools::merge_join_by を使いました。（今回は \(Q \gg N\) なので最速を目指すなら公式解説みたいにするのが良いと思います。）

use either::Either;
use itertools::Itertools;
use proconio::input;
use std::cmp::Ordering;
use superslice::Ext;

fn main() {
    input! {
        n: usize,
        mut points: [(i64, i64); n],
        q: usize,
        g0: i64,
        ra: i64,
        rb: i64,
    }
    points.sort_unstable();
    let mut points = points
        .into_iter()
        .enumerate()
        .map(|(id, (x, y))| Point { i: id, x, y })
        .collect_vec();

    let mut rng = Rng::new(g0);
    let mut queries = (0..q)
        .map(|_| {
            (
                -ra + rng.next() % (2 * ra + 1),
                -rb + (rng.next() * ((1 << 31) - 1) + rng.next()) % (2 * rb + 1),
            )
        })
        .collect_vec();
    queries.sort_unstable();

    let mut pairs = points
        .iter()
        .copied()
        .tuple_combinations::<(_, _)>()
        .filter(|&(p0, p1)| p0.x != p1.x)
        .collect_vec();
    pairs.sort_by(pairs_cmp);
    let mut position = (0..n).collect_vec();
    let mut ans = 0;
    for either in pairs.iter().copied().merge_join_by(
        queries.iter().copied(),
        |(Point { x: x0, y: y0, .. }, Point { x: x1, y: y1, .. }), &(a, _)| {
            (y1 - y0) < a * (x1 - x0)
        },
    ) {
        match either {
            Either::Left((Point { i: i0, .. }, Point { i: i1, .. })) => {
                let pos0 = position[i0];
                let pos1 = position[i1];
                position.swap(i0, i1);
                points.swap(pos0, pos1);
            }
            Either::Right((a, b)) => {
                let lb = points.lower_bound_by_key(&0, |Point { x, y, .. }| y - a * x - b);
                ans += n - lb;
            }
        }
    }
    println!("{}", ans);
}

fn pairs_cmp(&(p0, p1): &(Point, Point), &(p2, p3): &(Point, Point)) -> Ordering {
    let Point {
        x: x0,
        y: y0,
        i: i0,
    } = p0;
    let Point { x: x1, y: y1, .. } = p1;
    let Point {
        x: x2,
        y: y2,
        i: i2,
    } = p2;
    let Point { x: x3, y: y3, .. } = p3;
    ((y0 - y1) * (x2 - x3))
        .cmp(&((x0 - x1) * (y2 - y3)))
        .then_with(|| (i64::from(i0 <= i2) * (y3 - y2)).cmp(&(i64::from(i2 <= i0) * (y0 - y1))))
        .then_with(|| (i64::from(i0 <= i2) * (x2 - x3)).cmp(&(i64::from(i2 <= i0) * (x1 - x0))))
        .then_with(|| unreachable!())
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
    x: i64,
    i: usize,
    y: i64,
}

struct Rng(i64);
impl Rng {
    fn new(seed: i64) -> Self {
        Self(seed)
    }

    fn next(&mut self) -> i64 {
        self.0 = (48271 * self.0) % ((1 << 31) - 1);
        self.0
    }
}