题目链接 喵呜，离散树状数组。 这道题由于相同的值加和的时候只算一次，所以比较伤脑筋== 怎么办呢？ 我们发现对于一个值，由于相同的只算一次，所以在任意时间内，这个值只需要出现一次。 如果我们从作往右将原数组更新到树状数组，如果某个值之前出现过，那么我在更新当前的时候，还需要删掉之前那个。 这样就可以保证当前的序列中一个值只出现了一次，而且位置更新成最后出现的位置。 如果只出现一次的话那就又是我们喜闻乐见的那个熟悉的树状数组了呢 喵呜！ 但是这样删掉前面出现的元素真心大丈夫？ 万一之后又查询了之前你删掉的点岂不是整个人都萌萌哒了？ 所以我们可以按照查询区间的又断点排序，保证前面删掉的点以后不会再被查询。 也就是按照顺序，从左往右，边 …

poj 2481 题目链接 题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合） 思路： 下面是一年前用树状数组过掉的时候写的题解： 和 star那道题差不多。 需要注意的是star那道题读入的时候已经排好了序，而这道题没有排序 由于答案是按照下表输出，排序的时候下标会被打乱，所以要存一下下表到结构体里。 另一个区别是，star那道题星星不会重复，就是说一个位置不会有多颗星星。 而这道题却可能，而且题目中说，如果区间的长度差为0（就是后面的那个不等式），那么不计数。 因为区间下标可能为0，但是树状数组的下表必须从1开始，所以下表要+1，但是由于下表可能有所重复，所以 不能用++,而是 …

poj 2352题目链接 题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。 要求统计0到n-1 level的星星各有多少个。 下面是一年前写的树状数组的题解： 依然想不通，智商是硬伤，绝望的想哭，真的想哭。 更新于2015年08月04日01:47:18： 好像有点明白了.....详情看注释 树状数组ac代码： /************************************************************************* > File Name: code/poj/2352.cpp > Author: 111qqz > Email: …