总是50分,求求爹们帮忙看看吧

P1253 扶苏的问题

WikDD @ 2024-08-02 00:19:47

#include<iostream>  
#include<cmath>  
#include<stdio.h>  
using namespace std;  
typedef long long ll;  
const int N = 1000010;  
ll arr[N], maxx[N*4], add[N*4], change[N*4];  
bool update[N*4];  
inline int read()  
{  
    int x = 0, f = 1; char ch = getchar();   
    while (ch < '0' || ch>'9'){if (ch == '-') f = -1; ch = getchar(); }  
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }  
    return x * f;  
}  
void up(int i)  
{  
    maxx[i] = max(maxx[i*2], maxx[i*2+1]);  
}  
void updatelazy(int i, ll v)    
{  
    maxx[i] = v;  
    add[i] = 0;  
    change[i] = v;  
    update[i] = true;  
}  
void addlazy(int i, ll v)  
{   
    maxx[i] += v;  
    add[i] += v;  
}   
void down(int i)  
{  
    if (update[i])  
    {  
        updatelazy(i*2, change[i]);  
        updatelazy(i*2+1, change[i]);  
        update[i] = false;  
    }  
    if (add[i] != 0)  
    {  
        addlazy(i*2, add[i]);  
        addlazy(i*2+1, add[i]);  
        add[i] = 0;  
    }  
}  
void build(int l, int r, int i)  
{  
    if (l == r)  
        maxx[i] = arr[l];  
    else  
    {  
        int mid = (l + r) / 2;  
        build(l, mid, i*2);  
        build(mid + 1, r, i*2+1);   
        up(i);  
    }  
    add[i] = 0;  
    change[i] = 0;  
    update[i] = false;  
}  
void Update(int jobl, int jobr, ll jobv, int l, int r, int i)  
{  
    if (jobl <= l && r <= jobr)  
        updatelazy(i, jobv);  
    else  
    {  
        int mid = (l + r) / 2;  
        down(i);  
        if (jobl <= mid)  
            Update(jobl, jobr, jobv, l, mid, i*2);  
        if (jobr > mid)  
            Update(jobl, jobr, jobv, mid + 1, r, i*2+1);  
        up(i);  
    }  
}  
void Add(int jobl, int jobr, ll jobv, int l, int r, int i)  
{  
    if (jobl <= l && r <= jobr)  
        addlazy(i, jobv);  
    else  
    {  
        int mid = (l + r) / 2;  
        down(i);  
        if (jobl <= mid)  
            Add(jobl, jobr, jobv, l, mid, i*2);  
        if (jobr > mid)  
            Add(jobl, jobr, jobv, mid + 1, r, i*2+1);  
        up(i);  
    }  
}  
ll query(int jobl, int jobr, int l, int r, int i)  
{  
    if (jobl <= l && r <= jobr)  
        return maxx[i];  
    int mid = (l + r) / 2;  
    down(i);  
    ll ans = -1000000010;  
    if (jobl <= mid)  
        ans = max(ans, query(jobl, jobr, l, mid, i*2));  
    if (jobr > mid)  
        ans = max(ans, query(jobl, jobr, mid + 1, r, i*2+1));  
    return ans;  
}  
int main()  
{  
    ll n, m;  
    n = read();  
    m = read();  
    for (ll i = 1; i <= n; i++)  
        arr[i] = read();  
    build(1, n, 1);  
    while (m--)  
    {  
        int zuo, x, y; ll k;  
        zuo = read();  
        if (zuo == 1)  
        {  
            x = read(); y = read(); k = read();  
            Update(x, y, k, 1, n, 1);  
        }  
        else if (zuo == 2)  
        {  
            x = read(); y = read(); k = read();  
            Add(x, y, k, 1, n, 1);  
        }  
        else  
        {  
            x = read(); y = read();  
            printf("%lld\n", query(x, y, 1, n, 1));  
        }  
    }  
}  

by 2024wangyuxuan @ 2024-08-02 07:07:06

你这是哪一题? 线段树求最大值+区间修改吗?


by forgotmyhandle @ 2024-08-02 07:56:12

@2024wangyuxuan 但凡你看一下这篇讨论的所属板块。


by 2024wangyuxuan @ 2024-08-02 08:01:57

@forgotmyhandle 我傻掉了


|