灌水区能用来开动脑筋吗
查看原帖
灌水区能用来开动脑筋吗
68207
CreeperLordVader楼主2021/8/6 11:28

给定一个长度为nn的序列{ai}\{a_i\},求[1,n] [1,n] 中有多少个区间[l,r](1lrn)[l,r](1\leq l\leq r\leq n),满足区间内数的与结果等于区间最小值。

出题人的题解是这样的

枚举每个数作为最小值,先找到它往左、往右比它小的数,确定 l,r 的范围。如果要使它大于区间内数的与,那么它一定 有一位 1 被置为了 0,枚举每一位,找它往左、往右第一个 0,只要 l,r能包含这个 0 就会导致区间不符。找比它小的数和 找某一位第一个 0 都可以简单预处理出来。时间复杂度为 nlogn.

问题在于这样要怎么统计答案呢,假如对于每个i我确实求出了左右边界,如果选定区间种最小值不唯一,那么这个区间不就会被几个最小值重复统计?

2021/8/6 11:28
加载中...