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

题目传送门 solution 写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差 …

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

题目大意 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数) 题解 我过 …

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

题目大意 给出一个n*n的矩阵,给出m个询问,每个询问形如x,y,z,表示询问以x,y为中心点的z*z子矩阵的最大值MAX和最小值MIN,输出(MIN+MAX)/2。并将x,y修改为(MIN+MAX)/2(向下取整)。 Solution 支持修改一个数,并询问一个区间中的最大、最小值,可以想到用线段 …