降智题
用一个前缀和数组\(s_i\)记录前缀中满足\(a_{i-2} \geq a_{i-1} \geq a_i\)的\(i\)的数量
对于区间询问，答案即为\((r-l+1)-(s[r]-s[l+1])\)
因为对于一组\(a_{i-2} \geq a_{i-1} \geq a_i\)，我们发现决定条件是否满足的是\(a_{i-1}\)因此，我们只要不选择\(a_{i-1}\)即可
CF1817A
发布时间 2023-08-28 21:44:48作者: FOX_konata
降智题
用一个前缀和数组\(s_i\)记录前缀中满足\(a_{i-2} \geq a_{i-1} \geq a_i\)的\(i\)的数量
对于区间询问，答案即为\((r-l+1)-(s[r]-s[l+1])\)
因为对于一组\(a_{i-2} \geq a_{i-1} \geq a_i\)，我们发现决定条件是否满足的是\(a_{i-1}\)因此，我们只要不选择\(a_{i-1}\)即可