RE求教

P4513 小白逛公园

ker_xyxyxyx_xxs @ 2021-07-14 11:45:47

```cpp # include <iostream> # include <cstdio> using namespace std; typedef long long ll; const int maxn = 5e5 + 5; int w[maxn]; int n , m , opt , x , y; typedef struct { int l , r; int maxl , maxr , maxp , val; } seg; seg tr[maxn * 4]; int max1(int , int); int max2(int , int , int); void update(int); int getl(int , int , int); int getr(int , int , int); void build(int , int , int); void modify(int , int , int); int query(int , int , int); int main() { scanf("%d%d" , &n , &m); for (int i = 1 ; i <= n ; i ++) { scanf("%d" , &w[i]); } build(1 , 1 , n); for (int i = 1 ; i <= m ; i ++) { scanf("%d%d%d" , &opt , &x , &y); if (opt == 1) { if (x > y) swap(x , y); printf("%d\n" , query(1 , x , y)); } else { modify(1 , x , y); } } return 0; } int max1(int a , int b) { return a > b ? a : b; } int max2(int a , int b , int c) { return max1(a , max1(b , c)); } void update(int p) { int ls = p << 1; int rs = p << 1 | 1; tr[p].val = tr[ls].val + tr[rs].val; tr[p].maxl = max1(tr[ls].maxl , tr[ls].val + tr[rs].maxl); tr[p].maxr = max1(tr[rs].maxr , tr[rs].val + tr[ls].maxr); tr[p].maxp = max2(tr[ls].maxp , tr[rs].maxp , tr[ls].maxr + tr[rs].maxl); } int getl(int p , int l , int r) { int ls = p << 1; int rs = p << 1 | 1; if (tr[p].r <= r) return tr[p].maxl; int mid = (tr[p].l + tr[p].r) >> 1; if (r < mid) return getl(ls , l , r); else { int tot = tr[ls].val + getl(rs , l , r); return max1(tr[ls].maxl , tot); } } int getr(int p , int l , int r) { int ls = p << 1; int rs = p << 1 | 1; if (l <= tr[p].l) return tr[p].maxr; int mid = (tr[p].l + tr[p].r) >> 1; if (l > mid) return getr(rs , l , r); else { int tot = tr[rs].val + getr(ls , l , r); return max1(tr[ls].maxr , tot); } } void build(int p , int l , int r) { tr[p].l = l; tr[p].r = r; if (l == r) { tr[p].val = w[l]; tr[p].maxl = tr[p].maxp = tr[p].maxr = tr[p].val; return ; } else { int mid = (l + r) >> 1; build(p << 1 , l , mid); build(p << 1 , mid + 1 , r); update(p); } } void modify(int p , int x , int d) { if (tr[p].l == x && tr[p].r == x) { tr[p].val = d; tr[p].maxl = tr[p].maxr = tr[p].maxp = tr[p].val; return ; } int mid = (tr[p].l + tr[p].r) >> 1; if (x <= mid) modify(p << 1 , x , d); else modify(p << 1 | 1 , x , d); update(p); } int query(int p , int l , int r) { int ls = p << 1; int rs = p << 1 | 1; if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxp; int mid = (tr[p].l + tr[p].r) >> 1; if (l > mid) return query(rs , l , r); if (r <= mid) return query(ls , l , r); if (l <= mid && r > mid) { int lans = query(ls , l , r); int rans = query(rs , l , r); int mans = getr(ls , l , r) + getl(rs , l , r); return max2(lans , rans , mans); } } ```

|