P14111

区间最大值

AC

大师 · 发布于 2025-03-13 · 浏览 520 回复 1

include

include

using namespace std;

int main() {

list<int> LA, LB;
int num;

while (cin >> num && num != -1) {
	LA.push_back(num);
}
while (cin >> num && num != -1) {
	LB.push_back(num);
}
list<int>::iterator itA = LA.begin(), itB = LB.begin(), itC;
list<int> LC;
while (itA != LA.end() && itB != LB.end()) {
	if (*itA < *itB) {
		LC.push_back(*itA);
		++itA;
	} else {
		LC.push_back(*itB);
		++itB;
	}
}
while (itA != LA.end()) {
	LC.push_back(*itA);
	++itA;
}
while (itB != LB.end()) {
	LC.push_back(*itB);
	++itB;
}
for (const int &val : LC) {
	cout << val << " ";
}
cout << endl;

return 0;

}

全部回复 共 1 条

  1. ------监狱栅栏------ #1 ·

    `

    #include<iostream>
#include<cmath>
#include<fstream>
using namespace std;
int st[100001][18];
int main() { 
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &st[i][0]);  
	for (int j = 1; j < log2(n); j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 1; i <= m; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		int x = log2(r - l + 1);
		printf("%d\n", max(st[l][x], st[r - (1 << x) + 1][x]));
	}
	return 0;
}`

发表回复