标签为 [树套树] 的文章

BZOJ2141 排队

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

BZOJ4785 树状数组

题目传送门 solution 写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差的就是val[l-1]和val[r],然后要使他们相等就是说val[l-1]和val[r]要在mod 2意义下相等,当l=1时就是询问一个点的前缀和和后缀和是否相等。 然后将每个询问看成一个二维平面上的点,(l-1,r),用树套树来维护点合法的概率,用(l1,r1,l2,r2)表示左端点在l1,r1间,右端点在(l2,r2)间的所有区间,然后在(l,r ......

BZOJ3295 动态逆序对(树套树)

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

BZOJ3065 带插入区间K小值

题目传送门 题目大意 带插入、修改的区间k小值在线查询。 题解 调了一下午,最后发现错误如下 正确的: C++ if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k]]].sum)) { if (tmp) { if (lson[k]==tmp) rebuild(lson[k]); else rebuild(rson[k]); tmp=0; } } else tmp=k; 12345678910 if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k] ......

BZOJ3196 Tyvj 1730 二逼平衡树

题目大意 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数) 题解 我过的第一题树套树吧QWQ 第一维用区间线段树,第二维用权值线段树,开始要离散化 第一个操作就是求和 第二个操作二分 第三个操作是修改 第四五个操作可以直接用一二两个操作来实现 好吧就是一道裸题,但有点难写 代码 ......

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<iostream> #include<cstdio> #include<algorithm> #include<cmath> #i ......

HDU4819 Mosaic

题目大意 给出一个n*n的矩阵,给出m个询问,每个询问形如x,y,z,表示询问以x,y为中心点的z*z子矩阵的最大值MAX和最小值MIN,输出(MIN+MAX)/2。并将x,y修改为(MIN+MAX)/2(向下取整)。 Solution 支持修改一个数,并询问一个区间中的最大、最小值,可以想到用线段树维护。以前写过把一个二维矩阵分成四块的二维线段树,因为各种原因,它的复杂度很大。所以只能用树套树维护。外层的线段树中,每个节点都维护一棵内层的线段树,就可以做到询问区间。但在外层的线段树上似乎只能单点修改。 代码  C++ / ......