#define INF 0x3f3f3f3f
#define ls (root << 1)
#define rs (root << 1 | 1)
// 区间查最值
class SegTree {
private:
    // 本题没有更新update操作
    // 不用lazy
    struct Node {
        int val;
        // int lazy;
    };
    vector<Node> tree;
    vector<int> arr;
    int n;

public:
    SegTree(vector<int>& arr, int n) {
        this->n = n;
        this->arr = arr;
        this->tree.resize(n * 4);
    }

    void pushUp(int root) {
        tree[root].val = max(tree[ls].val, tree[rs].val);
    }

    void build(int root, int left, int right) {
        if (left == right) {
            tree[root].val = arr[left];
            return ;
        }

        int mid = (right - left) / 2 + left;
        build(ls, left, mid);
        build(rs, mid + 1, right);
        pushUp(root);
    }

    // 查询最大值，默认无效返回无穷小
    int query(int root, int left, int right, int from, int to) {
        if (from > right || to < left) {
            return -INF;
        }
        if (from <= left && right <= to) {
            return tree[root].val;
        }

        // 本题没有更新update操作
        // 不用pushDown
        int mid = (right - left) / 2 + left;
        return max(
            query(ls, left, mid, from, to),
            query(rs, mid + 1, right, from, to)
        );
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        const int n = nums.size();
        // [0, n - 1] -> [1, n]
        nums.insert(nums.begin(), 0);

        SegTree tree(nums, n);
        tree.build(1, 1, n);

        vector<int> ans;
        for (int i = 1; i + k - 1 <= n; i += 1) {
            ans.push_back(tree.query(1, 1, n, i, i + k - 1));
        }

        return ans;
    }
};

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

#define ls (root << 1)
#define rs (root << 1 | 1)
using ll = long long;

class SegTree {
private:
    int n;
    vector<int> tree;

public:
    SegTree(int n) : n(n), tree(n * 4) {}

    void pushUp(int root) {
        tree[root] = tree[ls] + tree[rs];
    }

    // 单点加权
    // 没有lazy，没有pushDown
    void update(int root, int left, int right, int pos, int val) {
        if (pos < left || pos > right) {
            return ;
        }
        // 长度为1的单点
        if (pos <= left && right <= pos) {
            tree[root] += val;
            return ;
        }

        int mid = (right - left) / 2 + left;
        update(ls, left, mid, pos, val);
        update(rs, mid + 1, right, pos, val);
        pushUp(root);
    }

    int query(int root, int left, int right, int from, int to) {
        if (from > right || to < left) {
            return 0;
        }
        if (from <= left && right <= to) {
            return tree[root];
        }

        int mid = (right - left) / 2 + left;
        return query(ls, left, mid, from, to) + 
            query(rs, mid + 1, right, from, to);
    }

public:
    void update(int pos, int val) {
        update(1, 1, n, pos, val);
    }

    int query(int left, int right) {
        return query(1, 1, n, left, right);
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        
        //! [前缀和]
        vector<ll> pre(n + 1);
        for (int i = 1; i <= n; i += 1) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        //! [前缀和]

        //! [离散化]
        // 去重 + 排序
        set<ll> st;
        for (auto x : pre) {
            st.insert(x);
            st.insert(x - upper);
            st.insert(x - lower);
        }
        // 离散化的映射数组 [1, n]从1开始
        unordered_map<ll, int> index;
        for (int idx = 1; auto x : st) {
            index[x] = idx;
            idx += 1;
        }
        //! [离散化]

        //! 利用线段树做计数缓存
        SegTree tree(index.size());
        int ans = 0;
        for (auto x : pre) {
            int left = index[x - upper];
            int right = index[x - lower];

            ans += tree.query(left, right);
            tree.update(index[x], 1);
        }

        return ans;
    }
};

#define ls (root << 1)
#define rs (root << 1 | 1)
class SegTree {
private:
    vector<int> tree;   // 记录下标
    vector<int> arr;
    int n;

public:
    SegTree() = default;
    SegTree(vector<int>& arr, int n) {
        this->n = n;
        this->arr = arr;
        this->tree.resize(n * 4);
    }

    void pushUp(int root) {
        if (arr[tree[ls]] > arr[tree[rs]]) {
            tree[root] = tree[ls];
        } else {
            tree[root] = tree[rs];
        }
    }

    void build(int root, int left, int right) {
        if (left == right) {
            tree[root] = left;
            return ;
        }

        int mid = (right - left) / 2 + left;
        build(ls, left, mid);
        build(rs, mid + 1, right);
        pushUp(root); 
    }

    // 注意，返回的是下标
    int query(int root, int left, int right, int from, int to) {
        if (to < left || from > right) {
            return -1;
        }
        if (from <= left && right <= to) {
            return tree[root];
        }

        int mid = (right - left) / 2 + left;
        // 注意，这里返回的是下标
        // 还要转成实际位置上的数值比较后才能返回
        int lIdx = query(ls, left, mid, from, to);
        int rIdx = query(rs, mid + 1, right, from, to);
        if (lIdx == -1) {
            return rIdx;
        }
        else if (rIdx == -1) {
            return lIdx;
        }
        else {
            if (arr[lIdx] > arr[rIdx]) {
                return lIdx;
            } else {
                return rIdx;
            }
        } // if return
    }
};

class Solution {
private:
    int n;
    SegTree tree;
    vector<int> arr;

    TreeNode* dfs(int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 在[left, right]范围内获取最大值
        int idx = tree.query(1, 1, n, left, right);
        return new TreeNode {
            arr[idx],
            dfs(left, idx - 1),
            dfs(idx + 1, right)
        };
    }

public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        this->n = nums.size();
        arr = nums;
        // [0, n-1] -> [1, n]
        arr.insert(arr.begin(), 0);
        tree = SegTree(arr, n);
        tree.build(1, 1, n);

        // 闭区间
        return dfs(1, n);
    }
};

const int N   ;						  // 区间长度
const int logN;						  // log2(区间长度)的上取整
const int M   ;						  // 调用次数
const int nodeCnt = 4 * M * logN;     // 可以调整参数和加偏移做个保守的计算

// 手写递增分配器
template<typename Type, size_t N>
class TreeAllocator {
    Type node[N];
    size_t i = 0;

public:
    Type* get() {
        auto p = node + i;
        i += 1;
        new (p) Type{};
        return p;
    }
};

// 区间 true | false
// 区间统计
class SegmentTree {
private:
    struct Node {
        int val  = 0;
        int lazy = -1;

        Node* left  = nullptr;
        Node* right = nullptr;
    };

    TreeAllocator<Node, 500010> alloc;
    Node*     root = nullptr;
    const int n    = 1e9 + 7;

public:
    SegmentTree() {
        root = alloc.get();
    }

private:
    void checkSon(Node* root) {
        if (nullptr == root->left) {
            root->left = alloc.get();
        }
        if (nullptr == root->right) {
            root->right = alloc.get();
        }
    }

    void pushUp(Node* root) {
        root->val = root->left->val + root->right->val;
    }

    // 每次调用 pushDown 首先第一步检查左右子树
    void pushDown(Node* root, int left, int right) {
        checkSon(root);

        if (root->lazy == -1) {
            return;
        }
        // lazy 只有1|0 表示true|false
        const int mid      = left + (right - left) / 2;
        const int leftLen  = mid - left + 1;
        const int rightLen = right - mid;
        
        root->left->val   = leftLen * root->lazy;
        root->right->val  = rightLen * root->lazy;
        root->left->lazy  = root->lazy;
        root->right->lazy = root->lazy;
        root->lazy        = -1;
    }

private:
    // bool val
    // true | false 的全覆盖
    void update(Node* root, int left, int right, int from, int to, bool val) {
        if (from > right || to < left) {
            return;
        }
        if (from <= left && right <= to) {
            root->val  = val * (right - left + 1);
            root->lazy = val;
            return;
        }

        pushDown(root, left, right);
        const int mid = left + (right - left) / 2;
        update(root->left, left, mid, from, to, val);
        update(root->right, mid + 1, right, from, to, val);
        pushUp(root);
    }

    int query(Node* root, int left, int right, int from, int to) {
        if (from > right || to < left) {
            return 0;
        }
        if (from <= left && right <= to) {
            return root->val;
        }

        pushDown(root, left, right);
        const int mid = left + (right - left) / 2;
        return query(root->left, left, mid, from, to) +
               query(root->right, mid + 1, right, from, to);
    }

public:
    void add(int left, int right, int val) {
        update(root, 1, n, left, right, val);
    }

    int ask(int left, int right) {
        return query(root, 1, n, left, right);
    }
};

class RangeModule {
    SegmentTree tree;

public:
    RangeModule() {
    }

    // RangeModule 的所有查询更新是 `left <= x < right`
    // SegmentTree 的所有查询是 `[left, right]`

    void addRange(int left, int right) {
        tree.add(left, right - 1, true);
    }

    bool queryRange(int left, int right) {
        // 查询区间为true的点数是否为区间长度
        return tree.ask(left, right - 1) == (right - left);
    }

    void removeRange(int left, int right) {
        tree.add(left, right - 1, false);
    }
};

#define ls (root << 1)
#define rs (root << 1 | 1)
// 区间累计
// 区间求最值
class SegTree {
private:
    struct Node {
        int val = 0;
        int lazy = 0;
    };

    unordered_map<int, Node> tree;
    const int n = 1e9 + 10;

public:
    SegTree() {}

    void pushUp(int root) {
        tree[root].val = max(tree[ls].val, tree[rs].val);
    }

    void pushDown(int root) {
        if (tree[root].lazy == 0) {
            return ;
        }

        tree[ls].val  += tree[root].lazy;
        tree[ls].lazy += tree[root].lazy;
        tree[rs].val  += tree[root].lazy;
        tree[rs].lazy += tree[root].lazy;
        
        tree[root].lazy = 0;
    }

    void update(int root, int left, int right, int from, int to, int val) {
        if (from > right || to < left) {
            return ;
        }
        if (from <= left && right <= to) {
            tree[root].val  += val;
            tree[root].lazy += val;
            return ;
        }

        pushDown(root);
        int mid = (right - left) / 2 + left;
        update(ls, left, mid, from, to, val);
        update(rs, mid + 1, right, from, to, val);
        pushUp(root);
    }

    int query(int root, int left, int right, int from, int to) {
        if (from > right || to < left) {
            return 0;
        }
        if (from <= left && right <= to) {
            return tree[root].val;
        }

        pushDown(root);
        int mid = (right - left) / 2 + left;
        return max(
            query(ls, left, mid, from, to),
            query(rs, mid + 1, right, from, to)
        );
    }

public: 
    // 注意：本题的左端点是0，根节点也不是乱定的
    // 因此，不推荐用传统的下标法，即便本分代码可以ac
    void update(int left, int right, int val) {
        update(1, 0, n, left, right, val);
    }
    
    int query(int left, int right) {
        return query(1, 0, n, left, right);
    }
};

class MyCalendarTwo {
private:
    SegTree tree;

public:
    MyCalendarTwo() {}
    
    // 要求不超过2
    bool book(int start, int end) {
        int left = start, right = end - 1;
        if (tree.query(left, right) >= 2) {
            return false;
        } else {
            // 每次贡献1次
            tree.update(left, right, 1);
            return true;
        }
    }
};