二分法 + 前缀和

这个题目非常强的设定是”整条防线上也最多只有一个位置有奇数个防具。”
可以用二分法来猜这个”奇数点”, 如果猜的点在”奇数点”的左边, 那么前缀和一定是偶数.
如果猜的点在”奇数点”上或者后边, 那么前缀和一定是奇数.
前缀和的计算方法可以利用”序列是等差序列”这个性质.

时间复杂度

O(N*log(R))
N为防线的个数
R为防线的范围(极差)

Python 代码

def check(mid):
    cnt = 0
    for s, e, d in points:
        if mid >= s:
            cnt += (min(e, mid) - s) // d + 1
    return cnt

T = int(input())
for _ in range(T):
    N = int(input())
    points = []
    l = float("inf")
    r = float("-inf")
    for i in range(N):
        s, e, d = map(int, input().split())
        l = min(l, s)
        r = max(r, e)
        points.append((s, e, d))
    r_raw = r
    while l < r:
        mid = (l + r) >> 1
        if check(mid) % 2:
            r = mid
        else:
            l = mid + 1
    if l >= r_raw:
        print("There's no weakness.")
    else:
        print(l, check(l) - check(l - 1))