ST表50pts+WA,求助
查看原帖
ST表50pts+WA,求助
439207
hhw_khw楼主2022/2/12 14:16
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int maxst[maxn][12], minst[maxn][12], lg2[maxn], n, m, c;
bool ismute = false;
void st_init() {
	for (int i = 1; i <= n; i ++) {
		cin >> maxst[i][0];
		minst[i][0] = maxst[i][0];
		lg2[i] = lg2[i >> 1] + 1;
	}
	for (int j = 1; 1 << j <= n; j ++)
	for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
		maxst[i][j] = max(maxst[i][j - 1], maxst[i + (1 << j - 1)][j - 1]);
		minst[i][j] = min(minst[i][j - 1], minst[i + (1 << j - 1)][j - 1]);
	}
}
inline int querymax(int l, int r) {
	return max(maxst[l][lg2[r - l + 1]], maxst[r - (1 << lg2[r - l + 1]) + 1][lg2[r - l + 1]]);
}
inline int querymin(int l, int r) {
	return min(minst[l][lg2[r - l + 1]], minst[r - (1 << lg2[r - l + 1]) + 1][lg2[r - l + 1]]);
}
int main() {
	lg2[0] = -1;
	cin >> n >> m >> c;
	st_init();
	for (int i = 1; i <= n - m + 1; i ++) {
        if (querymax(i, i + m - 1) - querymin(i, i + m - 1) <= c) {
            ismute = 1;
            cout << i << endl;
        }
        //cout << querymax(i, i + m - 1) - querymin(i, i + m - 1) << endl;
	}
	if (!ismute) cout << "NONE" << endl;
	return 0;
}

2022/2/12 14:16
加载中...