关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：模拟 + 前缀和

• 我们设 $a_0 = 0, a_{n + 1} = M$，便可以将最初和最终两次操作一起考虑。我们加入的操作一定处在某两个相邻时刻之间。
• 我们不妨设在 $a_i$ 和 $a_{i + 1}$ 两个时刻之间加入一次操作，那么实际上不会影响 $[a_0, a_i]$ 之间的亮灯情况，而 $[a_{i + 1}, a_{n + 1}]$ 之间的亮灯情况被完全翻转了，也即这一段之间的亮灯、灭灯时间互换了。所以，我们需要记录原来各段区间的亮灯和灭灯时长，这可以用前缀和维护。在代码中，我们用 $light$ 数组维护原来的亮灯时长， $dark$ 数组维护原来的灭灯时长。$[a_0, a_i]$ 段的亮灯时间即为 $light[i] - light[0]$， $[a_{i + 1}, a_{n + 1}]$ 之间的亮灯时间为原来该段的灭灯时间，也即 $dark[n + 1] - dark[i + 1]$。
• 我们继续考虑 $[a_i, a_{i + 1}]$ 区间，不论在该区间内哪一时刻加入新操作，都会将这一区间分为一部分亮灯时刻和一部分灭灯时刻，且不会影响该区间之外的亮灯时长。那么，为了最大化这一段内的亮灯时长，我们将该区间分为时长为 $1$ 的灭灯时长和时长为 $a_{i + 1} - a_i - 1$ 的亮灯时长即可。所以在代码中，这一段最大的亮灯时长为 $a[i + 1] - a[i] - 1$。
• 特别地！！！要注意，可以不加入新操作，所以结果初始值便可以设为原来的总亮灯时长。

代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T = 1;
    cin >> T;
    while(T--) {

        int n, M;
        cin >> n >> M;
        vector<int> a(n + 2), light(n + 2), dark(n + 2);
        a[0] = 0, a[n + 1] = M;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1 ; i <= n + 1; i++) {
            light[i] += light[i - 1];
            dark[i] += dark[i - 1];
            if(i & 1) light[i] += a[i] - a[i - 1];
            else dark[i] += a[i] - a[i - 1];
        }

        int ret = light[n + 1]; // 不加入新操作

        for(int i = 0; i <= n; i++) {
            ret = max(ret, light[i] - light[0] + dark[n + 1] - dark[i + 1] + a[i + 1] - a[i] - 1);
        }

        cout << ret << endl;
    }
    return 0;
}