忠诚 标签(空格分隔): 树状数组 线段树 题目描述 老管家是一个聪明能干的人。他为财主工作了整整10年,财主为了让自已账目更加清楚。要求管家每天记k次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每 …

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P, …

题目传送门 Solution: 这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在 …

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295 对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层 …

题目传送门:http://poj.org/problem?id=2155 这道题要求区间修改,单点查询,可以用类似差分的方法转化为单点修改,区间查询。对于翻转操作X1,Y1,X2,Y2,只要把(X1,Y1),(X1,Y2+1),(X2+1,y1),(X2+1,Y2+1)四个点的值^=1,询问时只需求 …