题解 | 有趣的区间

n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
if a[n-1]%2:
    dp[n-1]=1
for i in range(n-2,-1,-1):
    if a[i]%2:
        dp[i]=n-i
    else:
        dp[i]=dp[i+1]
print(sum(dp))

为了不重不漏地统计区间，用dp[i]表示以a[i]为左端点的区间个数。观察可知，区间里只要有一个奇数，按位或的结果就是1。从后往前考虑，先初始化：若a[n-1]为奇数，dp[n-1]=1，否则为0.

再填表，对于dp[i]，若a[i]为奇数，那么以a[i]作为左边界的任意一个区间都是合法的，dp[i]=n-i；若a[i]为偶数，dp[i]=dp[i+1]（完全继承它后面提供的区间数量，没有增加）

最后输出sum(dp)就是全部合法区间的数量。