Python统计电线交叉数代码超时，如何优化减少运算量？

问题原因 #

你的核心超时问题出在findCrosses函数的实现逻辑：

• 双重循环的时间复杂度为O(n²)，当输入规模n超过1000时，运算量会达到百万级别，n到10000就会到亿级，远超过Python单秒可承载的运算上限，必然触发超时。

优化思路 #

这个交叉线计数问题本质是逆序对计数问题：

1. 先将所有电线按照左侧端点从小到大排序，此时左侧已经严格递增，两条电线交叉的充要条件为：排在前面的电线的右侧端点值 > 排在后面的电线的右侧端点值，完全符合逆序对的定义。
2. 逆序对可以用树状数组（Fenwick Tree）或者归并排序变种实现，时间复杂度直接降到O(n log n)，即使n达到1e5规模也可以正常运行。

优化后代码 #

import ast

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0]*(self.n + 2) # 避免下标越界
    
    def update(self, idx, delta=1):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def seperateInputs(inp):
    # 用ast直接解析合法列表，比手动拆分字符串效率更高、容错性更好
    n_part, list_part = inp.split(' ', 1)
    n = int(n_part)
    wires = ast.literal_eval(list_part)
    return n, wires

def findCrosses(n, wires):
    # 按左侧端点从小到大排序
    wires_sorted = sorted(wires, key=lambda x: x[0])
    # 提取右侧端点序列
    right_values = [x[1] for x in wires_sorted]
    # 离散化处理（应对右端点范围过大的情况）
    sorted_unique = sorted(set(right_values))
    rank = {v:i+1 for i, v in enumerate(sorted_unique)} # 树状数组从1开始下标
    max_rank = len(sorted_unique)
    
    ft = FenwickTree(max_rank)
    cross_count = 0
    # 从后往前遍历统计逆序对
    for val in reversed(right_values):
        r = rank[val]
        cross_count += ft.query(r - 1)
        ft.update(r)
    return cross_count

def main():
    import sys
    # 批量读取输入，比逐行input更快
    input = sys.stdin.read().splitlines()
    m = int(input[0])
    for i in range(1, m+1):
        n, wires = seperateInputs(input[i])
        print(findCrosses(n, wires))

if __name__ == "__main__":
    main()

额外优化点 #

1. 输入处理用ast.literal_eval直接解析列表字符串，比你原来手动拆分字符串的逻辑效率更高，也更不容易出格式错误。
2. 用sys.stdin.read()批量读取所有输入，避免频繁调用input()的IO开销，大规模输入下性能提升明显。
3. 增加了离散化逻辑，即使题目中右侧端点取值范围很大，也可以正常运行，不会出现树状数组开不下的问题。

你提供的样例输入用上述代码运行可以得到完全一致的输出，且大规模输入下不会超时。

内容的提问来源于stack exchange，提问作者user16014650