Solution

class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        self.arr = []
        def traverse(r):
            if not r:
                return
            traverse(r.left)
            self.arr.append(r.val)
            traverse(r.right)
        traverse(root)
        def find_bound(x, y):
            # x <= arr[left...right] <= y   1 3 4 4 6 8
            left = bisect_left(self.arr, x)
            right = bisect_right(self.arr, y) - 1
            return left, right
        res = 0
        for t, x, y in ops[::-1]:  # 每个节点的最终颜色取决于最后一次染色
            left, right = find_bound(x, y)
            if t == 1:
                res += right + 1 - left
            self.arr =  self.arr[:left] + self.arr[right+1:]  # 去掉染过色的节点
        
        return res

线段树的解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

 //[769836168,10709914,986872749,null,569945181,850182753,null,514412027,691018511,842990509,886343010,128384490,null,582871641,756062719,null,null,null,null,51807103,514127439,null,590845769,744651324,null,null,null,251214860,null,null,665257777,null,null,222643485,431635363,null,null,null,null,290988646]
// [[1,514127439,769836168],[0,756062719,850182753],[1,290988646,590845769],[0,756062719,886343010],[0,51807103,290988646],[1,691018511,691018511],[0,290988646,842990509],[0,590845769,665257777],[1,665257777,756062719],[1,590845769,769836168],[1,744651324,744651324],[1,590845769,756062719],[1,290988646,590845769],[1,769836168,986872749],[0,582871641,850182753],[1,665257777,665257777],[0,514127439,756062719],[1,842990509,842990509],[0,850182753,986872749]]

class Solution {
    public int getNumber(TreeNode root, int[][] ops) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        int[] nums = new int[list.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = list.get(i);
            // System.out.print("" + nums[i] + ", ");
        }
        // System.out.println();
        int[] diff = new int[nums.length];
        SegmentTree st = new SegmentTree(diff);
        for (int[] op : ops) {
            int c = op[0];
            int x = op[1], y = op[2];
            if (x > nums[nums.length - 1] || y < nums[0]) continue;
            // find x pos
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= x) right = mid;
                else left = mid + 1;
            }
            int tx = left;
            // find y pos
            left = 0; right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (nums[mid] <= y) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            int ty = left;
            if (tx > ty) continue;
            st.update(tx, ty, c);
            // st.query(0, diff.length - 1);
            // System.out.println(st.query(0, diff.length - 1) + " # " + c + " # " + "[" + tx + ", " + ty + "]" + " # " + "[" + x + ", " + y + "]");
        }
        return st.query(0, diff.length - 1);
        
    }
    
    void dfs(TreeNode root, List<Integer> list) {
        if (root == null) return;
        dfs(root.left, list);
        list.add(root.val);
        dfs(root.right, list);
    }
}

class SegmentTree {
    private int[] tree, nums, lazy;
    final int INIT = -1;
    public SegmentTree(int[] nums) {
        int n = nums.length;
        tree = new int[4*n];
        lazy = new int[4*n];    // lazy tag
        Arrays.fill(lazy, INIT);
        this.nums = nums;
        buildTree(0, 0, n-1);
    }

    private void buildTree(int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        int leftNode  = node * 2 + 1;
        int rightNode = node * 2 + 2;

        buildTree(leftNode, start, mid);
        buildTree(rightNode, mid+1, end);

        tree[node] = tree[leftNode] + tree[rightNode];
    }

    private void pushDown(int node, int start, int end) {
        if (lazy[node] == INIT) {
            return;
        }
        int leftNode = node * 2 + 1;
        int rightNode = node * 2 + 2;
        int mid = start + (end - start) / 2;
        
        // 如果方案为区间增值，把下面四个 = 改成 += 即可
        tree[leftNode] = lazy[node] * (mid - start + 1);
        lazy[leftNode] = lazy[node];
        tree[rightNode] = lazy[node] * (end - mid);
        lazy[rightNode] = lazy[node];
        // 清空当前 lazy tag
        lazy[node] = INIT;
    }

    private void updateTree(int node, int start, int end, int left, int right, int val) {
        // 当前节点被区间完全覆盖，更新节点并设置 lazy tag，这样就没必要向下更新了
        if (left <= start && end <= right) {
            // 如果方案为区间增值，把下面两个 = 改成 += 即可
            tree[node] = (end - start + 1) * val;  
            lazy[node] = val;   
            return;
        }

        // 把当前节点的 lazy tag 传递到下一层
        pushDown(node, start, end);

        int mid = start + (end - start) / 2;
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;

        // 需要更新左子树
        if (left <= mid) {
            updateTree(leftNode, start, mid, left, right, val);
        } 
        // 需要更新右子树
        if (right > mid) {
            updateTree(rightNode, mid+1, end, left, right, val);
        } 
        // 更新当前节点
        tree[node] = tree[leftNode] + tree[rightNode];
    }

    private int queryTree(int node, int start, int end, int left, int right) {
        // 查找范围不在当前范围内
        if (right < start || left > end) {
            return 0;
        }
        // 当前范围就在查找范围中，直接返回
        if (start >= left && end <= right) {
            return tree[node];
        }
        
        // 部分范围在查找区间中，先把 lazy tag 传下去
        pushDown(node, start, end);
        

        int mid = start + (end - start) / 2;
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        int leftSum = queryTree(leftNode, start, mid, left, right);
        int rightSum = queryTree(rightNode, mid+1, end, left, right);
        return leftSum + rightSum;
    }

    public void update(int index, int val) {
        updateTree(0, 0, nums.length-1, index, index, val); 
    }

    public void update(int left, int right, int val) {
        updateTree(0, 0, nums.length - 1, left, right, val);
    }
    
    public int query(int left, int right) {
        int result = queryTree(0, 0, nums.length-1, left, right);
        return result;
    }
}

使用模板Range

力扣

class Solution {
public:
    int dfs(TreeNode* root, RangeModule& s) {
        return root ? s.queryRange(root->val, root->val + 1) + dfs(root->left, s) + dfs(root->right, s) : 0;
    }
    
    int getNumber(TreeNode* root, vector<vector<int>>& ops) {
        RangeModule s;
        for (const auto& e : ops) {
            switch (e[0]) {
                case 0:s.removeRange(e[1], e[2] + 1);break;
                case 1:s.addRange(e[1], e[2] + 1);break;
            }
        }
        return dfs(root, s);
    }
};

作者：vclip
链接：<https://leetcode-cn.com/problems/QO5KpG/solution/yong-by-vclip-pgc1/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class RangeModule(object):
    def __init__(self):
        self.ranges = []

    def _bounds(self, left, right):
        i, j = 0, len(self.ranges) - 1
        for d in (100, 10, 1):
            while i + d - 1 < len(self.ranges) and self.ranges[i+d-1][1] < left:
                i += d
            while j >= d - 1 and self.ranges[j-d+1][0] > right:
                j -= d
        return i, j

    def addRange(self, left, right):
        i, j = self._bounds(left, right)
        if i <= j:
            left = min(left, self.ranges[i][0])
            right = max(right, self.ranges[j][1])
        self.ranges[i:j+1] = [(left, right)]

    def queryRange(self, left, right):
        i = bisect.bisect_left(self.ranges, (left, float('inf')))
        if i: i -= 1
        return (bool(self.ranges) and
                self.ranges[i][0] <= left and
                right <= self.ranges[i][1])

    def removeRange(self, left, right):
        i, j = self._bounds(left, right)
        merge = []
        for k in xrange(i, j+1):
            if self.ranges[k][0] < left:
                merge.append((self.ranges[k][0], left))
            if right < self.ranges[k][1]:
                merge.append((right, self.ranges[k][1]))
        self.ranges[i:j+1] = merge

作者：LeetCode
链接：<https://leetcode-cn.com/problems/range-module/solution/range-mo-kuai-by-leetcode/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。