Codeforces 1333C. Eugene and an array(思维) /详解

Codeforces Round #632 (Div. 2) C. Eugene and an array 题意: 求出一个数列中子区间满足 此区间的任意子区间之和 不为0的区间个数。 思路: 考虑用dp[x]dp[x]dp[x]记录前缀和为xxx的区间右端点。 那么这道题其实可以看成用map记录前缀和的路径,依次计算每个元素作为区间右端点并且满足条件时对答案的贡献,再进行累加即可。 iii是以a[i]a[i]a[i]为右端点的子区间个数,lastlastlast是 距离 iii最近且[last,i][last,i][last,i]中包含和为0的子段的端点,那么即说明[last+1,i][l