比如上述例子:
{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}
如果给定查询区间[2, 9]
那就意味着要遍历个体元素2和个体元素9,但查询区间中,有几个桶完全包含了该区间,如{...}
此题采用了线段树,我们维护三元组分别表示为{当前区间的最大频次,左边界元素的频次,右边界出现的频次},这样我们就可以从下往上构造每个区间的三元组了,且能够由左孩子和右孩子不断向上合并,用分治的手段解决了统计频次问题...,完美解决。...BIT或线段树,BIT更简洁易懂。...之所以可以这么做,因为题目给了一下额外性质:
permutation,范围是在1 ~ N,且小标在0 ~ N - 1,所以这些值可以方便的映射到二维坐标平面(都不需要离散化处理)
当然在做题时,很重要的一点在于下标自然的排序了