题解 | #G python 分类讨论#

G 小红不想做平衡树 python 分类讨论

暴力做法，把区间[0,n-1]分成若干个单调区间

增变成减的极大值点x储存于列表h , x 满足 a[x-1]<a[x] and a[x]>a[x+1]

减变成增的极小值点x储存于列表l ，x 满足 a[x-1]>a[x] and a[x]<a[x+1]

只考虑第一个和最后一个区间都是增区间的情况，如果不是可以在前后增项变成第一个和最后一个区间都是增区间的情况

分增，减，增减，减增，增减增这5种情况讨论，分别计数即可。

a = list(map(int,input().split()))
def solve(a,n):
    l = []
    h = []
    l.append(0)
    res = True
    for i in range(1,n-1):
        if a[i] > a[i+1] and res:
            h.append(i)
            res = False
        elif a[i] < a[i+1] and not res:
            l.append(i)
            res = True
    h.append(n-1)
    ans1 = ans2 = ans3 = 0
    m = len(l)
    for i in range(m):  # 计数：增
        x,y = l[i],h[i]
        ans1 += (y-x+1)*(y-x+2)//2
    for i in range(m-1):   # 计数：减
        x,y = h[i],l[i+1]
        ans1 += (y-x+1)*(y-x+2)//2 - 2
    for i in range(m-1):  # 计数：增减
        x,y,z = l[i],h[i],l[i+1]
        for j in range(y+1,z+1):
            if a[y-1] < a[j]:
                ans2 += (y-x)
            else:
                break
    for i in range(m-1):  # 计数：减增
        x,y,z = h[i],l[i+1],h[i+1]
        for j in range(y-1,x-1,-1):
            if a[j] < a[y+1]:
                ans2 += (z-y)
            else:
                break
    for i in range(m-1):  # 计数：增减增
        x,y,z,w = l[i],h[i],l[i+1],h[i+1]
        if a[y-1] < a[z] and a[y] < a[z+1]:
            ans3 += (y-x)*(w-z)
    return ans1+ans2+ans3

if a[0] < a[1]: 
    if a[-2] < a[-1]:
        print(solve(a,n))
    else:
        b = a + [a[-1]+0.5]  # 在最后增项，使最后一个区间是增区间
        print(solve(b,n+1) - 2)
    
else:
    if a[-2] < a[-1]:
        b = [a[0]-0.5] + a  # 在前面增项，使第一个区间是增区间
        print(solve(b,n+1) - 2)
    else:
        b = [a[0]-0.5] + a + [a[-1]+0.5]  # 前后均增项
        print(solve(b,n+2) - 4)