andyli

题解 UVA11922 【Permutation Transformer】
用文艺平衡树($Splay$)来表示整个序列,则“截取出序列并放到序列末尾”的操作是不难实现的。如何实现文艺平衡树...
扫描右侧二维码阅读全文
22
2019/07

题解 UVA11922 【Permutation Transformer】

用文艺平衡树($Splay$)来表示整个序列,则“截取出序列并放到序列末尾”的操作是不难实现的。如何实现文艺平衡树的“翻转”呢?可以用类似线段树一样的标记来完成。给结点增加一个$flip$标记(表示以本结点为根的子树有没有旋转过),可以写出$pushdown$函数,代码如下:

void pushdown()
{
    if (flip) {
        flip = 0;
        swap(ch[0], ch[1]);
        ch[0]->flip = !ch[0]->flip;
        ch[1]->flip = !ch[1]->flip;
    }
}

注意要加一个哨兵结点。完整代码如下:

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 100005;

struct Node {
    Node* ch[2];
    int v, s, flip;
    void maintain() { s = ch[0]->s + ch[1]->s + 1; }
    void pushdown()
    {
        if (flip) {
            flip = 0;
            swap(ch[0], ch[1]);
            ch[0]->flip = !ch[0]->flip;
            ch[1]->flip = !ch[1]->flip;
        }
    }
    int cmp(int k) const
    {
        int d = k - ch[0]->s;
        if (d == 1)
            return -1;
        return d <= 0 ? 0 : 1;
    }
} * root, seq[maxn];

Node* null = new Node();
int cnt;
void rotate(Node*& o, int d)
{
    Node* k = o->ch[d ^ 1];
    o->ch[d ^ 1] = k->ch[d];
    k->ch[d] = o;
    o->maintain();
    k->maintain();
    o = k;
}

Node* build(int s)
{
    if (!s)
        return null;
    Node *L = build(s / 2), *o = &seq[++cnt];
    o->v = cnt;  // 节点编号
    o->ch[0] = L;
    o->ch[1] = build(s - s / 2 - 1);
    o->flip = o->s = 0;
    o->maintain();
    return o;
}

void splay(Node*& o, int k)
{
    o->pushdown();
    int d = o->cmp(k);
    if (d == 1)
        k -= o->ch[0]->s + 1;
    if (d != -1) {
        Node* p = o->ch[d];
        p->pushdown();
        int d2 = p->cmp(k);
        int k2 = (!d2 ? k : k - p->ch[0]->s - 1);
        if (d2 != -1) {
            splay(p->ch[d2], k2);
            if (d == d2)
                rotate(o, d ^ 1);
            else
                rotate(o->ch[d], d);
        }
        rotate(o, d ^ 1);
    }
}

// 合并left和right。假定left的所有元素比right小。注意right可以是null,但left不可以
Node* merge(Node* left, Node* right)
{
    splay(left, left->s);
    left->ch[1] = right;
    left->maintain();
    return left;
}

// 把o的前k小结点放在left里,其他的放在right里。1<=k<=o->s。当k=o->s时,right=null
void split(Node* o, int k, Node*& left, Node*& right)
{
    splay(o, k);
    left = o;
    right = o->ch[1];
    o->ch[1] = null;
    left->maintain();
}
vector<int> ans;
void getans(Node* o)
{
    if (o != null) {
        o->pushdown();
        getans(o->ch[0]);
        ans.push_back(o->v);
        getans(o->ch[1]);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    root = build(n + 1); // 最前面有一个哨兵结点
    null->s = 0;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        Node *left, *mid, *right, *o;
        split(root, a, left, o);  // 如果没有哨兵结点,a将改成a-1,违反split的限制
        split(o, b - a + 1, mid, right);
        mid->flip ^= 1;
        root = merge(merge(left, right), mid);
    }
    getans(root);
    for (size_t i = 1; i < ans.size(); i++)
        printf("%d\n", ans[i] - 1); // 节点编号减1才是真正的值
    return 0;
}
Last modification:November 6th, 2019 at 05:07 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment