题目：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;}
};