[ROIR 2018 Day2] 大数据处理 题解
MightZero
·
·
题解
原问题直接做显然是不好处理的，考虑做如下转化：给定一个指定的内存段（即题目条件中 c_i,v_i 所表示的内存段），每次选择一个所有元素都相同的合法序列并修改整个序列为某个值，求将整个内存段修改为全 0 的最小操作次数。由于修改为 0 在最优方案中必然是在最后一步修改整个内存段，因此只需要考虑将将整个内存段所有元素修改为相同值所需要的最小操作次数。
注意到题目给出的合法区间本质上可以看作一棵范围 [0,2^k-1] 的线段树的某个节点，考虑建线段树；但是树的深度比较大，需要动态开点。建树时将每个 c_i,v_i 对应的区间插入线段树即可。
对于每个线段树上的节点，可以维护一个集合 S_x 表示在最优操作次数下将当前节点对应区间所有元素修改为相同值时，这一相同值所有可能的取值；
遍历整棵线段树，考虑如何合并节点的左右儿子的 S_x：
-
若 S_{lson} \cap S_{rson} = \emptyset，那么必须修改其中一个儿子对应区间的值才能满足条件，此时将 ans+1；由于可以将一个儿子的值修改为另一个儿子取值集合中的任意元素，最终可能的取值集合 S_x = S_{lson} \cup S_{rson}
-
若 S_{lson} \cap S_{rson} \neq \emptyset，此时不需要修改，ans 不变，S_x = S_{lson} \cap S_{rson}。
说明：若某个节点 x 处 S_{lson_x} \cap S_{rson_x} \neq \emptyset，这个节点的儿子可以修改也可以不修改；但是本题中需要考虑的是最小操作次数，如果这一结点的某个祖先 x' 处必须修改，即 S_{lson_{x'}} \cap S_{rson_{x'}} = \emptyset，注意到在 x' 处修改儿子对于在 x 处修改儿子是必然不劣的，因此只在必须修改的时候修改儿子可保证答案最优。
具体实现上可以使用 std::set 或者 std::vector 维护集合，输出 ans 时记得 +1。