概要

各クエリで指定された座標範囲内の社員について、「同率順位」での順位の総和を求めます。順位の総和は「要素数から決まる定数 − 同じ評価スコア同士の組数」に変形でき、区間内の「同値ペア数」を高速に数える問題になります。

考察

1. 順位の総和は「同値ペア数」で表せる

クエリで得られる集合（実際には座標でソートした配列の部分区間）を \(m\) 人とし、評価スコア列を \(V_1,\dots,V_m\) とします。

各社員の順位は
- 自分より評価が真に大きい人数を \(k\) として \(k+1\)

なので、順位総和は [ \sum_{i=1}^{m} (1 + #{j: V_j > Vi}) = m + \sum{i=1}^{m} #{j: V_j > V_i} ]

ここで、2人の組 \((i,j)\)（\(i<j\)）を考えると： - \(V_i \neq V_j\) なら、小さい方は「自分より大きい人が1人いる」ので、この組は総和に +1 を寄与 - \(V_i = V_j\) なら、どちらも「真に大きい」には数えないので、寄与 0

つまり
[ \sum_{i=1}^{m} #{j: V_j > V_i} = \binom{m}{2} - (\text{同値ペア数}) ] よって [ \text{順位総和} = m + \binom{m}{2} - (\text{同値ペア数}) = \frac{m(m+1)}{2} - (\text{同値ペア数}) ]

したがって各クエリは、 - \(m = r-l+1\) が分かれば \(\frac{m(m+1)}{2}\) は即計算できる - 残りは区間内の 「同じ評価スコアのペア数」（例：同じ値が \(c\) 個なら \(\binom{c}{2}\)）を数えればよい

に帰着します。

2. 素朴解は間に合わない

各クエリで区間を取り出して頻度を数えると、最悪で \(O(N)\) かかり、 [ O(NQ) \approx 10^{10} ] となり TLE です。

3. 解決方針：区間の同値ペア数をオフラインで高速計算

座標 \(X_i\) は全て異なるので、社員を \(X\) でソートすると、クエリ \([L,R]\) は二分探索で配列の連続区間 \([l,r]\) に変換できます。

あとは「静的配列に対する多数の区間クエリで、区間内の同値ペア数」を高速に処理します。コードでは平方分割（ブロック分け）を使ったオフライン処理で、概ね \(O((N+Q)\sqrt{N})\) で解きます。

アルゴリズム

全体の流れ

1. 社員を勤務地座標 \(X\) でソートし、配列 V[0..N-1] を作る
   
2. 各クエリ \([L,R]\) を bisect_left/right でインデックス区間 \([l,r]\) に変換
   
3. 各クエリについて
   [ m=r-l+1,\quad \text{total}=\frac{m(m+1)}{2} ] を計算し、同値ペア数 pairs を求めて total - pairs を出力
   
4. 同値ペア数の求め方を、区間が
   • 同一ブロック内の場合：長さ \(\le S\) を活かして直接数える
   • 複数ブロックにまたがる場合：左端ブロックごとにまとめて右端を伸ばしながら処理する

という2通りで高速化します。

前処理：評価スコアの座標圧縮

評価スコア \(V_i\) は最大 \(10^9\) なので、そのまま頻度配列にできません。
uniq = sorted(set(V)) を作り、各 \(V\) を 0..K-1 に圧縮して A[i] とします（コードの mp と A）。

これにより頻度配列 cnt[0..K-1] が使えます。

同値ペア数の更新式

区間に値 \(a\) を1つ追加するとき、すでに区間内に \(a\) が \(c\) 個あれば、新たにできる同値ペアは \(c\) 個です。 - pairs += c - cnt[a] += 1

これで区間内の同値ペア数が管理できます。

ケース1：同一ブロック内クエリ（短いので直接）

ブロック幅を \(S \approx \sqrt{N}\) とします。
\(l,r\) が同じブロックなら長さは最大 \(S\) なので、区間を走査して頻度を数え、同値ペア数を作ります。

このとき毎回 cnt を初期化すると重いので、コードは - tmp_vis と ver（バージョン管理） で「このクエリで触れた値だけ初期化」しています。

ケース2：複数ブロックにまたがるクエリ（オフライン処理）

左端ブロック lb = l//S ごとにクエリを集め、同じ lb のクエリを 右端 r の昇順にソートします。

ブロック b の右端境界を midL = (b+1)*S とし、基本区間を - 常に左端固定 midL - 右端を cur_r で伸ばす という形で管理します。

処理手順（各クエリ \((l,r)\)）： 1. cur_r を r まで伸ばしながら cnt と pairs を更新（右側を追加） 2. 左側の不足分 [l, midL-1] を一時的に追加して pairs を得る 3. 追加した左側を削除して状態を元に戻す（次のクエリのため）

左側の一時追加はブロック幅 \(S\) 以内なので、1クエリあたり \(O(S)\) で済みます。右端の伸長はブロック内の全クエリで合計 \(O(N)\) 程度になります。

最後に [ \text{answer} = \text{total} - \text{pairs} ] を出力します。

計算量

• 時間計算量: おおむね \(O\big((N+Q)\sqrt{N}\big)\)
  
  • 同一ブロック内：各クエリ \(O(S)\)
    
  • 複数ブロック：右端伸長の合計 \(O(N)\)（ブロックごと）、各クエリの左側処理 \(O(S)\)
• 空間計算量: \(O(N + Q + K)\)（\(K\) は評価スコアの種類数、最大 \(N\)）

実装のポイント

• クエリ区間への変換：社員を \(X\) でソートし、l = bisect_left(X, L), r = bisect_right(X, R) - 1 とする（空なら l > r）。

• 答えの式：区間長 \(m\) に対し total = m*(m+1)//2、同値ペア数を pairs として total - pairs。

• 座標圧縮：V を 0..K-1 にして頻度配列で管理する。

• 同一ブロック内の高速化：毎回 cnt 全初期化をせず、tmp_vis + バージョンで「触った値だけ初期化」する。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    emp = []
    for _ in range(N):
        x = next(it)
        v = next(it)
        emp.append((x, v))
    emp.sort()

    X = [x for x, _ in emp]
    V = [v for _, v in emp]

    uniq = sorted(set(V))
    mp = {v: i for i, v in enumerate(uniq)}
    A = [mp[v] for v in V]
    K = len(uniq)

    S = int(N ** 0.5) + 1
    nb = (N + S - 1) // S

    queries_by_block = [[] for _ in range(nb)]
    ans = [0] * Q

    tmp_cnt = [0] * K
    tmp_vis = [0] * K
    ver = 0

    bl = bisect_left
    br = bisect_right

    for qi in range(Q):
        L = next(it)
        R = next(it)
        l = bl(X, L)
        r = br(X, R) - 1
        if l > r:
            ans[qi] = 0
            continue
        m = r - l + 1
        total = m * (m + 1) // 2
        lb = l // S
        rb = r // S
        if lb == rb:
            ver += 1
            cv = ver
            pairs = 0
            for idx in range(l, r + 1):
                a = A[idx]
                if tmp_vis[a] != cv:
                    tmp_vis[a] = cv
                    tmp_cnt[a] = 0
                c = tmp_cnt[a]
                pairs += c
                tmp_cnt[a] = c + 1
            ans[qi] = total - pairs
        else:
            queries_by_block[lb].append((r, l, qi, total))

    A_local = A
    for b in range(nb):
        qlist = queries_by_block[b]
        if not qlist:
            continue
        qlist.sort()
        midL = (b + 1) * S
        if midL > N:
            midL = N

        cnt = [0] * K
        pair = 0
        cur_r = midL - 1

        for r, l, qi, total in qlist:
            for idx in range(cur_r + 1, r + 1):
                a = A_local[idx]
                c = cnt[a]
                pair += c
                cnt[a] = c + 1
            cur_r = r

            for idx in range(midL - 1, l - 1, -1):
                a = A_local[idx]
                c = cnt[a]
                pair += c
                cnt[a] = c + 1

            pairs = pair

            for idx in range(l, midL):
                a = A_local[idx]
                c = cnt[a] - 1
                cnt[a] = c
                pair -= c

            ans[qi] = total - pairs

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。