线段树最大与最小值模板

模板：

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5 + 5; int t; int n,m; int x, y, k; int a[N]; //线段树最大与最小值的模板 struct tree{ int l, r; int sum, lmax, rmax, mx; int msum, lmin, rmin, mi; }tr[N * 4]; void pushup(tree &u, tree l, tree r){ u.sum = l.sum + r.sum; u.lmax = max(l.lmax, l.sum+r.lmax); u.rmax = max(l.rmax+r.sum, r.rmax); u.mx = max(max(l.mx, r.mx), l.rmax+r.lmax); u.msum = l.msum + r.msum; u.lmin = min(l.lmin, l.msum+r.lmin); u.rmin = min(l.rmin+r.msum, r.rmin); u.mi = min(min(l.mi, r.mi), l.rmin+r.lmin); } void build(int u, int l, int r){ tr[u] = {l, r, a[l], a[l], a[l], a[l], a[l], a[l], a[l], a[l]}; if (l == r)return ; int mid = (l + r)/2; build(u*2, l, mid); build(u<<1|1, mid + 1, r); pushup(tr[u], tr[u*2], tr[u<<1|1]); } tree Query(int u, int l, int r){ if (l <= tr[u].l && r >= tr[u].r) { return tr[u]; } int mid = (tr[u].l + tr[u].r)/2; if (y <= mid)return Query(u << 1, x, y); if (x > mid)return Query(u << 1|1, x, y); tree T; pushup(T, Query(u << 1, x, y), Query(u << 1| 1, x, y)); return T; } void solve(){ cin >> n ; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); cin >> m; for (int i = 1; i <= m; i++) { cin >> x >> y; tree tr; tr=Query(1,x,y); cout << max(abs(tr.mx), abs(tr.mi)) << \n; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); t = 1; while(t--){ solve(); } return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576