CF-6E Exposition 题解

题目大意

给定一个长度为n的数组，请在之中挑出最长的子数组，要求子数组中元素差的最大值不超过k。问有几个最长子数组，最长子数组的长度，以及这几个子数组的开始点、尾点。

解题思路

刚开始看到这题，就想着这个区间的最大值和最小值不好维护。

想了一下，看了眼题解，发现怎么可以这么暴力。。

（好像还有什么线段树，RMQ的解法，那些都不会啊

维护区间最大值只需要用multiset就可以了。

剩下的就是尺取了。

具体看代码。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int num[N];
multiset<int> s;
vector<pair<int,int>> v;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n, k; cin >> n >> k;
	ll len = 1;
	rep(i, 1, n)	cin >> num[i];
	ll l, r;
	l = r = 1;
	s.insert(num[1]);
	v.push_back({ 1,1 });
	while (r < n) {
		r++; s.insert(num[r]);
		while (*s.rbg() - *s.begin() > k && !s.empty()) {
			s.erase(s.find(num[l]));
			l++;
		}
		if (r - l + 1 > len) {
			v.clear();
			len = r - l + 1;
			v.push_back({ l,r });
		}
		else if (r - l + 1 == len)	v.push_back({ l,r });
	}
	cout << len << ' ' << v.size() << endl;
	for (auto x : v) {
		cout << x.first << ' ' << x.second << endl;
	}
	return 0;
}