leetcode 1649. 通过指令创建有序数组

题目：1649. 通过指令创建有序数组 - 力扣（LeetCode）

经典线段树问题

struct Node {
    Node* lc = nullptr;
    Node* rc = nullptr;
    int l;
    int r;
    int v = 0;
    Node(int l, int r) {
        this->l = l;
        this->r = r;
    }
    ~Node() {
        if (lc) {
            delete lc;
        }
        if (rc) {
            delete rc;
        }
    }
};
class Solution {
public:
    static const int MAX = 1000000007;
    void BuildTree(Node* node) {
        int l = node->l;
        int r = node->r;
        if (l == r) {
            return;
        }
        int m = (l + r) / 2;
        node->lc = new Node(l, m);
        node->rc = new Node(m + 1, r);
        BuildTree(node->lc);
        BuildTree(node->rc);
    }
    int Sum(Node* t, int l, int r) {
        if (l <= t->l && r >= t->r) {
            return t->v;
        }
        if (l > t->r || r < t->l) {
            return 0;
        }
        int64_t ret = 0;
        if (l <= t->lc->r) {
            ret += Sum(t->lc, l, r);
        }
        if (r >= t->rc->l) {
            ret += Sum(t->rc, l, r);
        }
        if (ret >= MAX) ret %= MAX;
        return (int) ret;
    }
    void Add(Node* t, int p) {
        if (p >= t->l && p <= t->r) {
            ++t->v;
            if (t->lc && p <= t->lc->r) {
                Add(t->lc, p);
                return;
            }
            if (t->rc && p >= t->rc->l) {
                Add(t->rc, p);
            }
        }
    }
    int createSortedArray(vector<int>& instructions) {
        if (instructions.size() <= 2) {
            return 0;
        }
        size_t n = instructions.size();
        int limL = instructions[0];
        int limR = instructions[0];
        for (int i = 0; i < n; i++) {
            int val = instructions[i];
            if (val < limL) limL = val;
            if (val > limR) limR = val;
        }
        Node* root = new Node(limL, limR);
        BuildTree(root);
        
        int64_t ret = 0;
        int64_t ls, rs;
        int min = instructions[0];
        int max = instructions[0];
        for (int i = 0; i < n; i++) {
            int val = instructions[i];
            if (val < min) {
                min = val;
                Add(root, val);
                continue;
            }
            if (val > max) {
                max = val;
                Add(root, val);
                continue;
            }
            if (val > limL) {
                ls = Sum(root, limL, val - 1);
            } else {
                ls = 0;
            }
            if (val < limR) {
                rs = Sum(root, instructions[i] + 1, limR);
            } else {
                rs = 0;
            }
            if (ls <= rs) {
                ret += ls;
            } else {
                ret += rs;
            }
            if (ret >= MAX) ret %= MAX;
            Add(root, val);
        }
        
        delete root;
        return (int) ret;
    }
};