带有更新的MEX查询 [英] MEX queries with updates

问题描述

给出长度为 n （<== 500000）的数组 A 。

A [ i ]< = 10 ^ 9。

有 q （< = 50000 ）两种查询：

1. 给出 l r -找到最小的正数在[ l ， r ]范围内不以A表示的整数-Mex-（
   
   
   

   我们可以看到从上图可以看出，叶节点保存着特定的数组索引值，内部节点从其左，右子级值（ min（左子级的最小值，右子级的最小值））。在此细分中，我们可以找到 O（logn）中任意范围的最小值。如果任何数组索引值发生变化，我们可以在 O（logn）中更新树。

   
   
   

   对于答案为（范围的最大值）+1的情况：

   
   
   

   为此，我们建立了一个细分，以查找该特定范围内的最大值。它类似于上面的段树，而不是找到最小值，而是找到最大值。

   
   
   

   对于答案既不是1也不是（最大值为范围）+1：

   
   
   

   在这种情况下，我们需要一个细分树，该树将给出最小的正缺失值，该正值大于该范围的最小值 [l，r] ，并且小于范围 [l，r] 的最大值。
   我们将使用值 0 表示此范围 [l，r] 没有缺失值。
   对于叶节点，我们将缺失值设置为 0 。
   现在我们将如何计算内部节点的缺失值。
   假设对于内部节点 P ，我们将计算缺失值。 P 的左孩子 L 和右孩子 R 。
   P 的缺失值将使用以下过程进行计算：

     P.Missing_Value =无限值
    //对于情况L = {1,2}，R = {4,5} 
   如果L.Max_Value + 1< R.Min_Value {
    P.Missing_Value = min（P.Missing_Value，L.Max_Value + 1）
   } 
    
    //对于情况L = {4,5}，如果R.Max_Value + 1< R = {1,2} 
    L.Min_Value {
    P.Missing_Value = min（P.Missing_Value，R.Max_Value + 1）
   } 
    
    //对于情况L = {1,3}， R = {1,3,4,5}或L = {1,3}，R = {4,5}或L = {3,5}，如果L则R = {1,2} 
   。 Missing_Value！= 0&& （L.Missing_Value< R.Min_Value || L.Missing_Value> R.Max_Value || L.Missing_Value == R.Missing_Value）{
    P.Missing_Value = min（P.Missing_Value，L.Missing_Value）
   } 
    
    //对于情况R = {1,3}，L = {1,3,4,5}或R = {1,3}，L = {4， 5}或R = {3,5}，如果R.Missing_Value！= 0&&，则L = {1,2} 
    （R.Missing_Value< L.Min_Value || R.Missing_Value> L.Max_Value || R.Missing_Value == L.Missing_Value）{
    P.Missing_Value = min（P.Missing_Value，R.Missing_Value）
   } 
    
    //如果没有缺失值
   如果P.Missing_Value ==无限{
    P.Missing_Value = 0 
   } 
     

   
   
   

   最后确定

   
   
   1. 首先检查ans是否可以为1。
   
   
   2. 如果ans不能为1，然后检查缺失值。
   
   
   3. 如果未找到缺失值，则ans将为最大值+1。
   
   

   在树的上方将是您的最终细分树。从中可以查询任何范围的最小值，最大值和缺失值。这些查询和更新（如果数组索引值更改）将花费 O（logn）。

   
   
   

   某些教程/资源关于段树：

   
   
   
   
   
   • > https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/
   
   
   • https://cp-algorithms.com/data_structures/ segment_tree.html
   
   
   
   

   Given an array A of length n(<= 500000).

   A[i] <= 10^9.

   There's q(<= 50000) queries of 2 types:

   1. Given l r - find the smallest positive integer number which is not presented in A in range [l, r] - Mex - (https://en.wikipedia.org/wiki/Mex_(mathematics)).
   2. Given i x - change value of A[i] to x.

   Naive O(n) for query and O(1) for update is too slow - O(n^2) in general.

   Can you come up with efficient algorithm/data structure to solve this problem?

   解决方案

   You can use Segment tree data structure and complexity will be O(nlogn + qlogn).If you are not familiar with Segment tree than it's better to gather knowledge about it. You will find plenty of resouces about it in online.

   In Segment tree generally each node keeps information about a specific range. Normally, leaf node keeps information about specific array index and internal node generates or updates informatin from his left and right child.

   Consider these cases for the smallest positive integer number which is not presented in A in range [l, r]:

   1. For {2,3} answer is 1 (1 is the smallest positive integer).
   2. for {1,2} answer is 3
   3. for {1,4,2} answer is 3

   For the case where answer is 1:

   If minimum value in the range is greater than 1, then answer is 1. For this build a segment to find what is minimum value in this specific range. See figure below:

   As we can see from above figure, leaf node holds the specific array index value and internal node updates it's value from it's left and right child value(min(left child's min value, right child's min value)). From this segment we can find minimum value for any range in O(logn). If any array index value changes, we can update the tree in O(logn).

   For the case where answer is (max of the range)+1:

   For this build a segment to find what is maximum value in this specific range. It is similar to above segment tree, instead of finding minimum value we are gonna find maximum value.

   For the case where answer is neither 1 nor (max of the range)+1:

   For this case we will need a segment tree that will give smallest missing positive value that is greater than minimum value of the range [l,r] and less than maximum value of the range [l,r]. We will use value 0 to represent there is no missing value for this range [l,r]. For leaf node we will set missing value to 0. Now how we will compute missing value for internal node. Let's say for a internal node P we are gonna calculate the missing value. P has left child L and right child R. Missing value for P will be calculated using following procedure:

   P.Missing_Value = infinite value
   // for the case L = {1,2} , R = {4,5}
   if L.Max_Value+1 < R.Min_Value {
     P.Missing_Value = min(P.Missing_Value, L.Max_Value + 1)
   }
   
   // for the case L = {4,5} , R = {1,2}
   if R.Max_Value+1 < L.Min_Value {
     P.Missing_Value = min(P.Missing_Value, R.Max_Value + 1)
   }
   
   // for the case L = {1,3} , R = {1,3,4,5} or L = {1,3} , R = {4,5} or L = {3,5} , R = {1,2}
   if L.Missing_Value != 0 && (L.Missing_Value < R.Min_Value || L.Missing_Value > R.Max_Value || L.Missing_Value == R.Missing_Value) {
     P.Missing_Value = min(P.Missing_Value, L.Missing_Value)
   }
   
   // for the case R = {1,3} , L = {1,3,4,5} or R = {1,3} , L = {4,5} or R = {3,5} , L = {1,2}
   if R.Missing_Value != 0 && (R.Missing_Value < L.Min_Value || R.Missing_Value > L.Max_Value || R.Missing_Value == L.Missing_Value) {
     P.Missing_Value = min(P.Missing_Value, R.Missing_Value)
   }
   
   // if there is no missing value
   if P.Missing_Value == infinite {
     P.Missing_Value = 0
   }
   

   To finalize

   1. First check whether ans could be 1.
   2. If ans can not be 1, then check missing value.
   3. If missing value not found, then ans will max value + 1.

   Above tree will be your final segment tree. From this you can query min, max and missing value for any range. These query and update(if array index value changes) will take O(logn).

   Some Tutorial/Resoure about segment tree:

   • https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/
   • https://cp-algorithms.com/data_structures/segment_tree.html

   这篇关于带有更新的MEX查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！