120. 防线

作者：弘树
日期：2024-10-15

1. 前缀和 + 二分

需要找到一种数据结构能够快速修改区间内的部分点的信息，如果直接枚举每一个点的话肯定会 TLE，

由于整个序列中最多存在一个奇数，如果存在的话，那么：

1. 在该奇数前面均为偶数，并且前缀和也为偶数。
2. 在该奇数后面均为偶数，所以从该奇数开始后面所有数的前缀和均为奇数

由此找到一个分界点，可以二分该分界点。

在二分的时候，需要计算二分点 $mid$ 的前缀和 $res$，之后判断 $res$是否为奇数：

1. 若为奇数，则将区间更改为 $[l, mid]$
2. 若为偶数，则将区间更改为 $[mid + r, r]$

最后判断二分结束时指针 $r$（或 $l$）处是偶数还是奇数，如果为奇数则输出答案，否则输出“There’s no weakness.”。

• 时间复杂度: $O(T \times N \times logE)$
• 空间复杂度: $O(N)$

C++

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 200010;

struct Seq
{
    int s, e, d;
}seqs[N];

int n;

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

void work()
{
    cin >> n;
    int l = 0, r = 0; 
    for (int i = 0; i < n; i ++)
    {
        cin >> seqs[i].s >> seqs[i].e >> seqs[i].d;
        r = max(r, seqs[i].e);
    }
    while (l < r)
    {
        int mid = (LL)l + r >> 1;
        if (get_sum(mid) & 1) r = mid;
        else l = mid + 1;
    }
    auto sum = get_sum(r) - get_sum(r - 1);
    if (sum & 1) cout << r << " " << sum << endl;
    else cout << "There's no weakness." << endl;
}

int main()
{
    int T; cin >> T;
    while (T --) work();
    return 0;
}