almost 2 years ago

前言

C题挺有意思的。

C

给定一个长度为的序列,次操作,操作有两种:
(1) 1 left right flag 代表将区间升序或降序排序;
(2) 2 left right 询问区间的乘积的最高位。

首先考虑区间积可以化成,维护了的和即可知道乘积的最高位。
考虑怎么排序,我们可以对每个单调的连续子序列用动态开点权值线段树维护,排序时把边界上的区间分裂出来,然后直接线段树合并,询问的时候考虑用set维护每个连续子序列的左端点,用BIT维护前缀和,询问的时候特殊考虑一下左右两边然后BIT直接询问区间和即可。
分析一下分裂合并的复杂度,设线段树的总边数为,那么每次分裂最多加条边,那么所有操作总的加入边数不会超过,考虑线段树合并如果遍历到了一个节点那么必定会减少一条边,删除的边不会超过加入的边数,因此可以保证复杂度
Philosopher.cpp

← 2016-7-7 模拟题 C(n,m) mod M →
 
comments powered by Disqus