题解 | 圆上计数

import bisect


def main():
    import sys

    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    C = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr : ptr + N]))

    # 排序点的位置
    a.sort()

    # 计算总方案数
    total = N * (N - 1) * (N - 2) // 6 if N >= 3 else 0

    # 计算不符合条件的方案数（能被同一个半圆包含的三元组）
    bad = 0
    half = C // 2

    for i in range(N):
        # 当前点的位置
        pos = a[i]
        # 半圆的结束位置（顺时针）
        end = pos + half
        # 找到第一个超过 end 的位置
        # 处理环形，将数组扩展为 a + [x+C for x in a]
        if end >= C:
            end -= C
            # 在环形中找
            j = bisect.bisect_right(a, end)
            cnt = (N - i - 1) + j
        else:
            j = bisect.bisect_right(a, end)
            cnt = j - i - 1

        # 从 cnt 个点中选 2 个的组合数
        if cnt >= 2:
            bad += cnt * (cnt - 1) // 2

    # 符合条件的方案数
    ans = total - bad
    print(ans)


if __name__ == "__main__":
    main()