6E - Exposition

原题链接https://codeforces.com/problemset/problem/6/E

题意：给你一个数组，问你一段连续的区间满足区间最大值和最小值的差不超过K的区间最大长度是多少？具体有哪些区间？

思路：由于RMQ我写的少，直接手撸线段树，然后双指针走即可，复杂度\(O(nlogn)\)

代码如下

struct node{
	int l, r;
	int maxd, mind;
}tr[N * 4];
int a[N];
int n, k;

void pushup(int u)
{
	tr[u].maxd = max(tr[u << 1].maxd, tr[u << 1 | 1].maxd);
	tr[u].mind = min(tr[u << 1].mind, tr[u << 1 | 1].mind);
}

void build(int u, int l, int r)
{
	if(l == r)
	{
		tr[u] = {r, r, a[r], a[r]};
		return;
	}
	tr[u] = {l, r};
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

int query_max(int u, int l, int r)
{
	if(tr[u].l >= l && tr[u].r <= r)	return tr[u].maxd;
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		int res = 0;
		if(l <= mid) res = query_max(u << 1, l, r);
		if(r > mid) res = max(res, query_max(u << 1 | 1, l, r));
		return res;
	}
}

int query_min(int u, int l, int r)
{
	if(tr[u].l >= l && tr[u].r <= r)	return tr[u].mind;
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		int res = 1e9;
		if(l <= mid) res = query_min(u << 1, l, r);
		if(r > mid) res = min(res, query_min(u << 1 | 1, l, r));
		return res;
	}
}


int main()
{
	IOS;
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++)	cin >> a[i];
	
	build(1, 1, n);
	
	int l, r;
	int maxm, mini;
	int res = 0;
	vector<pii> v;
	for(l = 1, r = 1 ; r <= n ; r ++)
	{
		maxm = query_max(1, l, r);
		mini = query_min(1, l, r);
		while(maxm - mini > k)
		{
			l ++;
			maxm = query_max(1, l, r);
			mini = query_min(1, l, r);
		}
		if(res < r - l + 1)
		{
			v.clear();
			res = r - l + 1;
			v.push_back({l, r});
		}
		else if(res == r - l + 1)
			v.push_back({l, r});
	}
	
	cout << res << " " << v.size() << endl;
	for(auto x : v)	cout << x.x << " " << x.y << endl;

	return 0;
}

6E - Exposition

原文：https://www.cnblogs.com/luoyicong/p/14618540.html