因为有人问所以就顺手写成题解了,时间仓促排版不好看请见谅awa
根据上述规则,一段区间内的 y 的准确次数会不同时,当且仅当这个区间里出现过 x ,也就是说 x 是导致 y 区间内准确次数变化的原因,当一个区间内没有输入的 x 时,这个区间内所有 y 的准确次数相同
所以解法是:
设正负无穷为 x 取不到的值,依次为2e9-2e9
定义区间单值的意义是 y 取该值时,准确次数为多少:
最后求区间最值即可.
区间加法的时间复杂度高,由于有多次区间加法和最后一次区间查询,可以用差分优化,每次区间[ab]加法在两点ab+1分别作加减标记,最后查询之前进行前缀和即可,前缀和后得到原区间,可以求出区间最值