上海理工大学2020”联想杯”的一道题
因为前面某题wa9次罚时爆炸
(带着后面罚时增加…)
这题又出不了
卡在100名让我担惊受怕qwq
题目链接
题意:
由于本人太菜无法描述…
还请看原题
思路:
枚举右端点(由于强制在线,也是必须的…),当前b[i]
从左端点递增看很容易发现,区间值也是递增的
这就很容易想到单调栈(由于不会所以赛中没写出)
也可以用笛卡尔树,而且容易思考(只是学会没多久不熟练写了我好久)
找出左边第一个 b[j]<=b[i] 的 j, [j+1, i]这段的值都是b[i]
而[1, j]这段的值不都相同,前缀和形式维护…
这时候计算出的a[i]中的贡献只有右端点是 i 的情况
a[i]+=a[i-1],就补回所有右端点的情况
(以上笛卡尔树思路,以下也是笛卡尔树,单调栈思路咕咕咕)
代码:
1 |
|