40pts求救

Ryanhao @ 2024-10-11 20:36:25

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e6+5;
int a[maxn];

struct node {
    int l,r;
    int max_now;
    int lazy_now_add, lazy_now_chg;
    bool is_chg;
} G[signed(maxn*3.2)];
inline int lch(int u) {
    return u<<1;
}
inline int rch(int u) {
    return lch(u)|1;
}

void push_up(int u) {
    G[u].max_now = max(G[lch(u)].max_now,G[rch(u)].max_now);
}
void build(int u, int l, int r) {
    G[u].l = l;
    G[u].r = r;
    if (l == r) {
        G[u].max_now = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(lch(u),l,mid);
    build(rch(u),mid+1,r);
    push_up(u);
}
void corr_add(int u, int k, int xk) {
    if (G[u].is_chg) {
        G[u].lazy_now_chg += k;
        G[u].max_now += k;
    } else {
        G[u].lazy_now_add += k;
        G[u].max_now += k;
    }
}
void corr_chg(int u, int k, int xk) {
    G[u].max_now = G[u].lazy_now_chg = k;
}
void push_down(int u) {
    corr_add(lch(u),G[u].lazy_now_add,-1);
    corr_add(rch(u),G[u].lazy_now_add,-1);
    G[u].lazy_now_add = 0;
    if (G[u].is_chg) {
        corr_chg(lch(u),G[u].lazy_now_chg,-1);
        corr_chg(rch(u),G[u].lazy_now_chg,-1);
        G[u].is_chg = 0;
        G[u].lazy_now_chg = 0;
    }
}

int query_now(int u, int s, int e) {
    if (s <= G[u].l && G[u].r <= e) {
        return G[u].max_now;
    }
    push_down(u);
    int ans = -2147483647;
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) ans = max(ans,query_now(lch(u),s,e)); 
    if (e >  mid) ans = max(ans,query_now(rch(u),s,e)); 
    return ans;
}
void add(int u, int s, int e, int w) {
    if (s <= G[u].l && G[u].r <= e) {
        corr_add(u,w,w);
        return;
    }
    push_down(u);
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) add(lch(u),s,e,w);
    if (e >  mid) add(rch(u),s,e,w); 
    push_up(u);
}
void chg(int u, int s, int e, int w) {
    if (s <= G[u].l && G[u].r <= e) {
        corr_chg(u,w,w);
        return;
    }
    push_down(u);
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) chg(lch(u),s,e,w);
    if (e >  mid) chg(rch(u),s,e,w); 
    push_up(u);
}

signed main() {
    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1,1,n);
    while(q--) {
        int op;
        int x,y;
        cin >> op >> x >> y;
        if (op == 3) {
            cout << query_now(1,x,y) << endl;
        }
        if (op == 2) {
            int w;
            cin >> w;
            add(1,x,y,w);
        }
        if (op == 1) {
            int w;
            cin >> w;
            chg(1,x,y,w);
        }
        //print(1);
    }
    return 0;
}

by Ivan422 @ 2024-10-11 20:43:17

chg tag 应该设置成 \infty

by zzz13579zzz @ 2024-10-11 20:59:45

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e6+5;
int a[maxn];

struct node {
    int l,r;
    int max_now;
    int lazy_now_add, lazy_now_chg;
    bool is_chg;
} G[maxn*4];
inline int lch(int u) {
    return u<<1;
}
inline int rch(int u) {
    return lch(u)|1;
}

void push_up(int u) {
    G[u].max_now = max(G[lch(u)].max_now,G[rch(u)].max_now);
}
void build(int u, int l, int r) {
    G[u].l = l;
    G[u].r = r;
    if (l == r) {
        G[u].max_now = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(lch(u),l,mid);
    build(rch(u),mid+1,r);
    push_up(u);
}
void corr_add(int u, int k, int xk) {
    G[u].lazy_now_add += k;
    G[u].max_now += k;
}
void corr_chg(int u, int k, int xk) {
    G[u].is_chg=1;
    G[u].lazy_now_add = 0;
    G[u].max_now = G[u].lazy_now_chg = k;
}
void push_down(int u) {
    if (G[u].is_chg) {
        corr_chg(lch(u),G[u].lazy_now_chg,-1);
        corr_chg(rch(u),G[u].lazy_now_chg,-1);
        G[u].is_chg = 0;
        G[u].lazy_now_chg = 0;
    }
    if(G[u].lazy_now_add){
        corr_add(lch(u),G[u].lazy_now_add,-1);
        corr_add(rch(u),G[u].lazy_now_add,-1);
        G[u].lazy_now_add = 0;      
    }
}

int query_now(int u, int s, int e) {
    if (s <= G[u].l && G[u].r <= e) {
        return G[u].max_now;
    }
    push_down(u);
    int ans = -1e18;
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) ans = max(ans,query_now(lch(u),s,e)); 
    if (e >  mid) ans = max(ans,query_now(rch(u),s,e)); 
    return ans;
}
void add(int u, int s, int e, int w) {
    if (s <= G[u].l && G[u].r <= e) {
        corr_add(u,w,w);
        return;
    }
    push_down(u);
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) add(lch(u),s,e,w);
    if (e >  mid) add(rch(u),s,e,w); 
    push_up(u);
}
void chg(int u, int s, int e, int w) {
    if (s <= G[u].l && G[u].r <= e) {
        corr_chg(u,w,w);
        return;
    }
    push_down(u);
    int mid = (G[u].l+G[u].r)/2;
    if (s <= mid) chg(lch(u),s,e,w);
    if (e >  mid) chg(rch(u),s,e,w); 
    push_up(u);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1,1,n);
    while(q--) {
        int op;
        int x,y;
        cin >> op >> x >> y;
        if (op == 3) {
            cout << query_now(1,x,y) << endl;
        }
        if (op == 2) {
            int w;
            cin >> w;
            add(1,x,y,w);
        }
        if (op == 1) {
            int w;
            cin >> w;
            chg(1,x,y,w);
        }
        //print(1);
    }
    return 0;
}

A了