兴高采烈地准备巩固一下莫队算法,没想到又碰到了离散化,兴高采烈的交上去,没想到因为一个符号,WA了20分钟。
题意
让你求每段区间内不同数字的和。
思路
莫队算法正是处理此类问题的。但是我们需要先离散化,不同于以往的题目,可以用sum[x]代表数字x出现的次数,在这里x可以达到1e10,因此需要先把原数组排序去重之后,用a[]代表原来a[]中的值在去重后数组中的位置,这样我们就可以看sum[a[x]]来代表a[x这个位置上的数字个个数了。如果可以就加上或减去b[a[x]]。
1 |
|
云腾致雨,露结为霜
兴高采烈地准备巩固一下莫队算法,没想到又碰到了离散化,兴高采烈的交上去,没想到因为一个符号,WA了20分钟。
让你求每段区间内不同数字的和。
莫队算法正是处理此类问题的。但是我们需要先离散化,不同于以往的题目,可以用sum[x]代表数字x出现的次数,在这里x可以达到1e10,因此需要先把原数组排序去重之后,用a[]代表原来a[]中的值在去重后数组中的位置,这样我们就可以看sum[a[x]]来代表a[x这个位置上的数字个个数了。如果可以就加上或减去b[a[x]]。
1 | #include <cstdio> |