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

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const long long INF = -2e18; // 使用一个足够小的数表示未找到
int n, m;
int block_size;
vector<long long> a;
vector<long long> lazy;
vector<vector<long long>> blocks;
vector<int> block_map;

// 重构指定块的有序版本
void rebuild(int b_idx) {
    int start = b_idx * block_size;
    int end = min((b_idx + 1) * block_size - 1, n - 1);
    blocks[b_idx].clear();
    for (int i = start; i <= end; ++i) {
        blocks[b_idx].push_back(a[i]);
    }
    sort(blocks[b_idx].begin(), blocks[b_idx].end());
}

// 只将懒标记应用到原数组a，不重构
void apply_lazy(int b_idx) {
    if (lazy[b_idx] == 0) return;
    int start = b_idx * block_size;
    int end = min((b_idx + 1) * block_size - 1, n - 1);
    for (int i = start; i <= end; ++i) {
        a[i] += lazy[b_idx];
    }
    lazy[b_idx] = 0;
}

void update(int l, int r, long long x) {
    int start_block = block_map[l];
    int end_block = block_map[r];

    if (start_block == end_block) {
        apply_lazy(start_block);
        for (int i = l; i <= r; ++i) {
            a[i] += x;
        }
        rebuild(start_block);
    } else {
        apply_lazy(start_block);
        for (int i = l; i < (start_block + 1) * block_size; ++i) {
            a[i] += x;
        }
        rebuild(start_block);

        for (int i = start_block + 1; i < end_block; ++i) {
            lazy[i] += x;
        }

        apply_lazy(end_block);
        for (int i = end_block * block_size; i <= r; ++i) {
            a[i] += x;
        }
        rebuild(end_block);
    }
}

long long query(int l, int r, long long k) {
    long long ans = INF;
    int start_block = block_map[l];
    int end_block = block_map[r];

    if (start_block == end_block) {
        for (int i = l; i <= r; ++i) {
            if (a[i] + lazy[start_block] < k) {
                ans = max(ans, a[i] + lazy[start_block]);
            }
        }
    } else {
        for (int i = l; i < (start_block + 1) * block_size; ++i) {
            if (a[i] + lazy[start_block] < k) {
                ans = max(ans, a[i] + lazy[start_block]);
            }
        }
        for (int i = start_block + 1; i < end_block; ++i) {
            long long target = k - lazy[i];
            auto it = lower_bound(blocks[i].begin(), blocks[i].end(), target);
            if (it != blocks[i].begin()) {
                ans = max(ans, *(--it) + lazy[i]);
            }
        }
        for (int i = end_block * block_size; i <= r; ++i) {
            if (a[i] + lazy[end_block] < k) {
                ans = max(ans, a[i] + lazy[end_block]);
            }
        }
    }
    return ans == INF ? -1 : ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    a.resize(n);
    block_size = sqrt(n);
    int num_blocks = (n + block_size - 1) / block_size;
    lazy.assign(num_blocks, 0);
    blocks.resize(num_blocks);
    block_map.resize(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        block_map[i] = i / block_size;
    }

    for (int i = 0; i < num_blocks; ++i) {
        rebuild(i);
    }

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            update(l - 1, r - 1, x);
        } else {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            cout << query(l - 1, r - 1, k) << "\n";
        }
    }

    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int blockSize;
    static long[] a;
    static long[] lazy;
    static ArrayList<Long>[] blocks;
    static int[] blockMap;

    static void rebuild(int bIdx) {
        int start = bIdx * blockSize;
        int end = Math.min((bIdx + 1) * blockSize - 1, n - 1);
        blocks[bIdx].clear();
        for (int i = start; i <= end; i++) {
            blocks[bIdx].add(a[i]);
        }
        Collections.sort(blocks[bIdx]);
    }

    // 只将懒标记应用到原数组a，不重构
    static void applyLazy(int bIdx) {
        if (lazy[bIdx] == 0) return;
        int start = bIdx * blockSize;
        int end = Math.min((bIdx + 1) * blockSize - 1, n - 1);
        for (int i = start; i <= end; i++) {
            a[i] += lazy[bIdx];
        }
        lazy[bIdx] = 0;
    }

    static void update(int l, int r, long x) {
        int startBlock = blockMap[l];
        int endBlock = blockMap[r];

        if (startBlock == endBlock) {
            applyLazy(startBlock);
            for (int i = l; i <= r; i++) {
                a[i] += x;
            }
            rebuild(startBlock);
        } else {
            applyLazy(startBlock);
            for (int i = l; i < (startBlock + 1) * blockSize; i++) {
                a[i] += x;
            }
            rebuild(startBlock);

            for (int i = startBlock + 1; i < endBlock; i++) {
                lazy[i] += x;
            }

            applyLazy(endBlock);
            for (int i = endBlock * blockSize; i <= r; i++) {
                a[i] += x;
            }
            rebuild(endBlock);
        }
    }

    static long query(int l, int r, long k) {
        long ans = Long.MIN_VALUE;
        int startBlock = blockMap[l];
        int endBlock = blockMap[r];
        
        if (startBlock == endBlock) {
            for (int i = l; i <= r; i++) {
                if (a[i] + lazy[startBlock] < k) {
                    ans = Math.max(ans, a[i] + lazy[startBlock]);
                }
            }
        } else {
            for (int i = l; i < (startBlock + 1) * blockSize; i++) {
                if (a[i] + lazy[startBlock] < k) {
                    ans = Math.max(ans, a[i] + lazy[startBlock]);
                }
            }
            for (int i = startBlock + 1; i < endBlock; i++) {
                long target = k - lazy[i];
                int idx = Collections.binarySearch(blocks[i], target);
                if (idx < 0) {
                    idx = -idx - 1; // Insertion point
                }
                if (idx > 0) {
                    ans = Math.max(ans, blocks[i].get(idx - 1) + lazy[i]);
                }
            }
            for (int i = endBlock * blockSize; i <= r; i++) {
                if (a[i] + lazy[endBlock] < k) {
                    ans = Math.max(ans, a[i] + lazy[endBlock]);
                }
            }
        }
        return ans == Long.MIN_VALUE ? -1 : ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        a = new long[n];
        blockSize = (int) Math.sqrt(n);
        int numBlocks = (n + blockSize - 1) / blockSize;
        lazy = new long[numBlocks];
        blocks = new ArrayList[numBlocks];
        blockMap = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
            blockMap[i] = i / blockSize;
        }

        for (int i = 0; i < numBlocks; i++) {
            blocks[i] = new ArrayList<>();
            rebuild(i);
        }

        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            if (type == 1) {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                long x = Long.parseLong(st.nextToken());
                update(l - 1, r - 1, x);
            } else {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                long k = Long.parseLong(st.nextToken());
                out.println(query(l - 1, r - 1, k));
            }
        }
        out.flush();
    }
}

import sys
import math
import bisect

def rebuild(b_idx):
    start = b_idx * block_size
    end = min((b_idx + 1) * block_size, n)
    # Clear and rebuild
    blocks[b_idx] = sorted(a[start:end])

# 只将懒标记应用到原数组a，不重构
def apply_lazy(b_idx):
    if lazy[b_idx] == 0:
        return
    start = b_idx * block_size
    end = min((b_idx + 1) * block_size, n)
    for i in range(start, end):
        a[i] += lazy[b_idx]
    lazy[b_idx] = 0

def update(l, r, x):
    start_block = l // block_size
    end_block = r // block_size

    if start_block == end_block:
        apply_lazy(start_block)
        for i in range(l, r + 1):
            a[i] += x
        rebuild(start_block)
    else:
        apply_lazy(start_block)
        for i in range(l, (start_block + 1) * block_size):
            a[i] += x
        rebuild(start_block)
        
        for i in range(start_block + 1, end_block):
            lazy[i] += x

        apply_lazy(end_block)
        for i in range(end_block * block_size, r + 1):
            a[i] += x
        rebuild(end_block)

def query(l, r, k):
    ans = -float('inf')
    start_block = l // block_size
    end_block = r // block_size

    if start_block == end_block:
        for i in range(l, r + 1):
            val = a[i] + lazy[start_block]
            if val < k:
                ans = max(ans, val)
    else:
        for i in range(l, (start_block + 1) * block_size):
            val = a[i] + lazy[start_block]
            if val < k:
                ans = max(ans, val)
        
        for i in range(start_block + 1, end_block):
            target = k - lazy[i]
            # bisect_left finds insertion point, which is what we need
            idx = bisect.bisect_left(blocks[i], target)
            if idx > 0:
                ans = max(ans, blocks[i][idx - 1] + lazy[i])
        
        for i in range(end_block * block_size, r + 1):
            val = a[i] + lazy[end_block]
            if val < k:
                ans = max(ans, val)
                
    return int(ans) if ans != -float('inf') else -1

def solve():
    global n, block_size, a, lazy, blocks
    
    # Fast I/O
    lines = sys.stdin.readlines()
    n, m = map(int, lines[0].split())
    a = list(map(int, lines[1].split()))
    
    block_size = int(math.sqrt(n))
    num_blocks = (n + block_size - 1) // block_size
    lazy = [0] * num_blocks
    blocks = [[] for _ in range(num_blocks)]
    
    for i in range(num_blocks):
        rebuild(i)

    results = []
    for line in lines[2:]:
        parts = list(map(int, line.split()))
        op = parts[0]
        if op == 1:
            l, r, x = parts[1], parts[2], parts[3]
            update(l - 1, r - 1, x)
        else:
            l, r, k = parts[1], parts[2], parts[3]
            results.append(str(query(l - 1, r - 1, k)))
            
    print("\n".join(results))

solve()