线段树 9pts 求助，悬赏 3 关注，球球大佬们救救孩子吧

Syrus @ 2023-08-12 17:58:24

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10, INF = 1e18;

int Park, Operation;
int Points[N];
struct Segment
{
    int L, R;
    int Sum, Max;
    int Max_L, Max_R;
}Tree[N * 4];
struct Result
{
    int Sum;
    int Max, Max_L, Max_R;
};

Result Get_Max(Result A, Result B)
{
    int T0 = A.Sum + B.Sum;
    int T1 = max(max(A.Max, B.Max), A.Max_R + B.Max_L);
    int T2 = max(A.Max_L, A.Sum + B.Max_L);
    int T3 = max(B.Max_R, A.Max_R + B.Sum);

    return {T0, T1, T2, T3};
}

void Pushup(int u)
{
    Tree[u].Sum = Tree[u << 1].Sum + Tree[u << 1 | 1].Sum;
    bool Flag1 = (Tree[u << 1].Max_R < 0), Flag2 = (Tree[u << 1 | 1].Max_L < 0);
    if ((Flag1 && Flag2) || (Flag1 | Flag2)) Tree[u].Max = max(Tree[u << 1].Max_L, Tree[u << 1 | 1].Max_R);
    else Tree[u].Max = Tree[u << 1].Max_R + Tree[u << 1 | 1].Max_L;
    Tree[u].Max_L = max(Tree[u << 1].Sum + Tree[u << 1 | 1].Max_L, Tree[u << 1].Max_L);
    Tree[u].Max_R = max(Tree[u << 1].Max_R + Tree[u << 1 | 1].Sum, Tree[u << 1 | 1].Max_R);
}

void Build(int u, int l, int r)
{
    if (l == r)
        Tree[u] = {l, l, Points[l], Points[l], Points[l], Points[l]};
    else
    {
        Tree[u] = {l, r, 0, -INF, -INF, -INF};
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        Pushup(u);
    }
}

void Modify(int u, int Position, int Value)
{
    if (Tree[u].L == Tree[u].R && Tree[u].L == Position)
        Tree[u] = {Tree[u].L, Tree[u].R, Value, Value, Value, Value};
    else
    {
        int mid = Tree[u].L + Tree[u].R >> 1;
        if (mid >= Position) Modify(u << 1, Position, Value);
        else Modify(u << 1 | 1, Position, Value);
        Pushup(u);
    }
}

Result Query(int u, int l, int r)
{
    if (Tree[u].L >= l && Tree[u].R <= r)
        return {Tree[u].Max, Tree[u].Max_L, Tree[u].Max_R};

    int mid = Tree[u].L + Tree[u].R >> 1;
    Result Answer;
    if (mid >= l && mid < r)
        Answer = Get_Max(Query(u << 1, l, r), Query(u << 1 | 1, l, r));
    else if (mid >= l)
        Answer = Query(u << 1, l, r);
    else
        Answer = Query(u << 1 | 1, l, r);

    return Answer;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> Park >> Operation;

    for (int i = 1; i <= Park; i ++)
        cin >> Points[i];

    Build(1, 1, Park);

    while (Operation --)
    {
        int op, l, r;

        cin >> op >> l >> r;

        if (op == 1)
        {
            if (l > r) swap(l, r);
            cout << Query(1, l, r).Max << endl;
        }
        else
            Modify(1, l, r);
    }

    return 0;
}

by _XHY20180718_ @ 2023-08-14 18:58:09

@Tiny_konnyaku

这里少赋值了sum return {Tree[u].Max, Tree[u].Max_L, Tree[u].Max_R};

还有pushup改了一下，不用那么麻烦

AC code:

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10, INF = 1e18;

int Park, Operation;
int Points[N];
struct Segment
{
    int L, R;
    int Sum, Max;
    int Max_L, Max_R;
}Tree[N * 4];
struct Result
{
    int Sum;
    int Max, Max_L, Max_R;
};

Result Get_Max(Result A, Result B)
{
    int T0 = A.Sum + B.Sum;
    int T1 = max(max(A.Max, B.Max), A.Max_R + B.Max_L);
    int T2 = max(A.Max_L, A.Sum + B.Max_L);
    int T3 = max(B.Max_R, A.Max_R + B.Sum);

    return {T0, T1, T2, T3};
}

void Pushup(int u)
{
    Tree[u].Sum = Tree[u << 1].Sum + Tree[u << 1 | 1].Sum;
    bool Flag1 = (Tree[u << 1].Max_R < 0), Flag2 = (Tree[u << 1 | 1].Max_L < 0);
    if ((Flag1 && Flag2) || (Flag1 | Flag2)) Tree[u].Max = max(Tree[u << 1].Max_L, Tree[u << 1 | 1].Max_R);
    else Tree[u].Max = Tree[u << 1].Max_R + Tree[u << 1 | 1].Max_L;
    Tree[u].Max_L = max(Tree[u << 1].Sum + Tree[u << 1 | 1].Max_L, Tree[u << 1].Max_L);
    Tree[u].Max_R = max(Tree[u << 1].Max_R + Tree[u << 1 | 1].Sum, Tree[u << 1 | 1].Max_R);
}

void Build(int u, int l, int r)
{
    if (l == r)
        Tree[u] = {l, l, Points[l], Points[l], Points[l], Points[l]};
    else
    {
        Tree[u] = {l, r, 0, -INF, -INF, -INF};
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        Pushup(u);
    }
}

void Modify(int u, int Position, int Value)
{
    if (Tree[u].L == Tree[u].R && Tree[u].L == Position)
        Tree[u] = {Tree[u].L, Tree[u].R, Value, Value, Value, Value};
    else
    {
        int mid = Tree[u].L + Tree[u].R >> 1;
        if (mid >= Position) Modify(u << 1, Position, Value);
        else Modify(u << 1 | 1, Position, Value);
        Pushup(u);
    }
}

Result Query(int u, int l, int r)
{
    if (Tree[u].L >= l && Tree[u].R <= r)
        return {Tree[u].Max, Tree[u].Max_L, Tree[u].Max_R};

    int mid = Tree[u].L + Tree[u].R >> 1;
    Result Answer;
    if (mid >= l && mid < r)
        Answer = Get_Max(Query(u << 1, l, r), Query(u << 1 | 1, l, r));
    else if (mid >= l)
        Answer = Query(u << 1, l, r);
    else
        Answer = Query(u << 1 | 1, l, r);

    return Answer;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> Park >> Operation;

    for (int i = 1; i <= Park; i ++)
        cin >> Points[i];

    Build(1, 1, Park);

    while (Operation --)
    {
        int op, l, r;

        cin >> op >> l >> r;

        if (op == 1)
        {
            if (l > r) swap(l, r);
            cout << Query(1, l, r).Max << endl;
        }
        else
            Modify(1, l, r);
    }

    return 0;
}

by Syrus @ 2023-08-15 07:29:33

@XHY20180718 感谢大佬，已关注~~~

by Syrus @ 2023-08-15 07:35:08

@XHY20180718 大佬，但您好像传成改之前的了(/ω＼)

by _XHY20180718_ @ 2023-08-15 07:55:26

@Tiny_konnyaku 抱歉，这才是：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10, INF = 1e18;

int Park, Operation;
int Points[N];
struct Segment
{
    int L, R;
    int Sum, Max;
    int Max_L, Max_R;
}Tree[N * 4];
struct Result
{
    int Sum;
    int Max, Max_L, Max_R;
};

Result Get_Max(Result A, Result B)
{
    int T0 = A.Sum + B.Sum;
    int T1 = max(max(A.Max, B.Max), A.Max_R + B.Max_L);
    int T2 = max(A.Max_L, A.Sum + B.Max_L);
    int T3 = max(B.Max_R, A.Max_R + B.Sum);

    return {T0, T1, T2, T3};
}

void Pushup(int u)
{
    Tree[u].Sum = Tree[u << 1].Sum + Tree[u << 1 | 1].Sum;
    Tree[u].Max = max(max(Tree[u << 1].Max, Tree[u << 1 | 1].Max),Tree[u << 1].Max_R + Tree[u << 1 | 1].Max_L);
    Tree[u].Max_L = max(Tree[u << 1].Sum + Tree[u << 1 | 1].Max_L, Tree[u << 1].Max_L);
    Tree[u].Max_R = max(Tree[u << 1].Max_R + Tree[u << 1 | 1].Sum, Tree[u << 1 | 1].Max_R);
}

void Build(int u, int l, int r)
{
    if (l == r)
        Tree[u] = {l, l, Points[l], Points[l], Points[l], Points[l]};
    else
    {
        Tree[u] = {l, r, 0, -INF, -INF, -INF};
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        Pushup(u);
    }
}

void Modify(int u, int Position, int Value)
{
    if (Tree[u].L == Tree[u].R && Tree[u].L == Position)
        Tree[u] = {Tree[u].L, Tree[u].R, Value, Value, Value, Value};
    else
    {
        int mid = Tree[u].L + Tree[u].R >> 1;
        if (mid >= Position) Modify(u << 1, Position, Value);
        else Modify(u << 1 | 1, Position, Value);
        Pushup(u);
    }
}

Result Query(int u, int l, int r)
{
    if (Tree[u].L >= l && Tree[u].R <= r)
        return {Tree[u].Sum,Tree[u].Max, Tree[u].Max_L, Tree[u].Max_R};

    int mid = Tree[u].L + Tree[u].R >> 1;
    Result Answer;
    if (mid >= l && mid < r)
        Answer = Get_Max(Query(u << 1, l, r), Query(u << 1 | 1, l, r));
    else if (mid >= l)
        Answer = Query(u << 1, l, r);
    else
        Answer = Query(u << 1 | 1, l, r);

    return Answer;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> Park >> Operation;

    for (int i = 1; i <= Park; i ++)
        cin >> Points[i];

    Build(1, 1, Park);

    while (Operation --)
    {
        int op, l, r;

        cin >> op >> l >> r;

        if (op == 1)
        {
            if (l > r) swap(l, r);
            cout << Query(1, l, r).Max << endl;
        }
        else
            Modify(1, l, r);
    }

    return 0;
}

by Syrus @ 2023-08-15 08:15:39

@XHY20180718 再次感谢