零数组变换 二分+查分数组｜｜线段树lazy

前言：其实这个题目用二分来写才比较合理，但是好久没写二分了，没想到

题目链接

查分+二分的话比较好理解
代码就不给出来了

class Tree:def __init__(self,n):self.n = nself.t = [0]*(4*n)self.lazy = [0]*(4*n)def push_down(self,o):if self.lazy[o] !=0:self.t[o*2] += self.lazy[o]self.lazy[o*2] += self.lazy[o]self.t[o*2+1] += self.lazy[o]self.lazy[o*2+1] += self.lazy[o]self.lazy[o] = 0def update(self,o,l,r,L,R,va):if L<=l and r<= R:self.t[o] += vaself.lazy[o] += vareturnself.push_down(o)mid = (l+r)//2if L<=mid:self.update(o*2,l,mid,L,R,va)if mid<R:self.update(o*2+1,mid+1,r,L,R,va)self.t[o] = max(self.t[o*2],self.t[o*2+1])def query(self,o,l,r,L,R):if L<=l and r<=R:return self.t[o]self.push_down(o)mid = (l+r)//2tmp = 0if L<=mid:tmp = max(tmp,self.query(o*2,l,mid,L,R))if mid<R:tmp = max(tmp,self.query(o*2+1,mid+1,r,L,R))return tmpclass Solution:def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:n = len(nums)tr = Tree(n)for i,va in enumerate(nums):tr.update(1,0,n-1,i,i,va)for i in range(len(queries)):l,r,va = queries[i]if tr.query(1,0,n-1,0,n-1) <= 0:return itr.update(1,0,n-1,l,r,-va)if tr.query(1,0,n-1,0,n-1) <= 0:return len(queries)return -1