111qqz的小窝

老年咸鱼冲锋!

hdu 3333 Turing Tree (求区间中不相同数的和,离线+线段树/树状数组)

题目链接

喵呜,离散树状数组。

这道题由于相同的值加和的时候只算一次,所以比较伤脑筋==

怎么办呢?

我们发现对于一个值,由于相同的只算一次,所以在任意时间内,这个值只需要出现一次。

如果我们从作往右将原数组更新到树状数组,如果某个值之前出现过,那么我在更新当前的时候,还需要删掉之前那个。

这样就可以保证当前的序列中一个值只出现了一次,而且位置更新成最后出现的位置。

如果只出现一次的话那就又是我们喜闻乐见的那个熟悉的树状数组了呢 喵呜!

但是这样删掉前面出现的元素真心大丈夫? 万一之后又查询了之前你删掉的点岂不是整个人都萌萌哒了?

 

所以我们可以按照查询区间的又断点排序,保证前面删掉的点以后不会再被查询。

也就是按照顺序,从左往右,边查询,边更新原数组到树状数组。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。


重要的事情说三遍。

所谓离线操作,就是查询的时候不直接输出答案,而是将答案存起来,然后最后一起输出。

 

我们需要开一个数组pre [x] 记录x这个数的上一个位置,初始为-1

由 x的范围太大,数组存不下,所以要离散化。

离散化是为了记录一个数上次出现的位置!

注意要开LL 。

 

update:20160916,写了个线段树的版本。

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363