标签为 [树状数组] 的文章

BZOJ 2434 阿狸的打字机

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P,则求出y==当前P的次数的所在节点的子树大小。 如果为B,删去当前节点的影响,返回它的父亲 否则 加入,加上当前节点的影响 可以用树状数组维护 Code: #include<cstdio> #include<algorithm> #in ......

BZOJ2141 排队

题目传送门 Solution: 这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在它后面有几个数比它小。然后就可以维护逆序对的数量了。这个可以用树套树来完成,外层树状数组表示位置为1~i的前缀和,内层线段树表示权值在l~r的数的个数。 code: #include&lt;cstd ......

BZOJ3295 动态逆序对(树套树)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295 对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层线段树。外层树状数组维护位置为1~i的前缀和,内层线段树维护值在l~r的数有几个。然后就可以完美的解决问题了。这道题用bit套线段树代码非常短。 code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include& ......

POJ2155 Matrix(二维树状数组)

题目传送门:http://poj.org/problem?id=2155 这道题要求区间修改,单点查询,可以用类似差分的方法转化为单点修改,区间查询。对于翻转操作X1,Y1,X2,Y2,只要把(X1,Y1),(X1,Y2+1),(X2+1,y1),(X2+1,Y2+1)四个点的值^=1,询问时只需求左上角为(1,1),右下角为(X,Y)的矩阵的值的异或和,及模2意义下的数和。用二维树状数组就可以维护。 code: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #i ......