进行许多子串反转的算法？

Question

假设我有一个长度为N的字符串S，我想执行以下M个操作：

选择 1 <= L,R <= N 并反转子串 S[L..R]

我对所有 M 操作后最终字符串的样子很感兴趣。显而易见的方法是进行实际的交换，这会导致 O(MN) 最坏情况的行为。有没有更快的方法？我只是想跟踪索引结束的位置，但我找不到减少运行时间的方法（尽管我有一种直觉 O(M lg N + N) -- 对于操作和最终阅读 -- 是可能的）。

Answer 1

是的，这是可能的。制作一个像

这样的二叉树结构

struct node {
    struct node *child[2];
    struct node *parent;
    char label;
    bool subtree_flipped;
};

然后你可以有一个合乎逻辑的 getter/setter for left/right child:

struct node *get_child(struct node *u, bool right) {
    return u->child[u->subtree_flipped ^ right];
}

void set_child(struct node *u, bool right, struct node *c) {
    u->child[u->subtree_flipped ^ right] = c;
    if (c != NULL) { c->parent = u; }
}

旋转必须保留翻转的位：

struct node *detach(struct node *u, bool right) {
    struct node *c = get_child(u, right);
    if (c != NULL) { c->subtree_flipped ^= u->subtree_flipped; }
    return c;
}

void attach(struct node *u, bool right, struct node *c) {
    set_child(u, right, c);
    if (c != NULL) { c->subtree_flipped ^= u->subtree_flipped; }
}

// rotates one of |p|'s child up.
// does not fix up the pointer to |p|.
void rotate(struct node *p, bool right) {
    struct node *u = detach(p, right);
    struct node *c = detach(u, !right);
    attach(p, right, c);
    attach(u, !right, p);
}

实施 splay 轮换。它应该采用一个 "guard" 指针，该指针被视为 NULL parent 用于展开目的，这样您就可以将一个节点展开到根，另一个节点展开到它的右边 child.这样做，然后你可以展开翻转区域的两个端点，然后切换根的翻转位和对应于不受影响的段的两个子树。

遍历是这样的。

void traverse(struct node *u, bool flipped) {
    if (u == NULL) { return; }
    flipped ^= u->subtree_flipped;
    traverse(u->child[flipped], flipped);
    visit(u);
    traverse(u->child[!flipped], flipped);
}

Answer 2

Splay tree可以帮到你，支持对数组进行逆向运算，总复杂度O(mlogn)

Answer 3

@F。 Ju 是对的，splay 树是实现您目标的最佳数据结构之一。

但是，如果您不想实现它们，或者 O((N + M) * sqrt(M)) 中的解决方案就足够了，您可以执行以下操作：

我们将执行 sqrt(M) 次连续查询，然后在 O(N) 时间内从头开始重建数组。

为了做到这一点，对于每个查询，我们将存储查询段 [a, b] 是否被反转的信息（如果你将某个范围的元素反转两次，它们将变为未反转）。

这里的关键是在这里维护不相交段的信息。请注意，由于我们在重建数组之前最多执行 sqrt(M) 个查询，因此我们将最多有 sqrt(M) 个不相交的段，我们可以在 sqrt(M) 时间内对 sqrt(M) 个段执行查询操作。如果您需要详细解释如何 "reverse" 这些不相交的片段，请告诉我。

这个技巧在解决这类问题时非常有用，值得学习。

更新：

在他们的比赛中，我使用我描述的方法解决了与您在 HackerRank 上的问题完全对应的问题。

这是problem

这是 C++ 中的 my solution。

这是the discussion about the problem和我的方法的简要说明，请查看我的第3条消息。

Answer 4

I'm trying to just keep track of where an index ends up

如果您只是想跟踪起始数组的一个条目，则很容易在 O(M) 时间内完成。

我本来打算只写伪代码，但不需要手动操作，所以我最终得到了可能有效的 C++。

// untested C++, but it does compile to code that looks right.
struct swap {
    int l, r;
    // or make these non-member functions for C
    bool covers(int pos) { return l <= pos && pos <= r; }
    int apply_if_covering(int pos) {
        // startpos - l = r - endpos;
        // endpos = l - startpos + r
        if(covers(pos))
            pos = l - pos + r;
        return pos;
    }
};

int follow_swaps (int pos, int len, struct swap swaps[], int num_swaps)
{
    // pos = starting position of the element we want to track
    // return value = where it will be after all the swaps
    for (int i = 0 ; i < num_swaps ; i++) {
        pos = swaps[i].apply_if_covering(pos);
    }
    return pos;
}

编译为 very efficient-looking code。

进行许多子串反转的算法？

Algorithm for doing many substring reversals?

string

algorithm

substring