题目传送门
本题调试过程中，出现了奇怪的问题： \(G++\) \(AC\) ,\(C++\) \(Complie\) \(Error\)
以后调用\(POJ\),还是老实的\(G++\)吧~
//#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const int N = 50010; int a[N]; struct node { int l, r, Max, Min; } t[N << 2]; int Max, Min; void pushup(int u) { t[u].Max = max(t[u << 1].Max, t[u << 1 | 1].Max); t[u].Min = min(t[u << 1].Min, t[u << 1 | 1].Min); } void build(int u, int l, int r) { t[u] = {l, r}; if (l == r) { t[u].Max = a[l], t[u].Min = a[l]; return; } int mid = (l + r) >> 1; build(u << 1, l, mid); //左孩子 build(u << 1 | 1, mid + 1, r); //右孩子 //向上推送信息 pushup(u); } void query(int u, int l, int r) { if (l <= t[u].l && r >= t[u].r) Max = max(Max, t[u].Max), Min = min(Min, t[u].Min); else { int mid = (t[u].l + t[u].r) >> 1; if (r <= mid) query(u << 1, l, r); else if (l >= mid + 1) query(u << 1 | 1, l, r); else query(u << 1, l, r), query(u << 1 | 1, l, r); } } int main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); while (q--) { Max = -INF, Min = INF; int l, r; scanf("%d%d", &l, &r); query(1, l, r); printf("%d\n", Max - Min); } return 0; }