确定最长的偶然子序列

Question

沿 a 有 N 个节点 （1 <= N <= 100,000） 个不同的位置长一维长度。 第 i 个节点位于位置 x_i （一个0...1,000,000,000 范围内的整数），节点类型为 b_i（整数范围 1..8）。节点不能处于同一位置

您希望在此一维上获取一个范围，其中所有类型的节点都得到了公平的表示。因此，您希望确保对于范围中存在的任何类型的节点，每种节点类型的数量相等（例如，类型 1 和 3 各有 27 个的范围是可以的，类型 1、3 和 4 中各有 27 个范围是好的，但是类型 9 的 1 和类型 10 的 3 是不行的）。你还想要至少 K （K>= 2） 种类型（共 8 种）要在兰特。查找满足约束的此范围的最大大小。 照片的大小是照片中节点的最大和最小位置之间的差异。

如果没有满足约束的范围，则改为输出 -1。

INPUT:
* Line 1: N and K separated by a space
* Lines 2..N+1: Each line contains a description of a node as two
        integers separated by a space; x(i) and its node type.
INPUT:
9 2  
1 1  
5 1  
6 1  
9 1  
100 1  
2 2  
7 2  
3 3  
8 3     
INPUT DETAILS:  
Node types: 1 2 3 - 1 1 2 3 1  - ...  -   1  
  Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100
OUTPUT:
* Line 1: A single integer indicating the maximum size of a fair
       range. If no such range exists, output -1.
OUTPUT:
6
OUTPUT DETAILS:
The range from x = 2 to x = 8 has 2 each of types 1, 2, and 3. The range
from x = 9 to x = 100 has 2 of type 1, but this is invalid because K = 2
and so you need at least 2 distinct types of nodes.

您能否帮助建议一些算法来解决此问题。我考虑过使用某种优先级队列或堆栈数据结构，但真的不确定如何进行。

谢谢，托德

Answer 1

发明几乎线性时间算法并不难，因为最近在CodeChef上讨论了类似的问题："ABC-Strings"。

1. 按节点位置对节点进行排序。
2. 准备节点类型的所有可能子集（例如，我们可以期望类型1,2,4,5,7在结果间隔中存在，而所有其他类型不存在）。对于 K=2，可能只有 256-8-1=247 个子集。对于每个子集，执行剩余步骤：
3. 将 8 个类型计数器初始化为 [
0,0,0,0,0,0,0,0,0]。
4. 对于每个节点，执行剩余步骤：
5. 当前节点类型的增量计数器。
6. 获取当前子集中包含的类型的L计数器，首先从其他L-1计数器中减去其中的计数器，这将生成L-1值。取剩余的8-L计数器，并将它们与这些L-1值组合成一个包含 7 个值的元组。
7. 使用此元组作为哈希映射的键。如果哈希映射不包含此键的值，请添加一个新条目，其键和值等于当前节点的位置。否则，从当前节点的位置减去哈希映射中的值并（可能）更新最佳结果。