提出 #74626989

---

ソースコード 拡げる

import sys
# 提高递归深度并使用快速读入
input = sys.stdin.read
def solve():
    data = input().split()
    if not data: return
    n = int(data[0])
    q = int(data[1])
    employees = []
    ptr = 2
    for i in range(n):
        x = int(data[ptr])
        v = int(data[ptr + 1])
        employees.append((x, v))
        ptr += 2
    # 1. 坐标压缩：莫队处理的是索引，所以我们要按 X 坐标排序员工
    # 排序后，查询 [L, R] 就变成了在排好序的数组中寻找对应的索引范围
    employees.sort()
    sorted_x = [e[0] for e in employees]
    # 对评分 V 进行离散化，方便用数组 count[] 记录出现次数
    all_v = sorted(list(set(e[1] for e in employees)))
    v_map = {val: i for i, val in enumerate(all_v)}
    v_indices = [v_map[e[1]] for e in employees]
    queries = []
    for i in range(q):
        l_val = int(data[ptr])
        r_val = int(data[ptr + 1])
        ptr += 2
        # 使用二分查找将坐标范围 [L, R] 转换为数组索引范围 [ql, qr]
        import bisect
        ql = bisect.bisect_left(sorted_x, l_val)
        qr = bisect.bisect_right(sorted_x, r_val) - 1
        queries.append((ql, qr, i))
    # 2. 莫队分块排序优化
    block_size = int(n / (q ** 0.5)) if q > 0 else n
    if block_size == 0: block_size = 1
    # 奇偶块排序优化：减小右指针回跳的开销
    queries.sort(key=lambda x: (x[0] // block_size,
                                x[1] if (x[0] // block_size) % 2 == 0 else -x[1]))
    # 3. 莫队核心转移
    ans = [0] * q
    count = [0] * len(all_v)
    current_m = 0  # 当前区间内的总人数
    current_pairs = 0  # 当前区间内评分相同的员工对数: sum(c_i * (c_i - 1) / 2)
    def add(idx):
        nonlocal current_m, current_pairs
        v = v_indices[idx]
        # 增加一个人，评分相同对数的增量是原来的 count[v]
        current_pairs += count[v]
        count[v] += 1
        current_m += 1
    def remove(idx):
        nonlocal current_m, current_pairs
        v = v_indices[idx]
        count[v] -= 1
        current_pairs -= count[v]
        current_m -= 1
    cur_l, cur_r = 0, -1
    for ql, qr, qid in queries:
        if ql > qr:  # 处理空区间
            ans[qid] = 0
            continue
        while cur_r < qr:
            cur_r += 1
            add(cur_r)
        while cur_l > ql:
            cur_l -= 1
            add(cur_l)
        while cur_r > qr:
            remove(cur_r)
            cur_r -= 1
        while cur_l < ql:
            remove(cur_l)
            cur_l += 1
        # 根据推导公式计算结果
        # RankSum = M + M*(M-1)/2 - current_pairs
        res = current_m + (current_m * (current_m - 1) // 2) - current_pairs
        ans[qid] = res
    # 4. 输出结果
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')
if __name__ == "__main__":
    solve()

提出情報

ジャッジ結果