文章目录 一、题目二、题解 一、题目 Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109

首先让 n n n乘上 2 2 2。 考虑枚举最终被删除的位置有哪些。 a i = 0 a_i=0 ai​=0表示这个位置被删除， a i = 1 a_i=1 ai​=1表示这个位置被保留，设满足 a i = 0 a_i=0 ai​=0的前缀长度为 l l l（ l l l是偶数）， p r e i pre_i prei​表示 a i a_i ai​的前缀和，则从左往右对于每个极长的被删除的连续