zkw线段树46pts求助

lateworker @ 2023-12-16 12:15:25

#include <iostream>
using namespace std;
#define int long long
const int N = 5e5+10, inf = 1010;
struct Segment_Tree{ int m, l, r, s; } st[N<<4];    // s:all, m:max, l:lmax, r:rmax
inline Segment_Tree merge(Segment_Tree a, Segment_Tree b) {
    return {
        max(max(a.m, b.m), a.r+b.l),
        max(a.l, a.s+b.l),
        max(b.r, b.s+a.r),
        a.s+b.s
    };
}
#define le (u<<1)
#define ri (u<<1|1)
int n, m, tn, a[N];
inline void build() {
    for(tn=1;tn<=n+1;tn<<=1);
    for(int i=1;i<=n;++i) st[i+tn] = {a[i], a[i], a[i], a[i]};
    for(int u=tn-1;u;--u) st[u]=merge(st[le], st[ri]);
}
inline void update(int u, int v) {
    u+=tn, st[u] = {v, v, v, v};
    for(u>>=1;u;u>>=1) st[u]=merge(st[le], st[ri]);
}
inline int query(int l, int r) {
    Segment_Tree ansl = {-inf,-inf,-inf,-inf};
    Segment_Tree ansr = {-inf,-inf,-inf,-inf};
    for(l+=tn-1,r+=tn+1;l^r^1;l>>=1,r>>=1) {
        if(~l&1) ansl = ansl.s==-inf?st[l^1]:merge(ansl, st[l^1]);
        if(r&1) ansr = ansr.s==-inf?st[r^1]:merge(st[r^1], ansr);
    }
    if(ansl.s==-inf) return ansr.m;
    if(ansr.s==-inf) return ansl.m;
    return merge(ansl, ansr).m;
}
signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    build();
    while(m--) {
        int k; cin>>k;
        if(k==1) {
            int a, b; cin>>a>>b;
            if(a > b) swap(a, b);
            cout<<query(a, b)<<"\n";
        } else {
            int p, s; cin>>p>>s;
            update(p, s);
        }
    }
    return 0;
}

by lateworker @ 2023-12-16 12:21:13

为什么把所有特判删了就能过？

#include <iostream>
using namespace std;
const int N = 5e5+10, inf = 1010;
struct Segment_Tree{ int m, l, r, s; } st[N<<2];    // s:all, m:max, l:lmax, r:rmax
inline Segment_Tree merge(Segment_Tree a, Segment_Tree b) {
    Segment_Tree ret;
    ret.m = max(max(a.m, b.m), a.r+b.l);
    ret.l = max(a.l, a.s+b.l);
    ret.r = max(b.r, b.s+a.r);
    ret.s = a.s+b.s;
    return ret;
}
#define le (u<<1)
#define ri (u<<1|1)
int n, m, tn, a[N];
inline void build() {
    for(tn=1;tn<=n+1;tn<<=1);
    for(int i=1;i<=n;++i) st[i+tn] = {a[i], a[i], a[i], a[i]};
    for(int u=tn-1;u;--u) st[u]=merge(st[le], st[ri]);
}
inline void update(int u, int v) {
    u+=tn, st[u] = {v, v, v, v};
    for(u>>=1;u;u>>=1) st[u]=merge(st[le], st[ri]);
}
inline int query(int l, int r) {
    Segment_Tree ansl = {-inf,-inf,-inf,-inf};
    Segment_Tree ansr = {-inf,-inf,-inf,-inf};
    for(l+=tn-1,r+=tn+1;l^r^1;l>>=1,r>>=1) {
        if(~l&1) ansl=merge(ansl, st[l^1]);
        if(r&1) ansr=merge(st[r^1], ansr);
    }
    return merge(ansl, ansr).m;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    build();
    while(m--) {
        int k; cin>>k;
        if(k==1) {
            int a, b; cin>>a>>b;
            if(a > b) swap(a, b);
            cout<<query(a, b)<<"\n";
        } else {
            int p, s; cin>>p>>s;
            update(p, s);
        }
    }
    return 0;
}

by sfqxx1 @ 2023-12-16 12:40:25

@lateworker 有没有可能特判不正确(？

by lateworker @ 2023-12-16 12:56:29

@sfqxx1 有可能, 但为什么不特判也能过?

by sfqxx1 @ 2023-12-16 12:58:29

@lateworker 或许这个程序已经是正解，不需要特判了吧。