把0当-1,1当1,做一个前缀和。题目就相当于,问任取两个前缀和之差有多少种。根据观察,发现相邻的绝对差永远是1,维护一个前缀最大值ma和最小值mi。再根据前面的最大最小值计算,在当前位置。使用翻转时,观赏度最大能增加多少(ma - a[i]),最大能减少多少(a[i] - mi)。最后分类讨论有多少贡献,或者直接扔进set里面,看有多少元素

相关推荐

牛客网
牛客企业服务