[DataSturcture] 红黑树求逆序对

题目很简短，表达的意思就是求逆序对（常规做法有红黑树，平衡二叉树，离散化线段树，归并排序）
leetcode 493

typedef bool RankTreeNodeColor;

struct RankTreeNode
{
    RankTreeNode(int key, RankTreeNode *parent = nullptr, RankTreeNode *left = nullptr, RankTreeNode *right = nullptr) : key(key), left(left), right(right), parent(parent), color(true)
    {
        _size = 1;
        _cnt = 1;
    }
    RankTreeNodeColor color;             // 红黑树的颜色
    int _size;                           // 记录树的数量
    int key;                             // 存储的键
    int _cnt;                            // 数量
    RankTreeNode *left, *right, *parent; // 左右节点
    RankTreeNode *ToggleColor()
    {
        color ^= true;
        return this;
    }
};

class RankTree
{
private:
    RankTreeNode *root;
    // 更新子树的总节点数
    RankTree *updateSize(RankTreeNode *node)
    {
        node->_size = node->_cnt;
        if (node->left != nullptr)
        {
            node->_size += node->left->_size;
        }
        if (node->right != nullptr)
        {
            node->_size += node->right->_size;
        }
        return this;
    }
    RankTree *fixSize(RankTreeNode *node)
    {
        updateSize(node);
        if (node->parent != nullptr)
        {
            fixSize(node->parent);
        }
        return this;
    }
    // 左旋
    RankTree *rotateLeft(
        RankTreeNode *node)
    {
        if (node == nullptr)
            return this;
        auto right = node->right;
        node->right = right->left;
        if (right->left != nullptr)
            right->left->parent = node;
        right->left = node;
        updateSize(node)->updateSize(right);
        if (node->parent == nullptr)
        {
            root = right;
            node->parent = right;
            right->parent = nullptr;
        }
        else
        {
            if (node->parent->left == node)
                node->parent->left = right;
            else
                node->parent->right = right;
            right->parent = node->parent;
            node->parent = right;
        }
        return this;
    }
    // 右旋
    RankTree *rotateRight(
        RankTreeNode *node)
    {
        if (node == nullptr)
            return this;
        auto left = node->left;
        node->left = left->right;
        if (left->right != nullptr)
            left->right->parent = node;
        left->right = node;
        updateSize(node)->updateSize(left);
        if (node->parent == nullptr)
        {
            root = left;
            left->parent = nullptr;
        }
        else
        {
            if (node->parent->left == node)
                node->parent->left = left;
            else
                node->parent->right = left;
            left->parent = node->parent;
        }
        node->parent = left;
        return this;
    }
    // 自平衡
    RankTree *fixBalance(RankTreeNode *node)
    {
        node->color = true;
        while (node != nullptr && node != root && node->parent->color)
        {
            if (node->parent == node->parent->parent->left)
            {
                auto parent_brother = node->parent->parent->right;
                if (parent_brother == nullptr || !parent_brother->color)
                {
                    if (node == node->parent->right)
                    {
                        node = node->parent;
                        rotateLeft(node);
                    }
                    node->parent->color = false;
                    node->parent->parent->color = true;
                    rotateRight(node->parent->parent);
                }
                else
                {
                    node->parent->color = false;
                    parent_brother->color = false;
                    parent_brother->parent->color = true;
                    node = parent_brother->parent;
                }
            }
            else
            {
                auto parent_brother = node->parent->parent->left;
                if (parent_brother == nullptr || !parent_brother->color)
                {
                    if (node == node->parent->left)
                    {
                        node = node->parent;
                        rotateRight(node);
                    }
                    node->parent->color = false;
                    node->parent->parent->color = true;
                    rotateLeft(node->parent->parent);
                }
                else
                {
                    node->parent->color = false;
                    parent_brother->color = false;
                    parent_brother->parent->color = true;
                    node = parent_brother->parent;
                }
            }
        }
        root->color = false;
        return this;
    }

public:
    RankTree() : root(nullptr)
    {
    }
    RankTree(std::vector<int> &array) : root(nullptr)
    {
        for (int i = 0; i < array.size(); ++i)
        {
            emplace(array[i]);
        }
    }
    RankTree(std::vector<int> array) : root(nullptr)
    {
        for (int i = 0; i < array.size(); ++i)
        {
            emplace(array[i]);
        }
    }
    RankTreeNode *find(int key)
    {
        RankTreeNode *ptr = root;
        while (ptr != nullptr)
        {
            if (ptr->key == key)
                return ptr;
            if (ptr->key < key)
                ptr = ptr->left;
            else
                ptr = ptr->right;
        }
        return ptr;
    }
    RankTree *emplace(int key)
    {
        RankTreeNode *ptr = root;
        if (ptr == nullptr)
        {
            root = (new RankTreeNode(key))->ToggleColor(); // 创建黑色根节点
        }
        else
        {
            auto parent = ptr;
            while (ptr != nullptr)
            {
                parent = ptr;
                if (ptr->key < key)
                    ptr = ptr->right;
                else if (ptr->key > key)
                    ptr = ptr->left;
                else
                {
                    ptr->_cnt++;
                    fixSize(ptr);
                    return this;
                }
            }
            if (key <= parent->key)
            {
                parent->left = new RankTreeNode(key, parent);
                fixSize(parent)->fixBalance(parent->left);
            }
            else
            {
                parent->right = new RankTreeNode(key, parent);
                fixSize(parent)->fixBalance(parent->right);
            }
        }
        return this;
    }
    int getRank(long long key)
    {
        RankTreeNode *ptr = root;
        int rank = 0;
        while (ptr != nullptr)
        {
            if (ptr->key <= key)
            {
                ptr = ptr->right;
            }
            else
            {
                if (ptr->right != nullptr)
                {
                    rank += ptr->right->_size;
                }
                rank+= ptr->_cnt;
                ptr = ptr->left;
            }
        }
        return rank;
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        RankTree tree;
        int ans = 0;
        int n=nums.size();
        for (int i=0;i<n;++i){
            auto num = nums[i];
            ans+=tree.getRank(2ll*num);
            tree.emplace(num);
        }
        return ans;
    }
};