竞赛讨论区 > 牛客网暑期ACM多校训练营(第一场)J 题解 BIT
头像
SidneySun
发布于 2018-07-20 14:05
+ 关注

牛客网暑期ACM多校训练营(第一场)J 题解 BIT

记第一个数字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)

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐