比较水． 唯一一点需要注意的是... 可能有重复元素... 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两个方向中是否至少有一个方向上和等于长度... 所以这样如果有重复元素的话，不处理会出错..　但实际上又没修改..直接前缀和就好了．．． 树状数组个毛线．．． 不过看到还有人线段树搞得233333 /************************************************************************* > File Name: code/bc/#57/1002.cpp > Author: 111qqz > Email: …

比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫　nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护． /************************************************************************* > File Name: code/bc/#56/r1003.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年09月22日 星期二 11时10 …

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

三维树状数组 容斥那里注意一下。 多组数据因为忘记清空c数组而wa了1次，细心！ /************************************************************************* > File Name: code/hdu/3584.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月07日 星期五 14时01分53秒 ************************************************************************/ …

1 和上一道类似，也是更新区间，查询单点。 用到了容斥原理。 /************************************************************************* > File Name: code/poj/2155.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月07日 星期五 00时42分38秒 ************************************************************************/ …

这道题和之前做的树状数组略有不同。 以前的都是更新单点，查询区间，这次反了过来。 做法差不多。 如果更新区间【x,y】增加１ 那么只要 update (x,1),update (y+1,-1) 问单点的时候，sum(i)就是i点的值，而不是1..i的和。 可以看做告诉公路收费口的比喻，update (x,1)相当于入口 update (y+1,-1)相当于出口。 而sum(i)就相当于被几个告诉公路穿过，或者说i点属于几个高速公路，所以是求和 还记得noip2012的时候在tyvj上遇到了一道线段数的题，被＠Ocean　海洋兄用了一个高速公路的神奇比喻解法A掉了。 现在回想，原来是用了树状数组。 …

Inversions **Time Limit:**250MS **Memory Limit:**4096KB 64bit IO Format:%I64d & %I64u Submit Status Description 180. Inversions time limit per test: 0.25 sec. memory limit per test: 4096 KB input: standard output: standard There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find …

这道题可以总结的地方不少。 １：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。 　cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。 ２：原始数组a[i]和树状数组的t[i]的对应问题（？？？存在疑问。。。应该只是这道题，而不是一般规律！） 　这道题n是５０００００，如果直接开数组是可以开得下的，不需要离散化。**但是树状数组的下标对应的是原始数组的值！**也就是t[i]的下表最大可能为９９９，９９９，９９９　！　显然存不下，需要离散化。 **３：学习了离散化的又一种写法。 ** …

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: …