poj_3580 伸展树

自己伸展树做的第一个题 poj 3580 supermemo.

题目大意

对一个数组进行维护，包含如下几个操作：

ADD x, y, d 在 A[x]--A[y] 中的每个数都增加d

REVERSE x, y 将 A[x]--A[y] 中的数进行反转，变为 A[y],A[y-1]....A[x+1],A[x]

REVOLVE x, y, T 将 A[x]--A[y]中的数连续右移T次

INSERT x, P 在A后添加数P

DELETE x 删除A[x]

MIN x, y 查询A[x]--A[y]中的最小值

思路

对有序进行操作可选的数据结构有线段树、treap、伸展树Splay等，这道题要求比较多，所以选用伸展树：
    伸展树对数组进行维护的核心思想是，将需要维护的一组数单独提取出来，形成一棵子树（一般为整棵树的根节点的右子节点的左孩子节点为根），然后再这个子树上进行操作。此时进行某些操作（如 ADD, REVERSE 等），只需要在根节点上做个标记，进行延迟处理（即在之后真正访问子节点时候才对子节点进行实际的更新操作），这样可以节省时间。
    每次对树的节点进行修改（比如DELETE, INSERT等）之后，都要进行维护信息，此时需要Update一下，然后将该节点旋转至树根。
    且在寻找一个区间的起始点对应在树中的节点的时候，都要将该节点所需要的所有信息带给该节点，这就要求在从根节点向下寻找该节点的时候，将路径上的所有节点（即该节点的祖先节点）上的标记都往下传，即PushDown。

实现(c++)

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<string.h>

#define MIN(a,b) a<b? a:b

#define MAX_NODE_NUM 200005

#define INFINITE 1 << 30

struct TreeNode{

    int data;

    int parent;

    int child[2];

    int child_dir;

    //程序相关的信息

    bool reverse;

    int min;

    int lazy;

    int size;

    //节点的索引为0，表示该节点为无效节点。若节点的parent = 0， 表示该节点为根节点，若节点的子节点为0，表示没有相应的子节点

    TreeNode(int d = INFINITE) :

        data(d), parent(0), child_dir(0), reverse(false), min(INFINITE), lazy(0), size(1){

        child[0] = child[1] = 0;

    }

    void Reset(){

        parent = 0;

        child[0] = child[1] = 0;

        reverse = false;

        size = 1;

        lazy = 0;

        min = INFINITE;

    }

};

TreeNode gTreeNode[MAX_NODE_NUM];

int gNumber[MAX_NODE_NUM];

int gNodeCount;

int gRootIndex;

void LinkNode(int par, int ch, int dir){

    gTreeNode[par].child[dir] = ch;

    gTreeNode[ch].parent = par;

    gTreeNode[ch].child_dir = dir;

}

//维护本节点信息

void Update(int node){

    gTreeNode[node].min = gTreeNode[node].data;

    gTreeNode[node].size = 1;

    int left = gTreeNode[node].child[0], right = gTreeNode[node].child[1];

    if (left){

        gTreeNode[node].min = MIN(gTreeNode[node].min, gTreeNode[left].min);

        gTreeNode[node].size += gTreeNode[left].size;

    }

    if (right){

        gTreeNode[node].min = MIN(gTreeNode[node].min, gTreeNode[right].min);

        gTreeNode[node].size += gTreeNode[right].size;

    }

}

//向下更新信息

void PushDown(int node){

    int left = gTreeNode[node].child[0];

    int right = gTreeNode[node].child[1];

    if (gTreeNode[node].reverse){

        LinkNode(node, left, 1);

        LinkNode(node, right, 0);

        gTreeNode[left].reverse ^= true;

        gTreeNode[right].reverse ^= true;

        gTreeNode[node].reverse = false;

    }

    int tmp_add = gTreeNode[node].lazy;

    if (tmp_add){

        gTreeNode[node].data += tmp_add;

        gTreeNode[left].min += tmp_add;

        gTreeNode[left].lazy += tmp_add;

        gTreeNode[right].min += tmp_add;

        gTreeNode[right].lazy += tmp_add;

        gTreeNode[node].lazy = 0;

    }

}

int BuildTree(int beg, int end){

    if (beg > end){

        return 0;

    }

    if (beg == end){

        gTreeNode[gNodeCount].data = gTreeNode[gNodeCount].min = gNumber[beg];

        return gNodeCount++;

    }

    int mid = (beg + end) / 2;

    int left = BuildTree(beg, mid - 1);

    int right = BuildTree(mid + 1, end);

    gTreeNode[gNodeCount].data = gTreeNode[gNodeCount].min = gNumber[mid];

    LinkNode(gNodeCount, left, 0);

    LinkNode(gNodeCount, right, 1);

    Update(gNodeCount);

    return gNodeCount++;

}

//zig or zag旋转

void Rotate(int x){

    if (x == gRootIndex){

        return;

    }

    int y = gTreeNode[x].parent;

    PushDown(y);

    PushDown(x);

    int d = gTreeNode[x].child_dir;

    int z = gTreeNode[y].parent;

    LinkNode(z, x, gTreeNode[y].child_dir);

    LinkNode(y, gTreeNode[x].child[!d], d);

    LinkNode(x, y, !d);

    Update(y);

    if (y == gRootIndex){

        gRootIndex = x;

    }

}

//旋转操作，将node节点旋转到 f 节点下方

void Splay(int x, int f){

    if (x == f){

        return;

    }

    PushDown(x);

    int y = gTreeNode[x].parent, z = 0;

    while (y != f){

        z = gTreeNode[y].parent;

        if (z == f){

            Rotate(x);

            break;

        }

        if (gTreeNode[x].child_dir == gTreeNode[y].child_dir){ //一字型旋转

            Rotate(y);

            Rotate(x);

        }

        else{ //之字形旋转

            Rotate(x);

            Rotate(x);

        }

        y = gTreeNode[x].parent;

    }

    Update(x);

}

//获取伸展树中 第k个节点的index

int GetKthInTree(int k){

    int node = gRootIndex, left, tmp_size;

    while (node){

        PushDown(node); //注意要将与该节点有关的信息带下去

        left = gTreeNode[node].child[0];

        tmp_size = gTreeNode[left].size;

        if (!left){//left 为空节点

            if (k == 1){

                return node;

            }

            else{

                node = gTreeNode[node].child[1];

                k--;

                continue;

            }

        }

        if (tmp_size + 1 == k){

            return node;

        }

        else if (tmp_size >= k){

            node = left;

        }

        else{

            node = gTreeNode[node].child[1];

            k -= (tmp_size + 1);

        }

    }

    return -1;

}

//选择区间，返回由该区间构成的子树的节点。节点为 根节点的右子节点的左子节点

int SelectInterval(int x, int y){

    if (x <= 0 || y > gNodeCount){

        printf("fuck this splay tree!!!\n");

        return -1;

    }

    if (x == 1 && y == gNodeCount - 1){

        return gRootIndex;

    }

    int node;

    if (x == 1){

        node = GetKthInTree(y + 1);

        Splay(node, 0);

        return gTreeNode[node].child[0];

    }

    if (y == gNodeCount - 1){

        node = GetKthInTree(x - 1);

        Splay(node, 0);

        return gTreeNode[node].child[1];

    }

    int node_beg = GetKthInTree(x - 1);

    Splay(node_beg, 0);

    int node_end = GetKthInTree(y + 1);

    Splay(node_end, gRootIndex);

    return gTreeNode[node_end].child[0];

}

void Add(int x, int y, int d){

    int node = SelectInterval(x, y);

    gTreeNode[node].min += d;

    gTreeNode[node].lazy += d;

    Splay(node, 0);

}

void Reverse(int x, int y){

    int node = SelectInterval(x, y);

    gTreeNode[node].reverse ^= true;  //注意是 ^= 而不是 直接 = （因为两次反转相当于不进行反转）

    Splay(node, 0);

}

void Revolve(int x, int y, int k){

    int w = y - x + 1;

    k = (k % w + w) % w;

    if (k == 0){

        return;

    }

    int node = SelectInterval(x, y);

    PushDown(node);

    int p = gTreeNode[node].parent;

    int node_x = GetKthInTree(x);

    Splay(node_x, p);

    PushDown(node_x);

    int node_y_sub_k = GetKthInTree(y - k);

    Splay(node_y_sub_k, node_x);

    PushDown(node_y_sub_k);

    int node_tmp = gTreeNode[node_y_sub_k].child[1];

    LinkNode(node_x, node_tmp, 0);

    gTreeNode[node_y_sub_k].child[1] = 0;

    //注意，node_y_sub_k 发生了改变，因此要更新

    Update(node_y_sub_k);

    Splay(node_tmp, 0);

}

void Insert(int x, int t){

    int node = SelectInterval(x, x);

    gTreeNode[gNodeCount].data = t;

    //将节点的信息push down，否则，如果该节点的信息没有被清除，在插入新节点后，可能会对新节点产生影响（因为新节点在该节点下方）

    PushDown(node);

    LinkNode(node, gNodeCount, 1);

    Splay(gNodeCount, 0);

    gNodeCount++;

}

void Delete(int x){

    int node = SelectInterval(x, x);

    PushDown(gTreeNode[node].parent);

    gNodeCount--;

    int p = gTreeNode[node].parent;

    gTreeNode[p].child[gTreeNode[node].child_dir] = 0; //去掉父节点的子节点

    //这里更改了，node，会导致node的父节点的信息发生改变，因此要进行维护！！！！

    Update(p);

    Splay(p, 0);

    p = gTreeNode[gNodeCount].parent;

    int left = gTreeNode[gNodeCount].child[0];

    int right = gTreeNode[gNodeCount].child[1];

    if (node == gNodeCount){

        gTreeNode[gNodeCount].Reset();

        return;

    }

    gTreeNode[node] = gTreeNode[gNodeCount];

    LinkNode(p, node, gTreeNode[gNodeCount].child_dir);

    if (p == 0){

        gRootIndex = node;  //可能会对根部造成改变

    }

    LinkNode(node, left, 0);

    LinkNode(node, right, 1);

    gTreeNode[gNodeCount].Reset();

}

int GetMin(int x, int y){

    int node = SelectInterval(x, y);

    //获得节点之后，一定要进行更新！！！

    PushDown(node);

    Update(node);

    return gTreeNode[node].min;

}

void debug(int node){

    if (node){

        debug(gTreeNode[node].child[0]);

        printf("node %d, parent = %d, left = %d, right = %d, data = %d, min = %d, lazy = %d, reverse = %d\n",

            node, gTreeNode[node].parent, gTreeNode[node].child[0], gTreeNode[node].child[1],

            gTreeNode[node].data, gTreeNode[node].min, gTreeNode[node].lazy, gTreeNode[node].reverse);

        debug(gTreeNode[node].child[1]);

    }

}

int main(){

    int node_num;

    gNodeCount = 1;

    scanf("%d", &node_num);

    for (int i = 0; i < node_num; i++){

        scanf("%d", gNumber + i);

    }

    gRootIndex = BuildTree(0, node_num - 1); //递归的方式构造一棵开始就平衡的二叉树

    gTreeNode[gRootIndex].parent = 0; //根

    int query_num;

    scanf("%d", &query_num);

    char op[10];

    int x, y, tmp;

    for (int i = 0; i < query_num; i++){

//        debug(gRootIndex);

        scanf("%s", op);

        if (strcmp(op, "ADD") == 0){

            scanf("%d%d%d", &x, &y, &tmp);

            Add(x, y, tmp);

        }

        else if (strcmp(op, "REVERSE") == 0){

            scanf("%d%d", &x, &y);

            Reverse(x, y);

        }

        else if (strcmp(op, "REVOLVE") == 0){

            scanf("%d%d%d", &x, &y, &tmp);

            Revolve(x, y, tmp);

        }

        else if (strcmp(op, "INSERT") == 0){

            scanf("%d%d", &x, &tmp);

            Insert(x, tmp);

        }

        else if (strcmp(op, "DELETE") == 0){

            scanf("%d", &x);

            Delete(x);

        }

        else if (strcmp(op, "MIN") == 0){

            scanf("%d%d", &x, &y);

            printf("%d\n", GetMin(x, y));

        }

        /*

        for (int i = 1; i < gNodeCount; i ++){

            printf("%d ", GetMin(i, i));

        }

        printf("\n\n");

        */

    }

    return 0;

}

巴特西

poj_3580 伸展树

题目大意

思路

实现(c++)

最新文章

热门文章