提交记录

时间复杂度：$O((n+m)\times \log_2 n)$。

#include <vector>
#include <stdio.h>
#include <ctype.h>
#define N 100005
#define M 2000005
#define R register
using namespace std;
char Buf[1 << 21], *S(Buf), *T(Buf);
#define getchar() (S == T && (T = (S = Buf) + fread(Buf, 1, 1 << 21, stdin), S == T) ? EOF : *S++)
inline void Input(int &x) {
    R char c(getchar());
    for (x = 0; !isdigit(c); ) c = getchar();
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
struct Query { int l, r, pos; };
int n, m, a[N], f[N], g[N], Ans[M];
Query Q[M], QL[M], QR[M];
inline int max(int a, int b) { return a > b ? a : b; }
void solve(int l, int r, int Ql, int Qr) {
	if (Ql > Qr)
		return;
	int mid(l + r >> 1), A(0), B(0);	
	f[mid] = g[mid] = a[mid];
	for (R int i(mid - 1); i >= l; --i) f[i] = max(f[i + 1], a[i]);
	for (R int i(mid + 1); i <= r; ++i) g[i] = max(g[i - 1], a[i]);
	for (R int i(Ql); i <= Qr; ++i)
		if (Q[i].l <= mid && Q[i].r >= mid)
			Ans[Q[i].pos] = max(f[Q[i].l], g[Q[i].r]);
		else
			Q[i].r < mid ? QL[++A] = Q[i] : QR[++B] = Q[i];
	if (l == r)
		return;	
	for (R int i(1); i <= A; ++i) Q[i + Ql - 1] = QL[i];
	for (R int i(1); i <= B; ++i) Q[Ql + A + i - 1] = QR[i];
	solve(l, mid, Ql, Ql + A - 1);
	solve(mid + 1, r, Ql + A, Ql + A + B - 1);
}
int main() {
	Input(n), Input(m);
	for (int i(1); i <= n; ++i) Input(a[i]);
	for (int i(1); i <= m; ++i) Input(Q[i].l), Input(Q[i].r), Q[i].pos = i;
	solve(1, n, 1, m);
	for (int i(1); i <= m; ++i) printf("%d\n", Ans[i]);
    return 0;
}