BZOJ3295 动态逆序对(树套树)

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

BZOJ2212Tree Rotations(线段树合并)

题目大意 有一棵2n-1个节点的二叉树,每个叶子节点上有一个权值(1..n的排列)。可以任意次交换某两棵兄弟子树。问最后叶子上的权值按先序遍历排序后逆序对的最小对数。n<=200000(参考图片) solution 因为两棵兄弟子树换或不换,对它们的祖先和儿子是没有影响的。所以从下到上搜索,并判断这个节点的两棵子树是否交换。考虑贪心,如果交换后能减少两棵子树之间形成的逆序对,就可以交换它们。 而怎么计算两棵子树交换后逆序对的变化情况?只要算出交换前两棵子树之间的逆序对个数就可以了。这用什么来维护呢? 如果用平衡树 ......

BZOJ3223 文艺平衡树

题目大意 需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间。并在最后输出整个数列。 Solution 翻转一个区间,显然是Splay的模板题。既然是模板题,题解当然很短…… 只是用了暴力Insert建树的方法,最开始是一条链,效率可能会变低。以后要尽量用build建树的方法。 代码 C++ #include<cstdio> #include<algorithm> using namespace std; int fa[1000010],son[1000010][3],rev[1000010],size[1000010]; int root,cnt; inline void pu ......

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] ......

HDU1828 Picture

题目大意 给定n个矩形(边平行于坐标轴),求被矩形覆盖图形的周长。 Solution 我们可以分别统计与x轴,y轴平行的周长之和。计算每条线段对答案的贡献。如果这条线段的某几段在被覆盖的图形外面,就可以加入答案。 例如对于平行于y轴的线段。用扫描线的方法,从左往右依次扫描,扫到左边的一条线段时,把整个区间整体+1,扫到右边的线段时,把整个区间整体-1。而操作时值是否为零发生变化的点,就是这条线段在被覆盖图形外面的点,也就是这条线段对答案的贡献。用线段树维护就可以。由于加上和减去的区间是一样的,甚至不用在修改 ......

BZOJ3196 Tyvj 1730 二逼平衡树

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

BZOJ3626 LCA

题目大意 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先 有q次询问,每次询问给出l r z,求$\sum_{i=l}^{r}deep[LCA(i,z)]$ 题解 做这题,首先要发现一个事实:两个点的LCA的深度就是两个点分别到根的链的公共点 所以,对于一次询问,可以将[l,r]区间内的点到根的链的每一个的权值+1,答案即为z到根的链上的点的权值和 这个是可以用树链剖分维护的 对于多次询问,我们将一个询问变成[1,l-1]和[1,r]两个询问,将询问排序,一边更新 ......

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 ......

SPOJ3267 D-query

题目大意 给你一串数,每次询问区间中不重复的数的个数。 Solution 对于这种问题,很想用莫队水过。关于莫队算法,请参考PhoenixGS的一篇博客。莫队算法 但如果询问强制在线的话,就不能用莫队做了。如果我们可以从每个点为结束点,都维护一棵线段树的话,就可以做到查询了。 暴力建树肯定不行,但可以发现,右端点从r变成r+1时,只有最多两个点发生了改变。所以只要改变这两个节点,并将线段树改以前的状态记下来。不在原线段树上修改,而是新开几个节点修改。说白了,就是维护一棵可持久化线段树,用主席树就可以。具体实现时和 ......

HDU4819 Mosaic

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