计数 "minimal" 个值

Question

问题：

我有 n 个向量的输入：

(x, y, z): x ∈ {1..n},y ∈ {1..n},z ∈ {1..n} (every "dimension" is set(1..n))
*I mean that in one vector x,y,z can be the same(x=y=z),
 but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2

v1>v2 if and only if x1>x2,y1>y2,z1>z2. 
lets denote vector v1 "minimal" if and only if ∄v ∈ input: v>v1

任务是计算输入中的最小向量。

来源：

我在本地编程大赛的任务中发现了这个问题

（翻译的）公式是：

n people participeted in competion. competion had three phases(every competitor 
took part in every stage). denote that the participant is better then 
participant b, if a ranks in all three stages is higher then participant b ranks. 
participant c is the best, if there is no such participant who is better 
than participant c. output the number of best participants.

1<=n<=100000 时限：1秒

我的尝试与想法

第一个想法是创建 class 结果（对于竞争对手的结果），重载运算符 >（或 <），就像：

bool operator > (const Score &s) const
{
    if (first_result > s.first_result)
        if (second_result > s.second_result)
            return third_result > s.third_result;
    return false;
}

并构建任何基于数组的数组（例如最小堆），它允许找到最小值（使用 <）并计算它们（我想我只是按照这种方式“重新创建”了堆排序的一个坏变体).这次尝试失败后，我尝试使用 Fenwick 树（二叉索引树）来完成相同的任务。

但后来我明白我的方法是不正确的（不行 class 和 < 过载）并且 mb 将任务转换为 1d 的想法一点也不好。

然后我找到了一些关于 n 维情况下的 BIT 和线段树的信息，我认为我可以用它们来解决这个问题。但是我很难实现工作变体（甚至在超过 1d 的情况下理解线段树的工作原理）

也许有人可以帮助实施（或找到更好的解决方案并解释）？

Answer 1

我的想法：

struct Point {
    int x;
    int y;
    int z;
};

bool operator < (const Point& lhs, const Point& rhs) {
    return std::tie(lhs.x, lhs.y, lhs.z) < std::tie(rhs.x, rhs.y, rhs.z);
}

bool dominate(const Point& lhs, const Point& rhs) {
    return lhs.x < rhs.x && lhs.y < rhs.y && lhs.z < rhs.z;
}

然后：

std::vector<Point> res;
const std::vector<Point> points = {...};

std::sort(points.begin(), points.end());

for (const auto& p : points) {
    if (!std::any_of(res.begin(), res.end(), [](const auto& m) { return dominate(m, p);})) {
        res.push_back(p);
    }
}
return res.size();

复杂度仍然是最坏情况n²。（目前是max(n log n, res.size() * n)）

Answer 2

首先，我们需要一个有序的key/value数据结构，您可以插入，删除，并及时找到prev/last小于或等于您自己的值O(log(n)) .想想 red-black 树或 btree 或跳过列表。

我将为该数据结构使用以下发明的表示法。我故意让它看起来不像任何真正的语言。

by_order.prev(key) 给出与最大键 <= 关联的 k-v 对 key。 by_order.prev(key).k 给出最大的键 <= 到 key。这可以是 None。 by_order.prev(key).v 给出与最大键 <= 关联的值到 key。 by_order.next(key) 给出与最小键关联的 k-v 对 >= 到 key，其中 .k 和 .v 表示他们之前所做的。 by_order.add(key, value) 添加 k-v 对。 by_order.del(key) 删除值为 key 的 k-v 对。

思路是这样的。我们首先按 x 然后 y 然后 z 排序。第一个向量是最小的。如果其 z 的值小于任何先前具有小于或等于 y 的元素的最低值 z，则此后的每个向量都是最小的。我们将使用 by_order 数据结构来测试该条件。

假设我没有出错，这里是伪代码：

sort(vectors) by x then y then z
Declare and initialize your empty ordered data structure by_order
// NOTE: by_order[val] will be the value of the largest key <= val
answer = [] // ie an empty list
answer.push(vectors[0])
by_order.add(vectors[0].y, by_order[vectors[0].z)
for v in vectors:
    z_best = by_order.prev(v.y).v
    if z_best is None or v.z < z_best:
        answer.push(v) // Yay!
        // Clear anything in by_order that we are an improvement on
        while True:
            pair = by_order.next(v)
            if pair.v is not none and pair.k < v.z:
                by_order.del(pair.v)
            else:
                break
        // and now we add this one to by_order.
        by_order.add(v.y, v.z)

排序的总时间为 O(n log(n))。

后跟每个 n 向量 O(log(n)) 查找以查看是否插入它，可能后跟 O(1) 插入到答案中， O(log(n))查找仍然跟随它的内容（别担心，我没有忘记被删除的那些），然后是 O(log(n)) 插入，然后是 O(log(n)) 检查发现这个需要被删除，然后是 O(log(n)) 删除。

这是很多 O(log(n)) 项，但总和仍然是 O(log(n))。 n 次。

结果是整个问题的 O(n log(n)) 算法。

计数 "minimal" 个值

Count "minimal" values

c++

algorithm

data-structures

segment-tree

binary-indexed-tree

问题：

来源：

我的尝试与想法