题目链接:https://loj.ac/problem/6279
题目大意:

思路:和上一题不同的是,查询小于c的最大元素,那么只要把整块查询改一改就可以了。当然写了个sb错误,把ans赋最小值为 (1<<32)内存溢出。 因为int 下1最多<<31

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x - 1) * Len + 1)
const int maxn = 5e5 + 5;
LL read()
{
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int a[100050], b[100050], add[1005];  // b[i]:i的块号
int Len, n;
set<int> v[1005];  //每个块的元素

void reset(int x)  //重构
{
    v[x].clear();
    for (int i = LL(x); i <= min(LL(x + 1) - 1, n); i++)
    {
        v[x].insert(a[i]);
    }
}

void Add(int L, int R, int x)
{
    int bL = b[L], bR = b[R];

    if (bL == bR)
    {
        for (int i = L; i <= R; i++)
        {
            a[i] += x;
        }
        reset(bL);  //边块修改完要重构
    }
    else
    {
        for (int i = L; i < LL(bL + 1); i++)
        {
            a[i] += x;
        }
        reset(bL);  //边块修改完要重构

        for (int i = bL + 1; i < bR; i++)
        {
            add[i] += x;
        }

        for (int i = LL(bR); i <= R; i++)
        {
            a[i] += x;
        }
        reset(bR);  //边块修改完要重构
    }
}

int query(int L, int R, int x)
{
    int ans = (1<<31);
    int bL = b[L], bR = b[R];

    if (bL == bR)
    {
        for (int i = L; i <= R; i++)
        {
            if (a[i] + add[bL] < x && a[i] + add[bL] > ans)
            {
                ans = a[i] + add[bL];
            }
        }
    }
    else
    {
        for (int i = L; i < LL(bL + 1); i++)
        {
            if (a[i] + add[bL] < x && a[i] + add[bL] > ans)
            {
                ans = a[i] + add[bL];
            }
        }

        for (int i = bL + 1; i < bR; i++)
        {
            int f = x - add[i];
            set<int>::iterator it = v[i].lower_bound(f);

            if (it == v[i].begin())
            {
                continue;
            }
            else
            {
                it--;
                ans = max(ans, *it + add[i]);
            }
        }

        for (int i = LL(bR); i <= R; i++)
        {
            if (a[i] + add[bR] < x && a[i] + add[bR] > ans)
            {
                ans = a[i] + add[bR];
            }
        }
    }
    return (ans == (1<<31)) ? -1 : ans;
}

void build(int n)
{
    Len = n / sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        add[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] = (i - 1) / Len + 1;
        v[b[i]].insert(a[i]);
    }
}

int main()
{
    n = read();
    build(n);

    for (int i = 1; i <= n; i++)
    {
        int op = read(), L = read(), R = read(), c = read();
        if (op == 0)
        {
            Add(L, R, c);
        }
        else
        {
            printf("%d\n", query(L, R, c));
        }
    }

    return 0;
}