题目描述

自习室内有一个智能灯。

在 0 时刻，管理员会将打开电闸，并将灯点亮。

在 M 时刻，管理员会直接拉下电闸，此时，如果灯处于点亮状态，则会因为断电而熄灭。

在 0∼M 之间有 n 个不同时刻，不妨用 a1,a2,…,an 表示，其中 0<a1<a2<…<an<M。

在这 n 个时刻中的每个时刻，管理员都会拨动一次智能灯的开关，使灯的状态切换（亮变灭、灭变亮）。

现在，你可以最多额外指定一个时刻（也可以不指定），让管理员在此时刻也拨动开关一次。注意选定的时刻不能与 a1,a2,…,an 相等。

你的目的是让亮灯的总时长尽可能长。

输出这个最大亮灯总时长。

样例

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据，第一行包含两个整数 n 和 M。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
输出一个整数，表示最大亮灯总时长。

数据范围
1≤T≤30,
1≤n≤105,
2≤M≤109,
0<a1<a2<…<an<M。
同一测试点内所有 n 的和不超过 105。

输入样例：
3
3 10
4 6 7
2 12
1 10
2 7
3 4
输出样例：
8
9
6

py 代码

#没有使用前缀和所以tle了
#代码写的很菜 请见谅
gt = lambda : list(map(int,input().split()))
st = lambda : list(map(int,("0 "+input()).split()))
def f(l):
    #print(l)
    #交叉前缀和
    s = [0]
    l1 = [0]
    l2 = [0]
    for i in range(1,len(l)) :
        s.append(l[i]-l[i-1])
    #print(s)
    for i in range(1,len(l)) :
        if i%2 : 
            l1.append(l1[-1]+s[i])
            l2.append(l2[-1])
        else :
            l1.append(l1[-1])
            l2.append(l2[-1]+s[i])
    #print(l1)
    #print(l2)
    m = l1[-1]
    #print(m)
    for i in range(1,len(s)-1) :
        if s[i] < 2 : continue
        m = max(m,l1[i-1]+l2[-1]-l2[i]+s[i]-1)
    m = max(m,l1[-2]+s[-1]-1)
    return m

n = gt()[0]
for i in range(n) :
    a = gt()
    b = st()
    b.append(a[1])
    print(f(b))