分析
考虑乱搞。
对于求次大值，用线段树维护就行了。记录下每个区间的最大、次大值。则两个子区间的父区间的最大值就是这四个最大的，次大值就是这四个次大的。复杂度 \(O(\log n)\)。
求次大值的出现次数，乱搞就行了。因为带修，带修莫队或者分块有些麻烦。其实用线段树就行。在维护区间最大、次大值的时候，直接同时维护一下它们对应的出现次数，然后就是一个区间和的问题。复杂度 \(O(\log n)\)。
所以总的复杂度为 \(O(n \log n)\)。不会有人去写莫队吧。
考虑乱搞。
对于求次大值，用线段树维护就行了。记录下每个区间的最大、次大值。则两个子区间的父区间的最大值就是这四个最大的，次大值就是这四个次大的。复杂度 \(O(\log n)\)。
求次大值的出现次数，乱搞就行了。因为带修，带修莫队或者分块有些麻烦。其实用线段树就行。在维护区间最大、次大值的时候，直接同时维护一下它们对应的出现次数，然后就是一个区间和的问题。复杂度 \(O(\log n)\)。
所以总的复杂度为 \(O(n \log n)\)。不会有人去写莫队吧。