题解 | 区间增量与区间前驱

def solve(testcase):
    n, q = MI()
    A = LII()
    
    blocksz = int(sqrt(n))
    blocks = [[] for _ in range(blocksz + 10)]
    blockinfo = [[] for _ in range(blocksz + 10)]
    blocklz = [0 for _ in range(blocksz + 10)]

    for i, v in enumerate(A):
        where, idx = divmod(i, blocksz)
        blocks[where].append(v)
    
    for i in range(blocksz + 10):
        blockinfo[i] = sorted(blocks[i])
    
    def update(l, r, x):
        lwhere, lidx = divmod(l, blocksz)
        rwhere, ridx = divmod(r, blocksz)

        if lwhere == rwhere:
            for i in range(lidx, ridx + 1):
                blocks[lwhere][i] += x
            blockinfo[lwhere] = sorted(blocks[lwhere])
        
        else:
            for j in range(lidx, len(blocks[lwhere])):
                blocks[lwhere][j] += x
            blockinfo[lwhere] = sorted(blocks[lwhere])
            lwhere += 1

            for j in range(ridx + 1):
                blocks[rwhere][j] += x
            blockinfo[rwhere] = sorted(blocks[rwhere])
            rwhere -= 1

            for i in range(lwhere, rwhere + 1):
                blocklz[i] += x
        
    def query(l, r, x):
        res = -inf

        lwhere, lidx = divmod(l, blocksz)
        rwhere, ridx = divmod(r, blocksz)

        if lwhere == rwhere:
            for i in range(lidx, ridx + 1):
                val = blocks[lwhere][i] + blocklz[lwhere]
                if val < x:
                    res = fmax(res, val)
        else:
            for j in range(lidx, len(blocks[lwhere])):
                val = blocks[lwhere][j] + blocklz[lwhere]
                if val < x:
                    res = fmax(res, val)
            
            lwhere += 1

            for j in range(ridx + 1):
                val = blocks[rwhere][j] + blocklz[rwhere]
                if val < x:
                    res = fmax(res, val)
            
            rwhere -= 1

            for i in range(lwhere, rwhere + 1):
                idx = bisect_right(blockinfo[i], x - blocklz[i] - 1) - 1
                if idx != -1:
                    res = fmax(res, blockinfo[i][idx] + blocklz[i])
            
        print(-1 if res == -inf else res)
                

    for _ in range(q):
        ops = LII()
        op = ops[0]

        if op == 1:
            l, r, x = ops[1] - 1, ops[2] - 1, ops[3]
            update(l, r, x)
        else:
            l, r, x = ops[1] - 1, ops[2] - 1, ops[3]
            query(l, r, x)

for testcase in range(1):
    solve(testcase)

题目少说了一个条件，在计算区间前驱时，如果不存在满足要求的数，就输出-1