『线段树合并』Day7

颓了一天了。md

虽然还没有过线段树合并板题，但早就用过了。

注意，单次合并复杂度是 \(O(n\log n)\) 的，但是一直合并，保证最终共有 \(n\) 个元素的话，总时间复杂度也是 \(o(n\log n)\) 的。不要理解成单次 \(\log n\)。

一个人千万不能忘记自己的初心，有时候需要静下心来想一想自己到底应该做什么。

难道之前逼自己赶上那么多的努力真的要白费吗。

习题

A 更为厉害

差不多 30 min 秒了。

考虑两种情况，\(b\) 是 \(a\) 的祖先，那么 \(c\) 只能是 \(a\) 的子树。

第二种情况 \(b\) 在 \(a\) 的子树里，但是距离有 \(k\) 的限制。然后 \(c\) 是 \(b\) 的子树，也就是 \(siz_b-1\) 种 \(c\)。

考虑 \(b\) 的个数，按照深度为下标建主席树，每次查询深度区间里在 \(a\) 子树的 dfn 区间中的 sum 即可。

B Minimax

之前看过线段树合并优化 dp，第一次实现。

由于是二叉树，所以 dp 的形式非常简单，就是前缀和后缀和加上一坨。

dp 是二维的，直接把第二维放进 ds 下标，前后缀和可以在你合并左右儿子的时候直接由 sum 得到。

可以结合代码理解。

int merge(int p, int q, int v1, int v2, int w, int l, int r) {
	if(!p and !q) return 0;
	v1 %= Mod, v2 %= Mod;
	if(!p) return upd(q, v2), q;
	if(!q) return upd(p, v1), p;
	pushdown(p); pushdown(q); 
	
	int mid = l + r >> 1;
	int s1 = T[ls].sum, s2 = T[rs].sum, s3 = T[T[q].l].sum, s4 = T[T[q].r].sum;
	
	ls = merge(ls, T[q].l, v1 + (1 - w) * s4, v2 + (1 - w) * s2, w, l, mid);
	rs = merge(rs, T[q].r, v1 + w * s3, v2 + w * s1, w, mid + 1, r);
	
	return pushup(p), p; 
}

C 众数

4 操作就是线段树合并板。考虑众数操作。

有一种好像是众数的套路做法，就是你维护当前的 house 数，如果新加入的数相同那么 cnt ++，否则 cnt --。如果 cnt < 0 那么替换 house 为 nowx。

容易发现序列加入顺序不会影响最终答案的取值。用 ds 维护这个过程。

但是没有必要啊。你众数在的那个值域区间一定满足 Sum > len / 2，根据这个直接 ds 二分即可。注意是 \(m\) 棵一起二分。

数据造得好。

D 旋转树木 Tree Rotations

一眼知交换左右儿子不会影响父亲的集合。

考虑合并的时候内部不可能有新的贡献，你只会算当前右子树中比左子树 val 大的、小的有多少个。

所以只要贪心选更小的一种方案即可。

在你合并的时候，由于要分到左右去 merge，所以你可以直接得出左右儿子的 sum，计算以 mid 作为分界的逆序对。然后递归到内部再算。

代码和 B 差不多。

E 排序

典。

要对数地对一般序列排序是脑子有问题才会想优化的。

但是题目非要我们排序，考虑简单方法。

如果是对 01 序列排序，就可以只维护 1 的个数，然后前缀后缀赋值操作即可。

而你询问只有一个单点，所以我们可以二分这个点是多大，根据所有数和二分值的大小关系转化成 01 序列。

为什么是对的啊。

排序后的序列一定是不变的，位置 q 也不变，只是你二分的 01 序列在变，而且 0 越来越多。（随着 mid 的增大）

什么时候 q 变成 0，就可以了。

晚测 JOISC2017 Sparkles

nb 题，双序列原 & 加强。

4 月做了双序列，但为什么这道题没做出来呢。

因为一开始就想错了。

想这种题怎么可能贪心，绅士居然想出了从 \(S\) 集合里面分离 \(B\) 集合出去的zhizhang做法，复杂度指数线性对数。可过。

注意：一个人肯定是等火要烧完了才传递，以及路径上经过的人会跟着这个人走，不劣。

所以推出：每个时刻，和 \(k\) 在一起的人构成一个连续的区间 \([l,r]\)。

你可以用一个平方 dp 进行转移。

首先，火把在最优传递方法下，是可以一共有 \((r-l)\)