T1
二分答案,每次输出后 \(l \gets l + 1\), \(r \gets r + 1\)。
T2
每次计算时,显然对于 \(a,b\) 某一位都是 \(1\) 才会对答案产生贡献。
我们统计每一位的贡献,\(a\) 的第 \(i\) 位为 \(1\) 时,\(b\) 中初始位置比第 \(i\) 位高的 \(1\) 都会右移到这一位,对答案的贡献就是 \(b\) 中初始位置比第 \(i\) 位高的 \(1\) 的数量 \(\times\) 这一位的位权 \(2^i\)。
预处理一下 \(2\) 的次幂就可以了。
T3
我们对于线段树每个节点维护一个矩阵 \([sum_a, sum_b, 1]\) 记录信息,再维护一个 \(3 \times 3\) 矩阵表示懒标记,清空时赋值为 \(I\)(单位矩阵)。
区间修改时,我们让当前节点的信息矩阵和懒标记矩阵同时乘上修改矩阵。
标记下传时,让左右儿子的信息矩阵和懒标记矩阵同时乘上当前节点的懒标记矩阵。
可以看出,我们对于信息的修改就是乘上修改矩阵,而懒标记矩阵等同于所有未下传的修改乘积。
由于父亲节点的懒标记矩阵修改时间一定晚于儿子被遍历(否则直接下传了),矩阵乘法满足结合律,所以说乘上懒标记矩阵等同于乘上父亲所有未下传的修改。
修改矩阵很好推,这里不放了,可以看代码。
T4
T5
我们先构造一组特解
显然,每个人的位置的范围可以看做一条线段,每条线段覆盖一个点,要求每个点都被覆盖。
我们把线段按左端点排序,并对线段维护一个小根堆,堆按照线段右端点排序。
由于题目保证有解,我们从左到右遍历每个点,把以这个点为左端点的所有点加入堆,然后把堆顶拿出来覆盖这个点(因为右端点最小,留到后面不可能更优)。这样我们就有了一组特解。
我们继续找是否存在另一组解
显然,如果存在另一组解,一定存在一组解是由特解中交换两个点的线段得来的,这两个点的线段都能覆盖到另一个点。
因此,我们用 ST 表预处理出区间 \([l,r]\) 的点中右端点最大的线段所覆盖的点的位置,然后从左到右遍历每个点,看它的线段左端点到它之间,是否存在点满足该点线段可以覆盖到它,即在 ST 表上区间查询。这样我们保证每对点都被统计到。