题意

给定一长度为n的序列a, 有两种操作；

1: 指定序列区间[l, r] 区间加上x；

2: 指定序列区间[l, r] 输出输出区间中小于x的元素的最大值；

分析

·本题和区间增量与区间小于计的题意相似(其实就是把小于x的最大值改成了小于x的元素的数量()

·首先，区间修改、区间查询让我们很自然能想到使用线段树

·线段树维护区间最大值，当当前区间完全包含于指定区间，且当前区间最大值 < x时返回 当前最大值

·否则递归但左右子区间查询

·但是由于本题中的查询有最大值 < x 这个条件(不像常见的线段树，当前区间包含于指定区间即可返回)，会导致区间查询复杂度从O(logn)退化，最坏到O(n).

·所以我们多维护一个区间最小值用于减枝

·当当前区间的最小值都 >= x 时，说明区间内没有元素满足 < x的条件，可直接返回

·注意：当区间内没有 <x 的元素时因返回-1， 该条件题目中没给

区间加

void update(int l, int r, ll num, int plc)
{
	if (l > stree[plc].r || r <stree[plc].l) return ;
	if (l <= stree[plc].l && stree[plc].r <= r)
	{
		stree[plc].maxv += num; // 因为是最值，直接加上即可
		stree[plc].minv += num;
		stree[plc].lazy += num;
		return ;
	}
	pushdown(plc);
	int mid = (stree[plc].l + stree[plc].r) >> 1;
	if (mid >= l) update(l, r, num, plc << 1);
	if (mid < r) update(l, r, num, plc << 1 | 1);
	pushup(plc);
}

区间查询

ll query(int l, int r, ll num, int plc)
{
	if (l > stree[plc].r || r < stree[plc].l) return -0x3f3f3f3f3f3f3f3f;
	if (stree[plc].minv >= num) return -0x3f3f3f3f3f3f3f3f; // 减枝
	
	if (l <= stree[plc].l && stree[plc].r <= r)
	{
		if (stree[plc].maxv < num) return stree[plc].maxv;
		if (stree[plc].l == stree[plc].r) return -0x3f3f3f3f3f3f3f3f; // 特判叶子结点不能， 防止pushdown溢出
	}
	pushdown(plc);
	
	ll res = -0x3f3f3f3f3f3f3f3f;
	int mid = (stree[plc].l + stree[plc].r) >> 1;
	if (mid >= l) res = max(res, query(l, r, num, plc << 1));
	if (mid < r) res = max(res, query(l, r, num, plc << 1 | 1));
	return res;
}

复杂度

·线段树初始化时间复杂度 O(n)

·线段树区间加时间复杂度 O(logn)

·线段树查询时间复杂度 最坏 O(n)、 平均O(logn)

·总体时间复杂度 最坏O(qn)、 平均O(qlogn)

·空间复杂度 O(4n)

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
typedef long long ll;

int n, q;
ll a[N];
struct STree
{
	int l, r;
	ll maxv, minv, lazy;
} stree[N << 2];

void pushup(int plc)
{
	stree[plc].maxv = max(stree[plc << 1].maxv, stree[plc << 1 | 1].maxv);
	stree[plc].minv = min(stree[plc << 1].minv, stree[plc << 1 | 1].minv); 
 } 
 
 void pushdown(int plc)
 {
	if (!stree[plc].lazy) return ;
	
	ll lz = stree[plc].lazy;
	int lson = plc << 1, rson = plc << 1 | 1;
 	
	stree[lson].maxv += lz;
	stree[lson].minv += lz;
	stree[lson].lazy += lz;
	
	stree[rson].maxv += lz;
	stree[rson].minv += lz;
	stree[rson].lazy += lz;
	
	stree[plc].lazy = 0;
}

void init(int l, int r, int plc)
{
	if (l > r) return ;
	stree[plc].l = l;
	stree[plc].r = r;
	stree[plc].lazy = 0;
	if (l == r)
	{
		stree[plc].maxv = stree[plc].minv = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	init(l, mid, plc << 1);
	init(mid + 1, r, plc << 1 | 1);
	pushup(plc);
}

void update(int l, int r, ll num, int plc)
{
	if (l > stree[plc].r || r <stree[plc].l) return ;
	if (l <= stree[plc].l && stree[plc].r <= r)
	{
		stree[plc].maxv += num;
		stree[plc].minv += num;
		stree[plc].lazy += num;
		return ;
	}
	pushdown(plc);
	int mid = (stree[plc].l + stree[plc].r) >> 1;
	if (mid >= l) update(l, r, num, plc << 1);
	if (mid < r) update(l, r, num, plc << 1 | 1);
	pushup(plc);
}

ll query(int l, int r, ll num, int plc)
{
	if (l > stree[plc].r || r < stree[plc].l) return -0x3f3f3f3f3f3f3f3f;
	if (stree[plc].minv >= num) return -0x3f3f3f3f3f3f3f3f;
	
	if (l <= stree[plc].l && stree[plc].r <= r)
	{
		if (stree[plc].maxv < num) return stree[plc].maxv;
		if (stree[plc].l == stree[plc].r) return -0x3f3f3f3f3f3f3f3f;
	}
	pushdown(plc);
	
	ll res = -0x3f3f3f3f3f3f3f3f;
	int mid = (stree[plc].l + stree[plc].r) >> 1;
	if (mid >= l) res = max(res, query(l, r, num, plc << 1));
	if (mid < r) res = max(res, query(l, r, num, plc << 1 | 1));
	return res;
}

int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	init(1, n, 1);
	for (int i = 0; i < q; i ++ )
	{
		int op, l, r;
		ll x;
		scanf("%d%d%d%lld", &op, &l, &r, &x);
		if (op == 1) update(l, r, x, 1);
		else
		{
			ll ans = query(l, r, x, 1);
			if (ans <= -0x3f3f3f3f3f3f3f3f) puts("-1"); // 注意无解返回-1
			else printf("%lld\n", ans);
		} 
	}
	
	return 0;
 }

希望对大家有所帮助qwq.