二分法

由于最多只会有一个位置是奇数，可以二分前缀和，对于当前位置前缀和如果为奇数，说明奇数在该位置左侧（包括当前位置），偶数的话必然在右侧
对于前缀和的处理，通常是预处理后直接查表使用就可以在n + logn的时间内解决该问题，但是因为此题的区间之间会有交集，不能在O(n)的时间内求出，想要预处理的话，必须要消耗n ^ 2的时间，所以只能通过在二分时额外求解，这样的话时间复杂度为nlogn，是可以接受的

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
int T, n;
const int N = 200005;

struct sed{
    LL s, e, d;
}a[N];

LL min(LL x, LL y)
{
    return x < y ? x : y;
}

LL max(LL x, LL y)
{
    return x > y ? x : y;
}

LL get_sum(LL x)
{
    LL res = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i].s <= x)
        {
            res += (min(a[i].e, x) - a[i].s) / a[i].d + 1;
        }
    }
    return res;
}

int main()
{
    cin >> T;
    while(T--)
    {
        LL l = 0, r = 0;
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[i].s = x;
            a[i].e = y;
            a[i].d = z;
            r = max(r, y);
        }

        while(l < r)
        {
            LL mid = l + r >> 1;
            if(get_sum(mid) & 1) r = mid;
            else l = mid + 1;
        }

        auto res = get_sum(r) - get_sum(r - 1);
        if(res % 2) cout << r << ' ' << res << endl;
        else cout << "There's no weakness." << endl;
    }


    return 0;
}