E. Exposition

题目链接：Problem - E - Codeforces

题目大意： 给你一个长度为n的序列，和一个整数k.现让找出所有连续的最长子区间， 其子区间的条件是：在区间里最大值减去最小值之差要小于 k .

输入：

输入数据的第一行包含两个用空格隔开的整数 n ( 1 ≤ n ≤ 1e5 )和 k ( 0 ≤ k ≤ 1e6 )

第二行包含 n 个整数，以空格分隔。每个数字 ai ( 1 ≤ ai ≤ 1e6 ).

输出：

在输出数据的第一行打印两个数字 a 和 b (用空格隔开)，其中 a是每个区间的长度。b是个数

在接下来的 b 行中，每行打印两个整数，中间用空格隔开，起始位置与终点位置。

具体题目描述见链接。

方法： 线段树，ST表， 二分

1.由于题目要求是要，让最大值与最小值做差运算小于k. 所以不难想到用一个特殊的数据结构去维护最大值于最小值。

2.看数据范围 1e5, 暴力求解区间的满足情况是不行的， 考虑使用其它算法。 当发现若只有一个数时，那它的最大值减去最小值就为0（也就最小的情况）。区间覆盖的越广，差值可能就越大，有单调性。考虑二分。

3.二分： 通过枚举左边界[1，n], 然后通过最大值二分找出相应的右边界， 统计此时的区间最大值。然后使用map将区间长度一致的分在一起，

4.二分时，要查询[i, mid](代码里)， 就要使用ST表或者线段树维护的最值。 此处的最大值二分见代码。

先贴ST表做法：

二分关键代码：

int mxx = 0; //记录最长的区间map<int, vector<pair<int,int>>> mp;//统计答案for(int i=1; i<=n; i++) {int l = i;int r = n;int dl = i;while(l<=r) { //二分右边界int mid = (l+r) >> 1;if(go(i,mid)<=k) { // go()函数查询的是差值，注意 i, 到middl = mid;  //满足， 看是否还可以变长，最值二分l = mid+1;}else{r = mid-1;}}mp[dl-i+1].push_back({i,dl});// 分区间mxx = max(mxx, dl-i+1); // 找最长的}

ST表完整代码：

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;struct ST{vector<vector<int>> data;vector<int> lg2;int n;ST(){}ST(int n){innt(n);}void innt(int n){this->n = n;data.resize(n+1, vector<int>(32));lg2.resize(n+1);lg2[0] = -1;for(int i=1; i<=n; i++) {lg2[i] = lg2[i>>1] + 1;}}int gcd(int a, int b){return b==0? a : gcd(b, a%b);}void buildGcd(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1 <= n; i++) {data[i][p] = gcd(data[i][p - 1], data[i + (1 << (p-1))][p-1]);}}}int queryGcd(int l, int r){int p = lg2[r-l+1];return gcd(data[l][p], data[r-(1<<p)+1][p]);}void buildMax(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = max(data[i][p-1], data[i + (1<<(p-1))][p-1]);}}}int queryMax(int l, int r){int p = lg2[r-l+1];return max(data[l][p], data[r-(1<<p)+1][p]);}void buildMin(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = min(data[i][p-1], data[i + (1<<(p-1))][p-1]);}}}int queryMin(int l, int r){int p = lg2[r-l+1];return min(data[l][p], data[r-(1<<p)+1][p]);}void buildAnd(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = data[i][p-1] & data[i + (1<<(p-1))][p-1];}}}int queryAnd(int l, int r){int p = lg2[r-l+1];return data[l][p] & data[r-(1<<p)+1][p];}void buildOr(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = data[i][p-1] | data[i + (1<<(p-1))][p-1];}}}int queryOr(int l, int r){int p = lg2[r-l+1];return data[l][p] | data[r-(1<<p)+1][p];}
};ST stmi, stmx; //使用的封装好的ST表int go(int l, int r){ //做差值运算return stmx.queryMax(l, r) - stmi.queryMin(l, r);
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;stmi.innt(n), stmx.innt(n);for(int i=1; i<=n; i++) {int t;cin >> t;stmi.data[i][0] = stmx.data[i][0] = t;}stmi.buildMin();stmx.buildMax();//建ST表int mxx = 0;map<int, vector<pair<int,int>>> mp;for(int i=1; i<=n; i++) {int l = i;int r = n;int dl = i;while(l<=r) { //二分右边界int mid = (l+r) >> 1;if(go(i,mid)<=k) {dl = mid;l = mid+1;}else{r = mid-1;}}mp[dl-i+1].push_back({i,dl});mxx = max(mxx, dl-i+1);}cout << mxx << ' ' << mp[mxx].size() << "\n";for(auto[x, y] : mp[mxx]) {cout << x << " " << y << "\n";}return 0;
}

线段树做法， 二分方法一致。只是采用线段树维护最值了。

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;const int N = 1e5+3;
struct Node{int l, r;int mi, mx;
}tr[N<<2]; // 开四倍
int a[N];
int n, k;void up(int id){tr[id].mi = min(tr[id<<1].mi, tr[id<<1|1].mi);tr[id].mx = max(tr[id<<1].mx, tr[id<<1|1].mx);
}void build(int id, int l,int r){tr[id].l = l;tr[id].r = r;if(l==r) {tr[id].mi = tr[id].mx = a[r];return ;}int mid = (l+r)>>1;build(id<<1, l, mid);build(id<<1|1, mid+1, r);up(id);
}int query_mi(int id, int jobl, int jobr){if(jobl <= tr[id].l && tr[id].r<=jobr){return tr[id].mi;}int mid = (tr[id].l + tr[id].r) >>1;int res = INT_MAX;if(jobl <= mid) {res = min(res, query_mi(id<<1, jobl, jobr));}if(jobr > mid) {res = min(res, query_mi(id<<1 | 1, jobl, jobr));}return res;
}int query_mx(int id, int jobl, int jobr){if(jobl <= tr[id].l && tr[id].r<=jobr){return tr[id].mx;}int mid = (tr[id].l + tr[id].r) >>1;int res = INT_MIN;if(jobl <= mid) {res = max(res, query_mx(id<<1, jobl, jobr));}if(jobr > mid) {res = max(res, query_mx(id<<1 | 1, jobl, jobr));}return res;
}int go(int jobl, int jobr){return query_mx(1, jobl, jobr) - query_mi(1, jobl, jobr);
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> k;for(int i=1; i<=n; i++) {cin >> a[i];}map<int, vector<pair<int,int>>> mp;build(1, 1, n); //建树int mxx = 0;for(int i=1; i<=n; i++) {int l = i;int r = n;int dl = i;while(l<=r) {int mid = (l+r)>>1;if(go(i,mid) <= k) {dl = mid;l = mid+1;}else{r = mid-1;}}mxx = max(mxx, dl - i + 1);mp[dl-i+1].push_back({i,dl});}cout << mxx << " " << mp[mxx].size() << "\n";for(auto [x,y] : mp[mxx]) {cout << x << " " << y << "\n";}return 0;
}

欢迎大佬指正，感谢你的收看与点赞。