给一个序列 $a,q$ 次操作。每次操作单点修改。每次操作后,询问序列$a$中有没有一个位置满足$a[i]=bit[i-1],$ 如果有,随便输出一个位置,如果没有输出$-1$。其中 $bit$ 为前缀和数组
题解
很容易想到按照 $a[i]-bit[i-1]$ 建线段树,修改操作可以利用$lazy$一个log实现,但查询位置 $0$ 的位置操作怎么一个 $log$ 实现?考虑 $a[i]-bit[i-1]$ 这个序列要都满足的话,至少是$1,1,2,4,8……$ ,最多$logn$次就到了$longlong$,所以线段树维护区间最大值$maxx$,查询区间$maxx< 0$ 就剪枝,找到合法位置也要剪枝
$trick:$ 每次修改后要把序列的值改掉