记第一个数字i出现的位置的下标为l[i],最后一个数字i出现的位置的下标为r[i]。记1-n中不同的数字个数为tot。 则对每一个询问(l, r)转化为有多少个i满足l < l[i] 且 r[i] < r,记这个数为cnt,则答案为tot - cnt。 将(l[i], r[i])看成平面上一点,则问题转化为二维平面上某点右下方有多少个点。扫描即可。 时间复杂度O(nlogn)
扫描二维码,关注牛客
下载牛客APP,随时随地刷题
全部评论
(1) 回帖