60分求助,再调不过男朋友要跟人跑了

P1253 扶苏的问题

刘辰雨 @ 2023-04-12 12:11:08

#include <iostream>
#include <cstdio>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;

struct node {
    node *lson, *rson;
    int lside, rside;
    long long maxv, lazychange, lazyadd;
    node() {
        this->lson = this->rson = NULL;
        this->lside = this->rside = 0;
        this->maxv = this->lazychange = this->lazyadd = -INF;
    }
}; 

void build(node *now, int l, int r) {
    now->lside = l;
    now->rside = r;
    if(l != r) {
        now->lson = new node;
        now->rson = new node;
        build(now->lson, l, (l+r)>>1);
        build(now->rson, ((l+r)>>1)+1, r);
    }
}

void update_add(node *now) {
    if(now->lazyadd != -INF) {
        if(now->lson) {
            now->lson->maxv += now->lazyadd;
            now->lson->lazyadd = now->lson->lazyadd == -INF ? now->lazyadd : now->lson->lazyadd + now->lazyadd;
        }
        if(now->rson) {
            now->rson->maxv += now->lazyadd;
            now->rson->lazyadd = now->rson->lazyadd == -INF ? now->lazyadd : now->rson->lazyadd + now->lazyadd;
        }
    }
    now->lazyadd = -INF;
}

void update_change(node *now) {
    if(now->lazychange != -INF) {
        if(now->lson) {
            now->lson->maxv = now->lazychange;
            now->lson->lazychange = now->lazychange;
        }
        if(now->rson) {
            now->rson->maxv = now->lazychange;
            now->rson->lazychange = now->lazychange;
        }
    }
    now->lazychange = -INF;
}

void change(node *now, int l, int r, long long v) {
    if(now->lside > r || now->rside < l) {
        return ;
    }
    if(now->lside >= l && now->rside <= r) {
        update_add(now);
        now->maxv = v;
        now->lazychange = v;
    } else {
        update_change(now);
        update_add(now);
        change(now->lson, l, r, v);
        change(now->rson, l, r, v);
        now->maxv = max(now->lson->maxv, now->rson->maxv);
    }
//  cout << now->lside << " " << now->rside << " " << now->maxv << " " << now->lazychange << " " << now->lazyadd << endl;
}

void add(node *now, int l, int r, long long v) {
    if(now->lside > r || now->rside < l) {
        return ;
    }
    if(now->lside >= l && now->rside <= r) {
        now->maxv += v;
        if(now->lazychange != -INF) {
            now->lazychange += v;
        } else {
            now->lazyadd = now->lazyadd == -INF ? v : now->lazyadd+v;
        }
    } else {
        update_change(now);
        update_add(now);
        add(now->lson, l, r, v);
        add(now->rson, l, r, v);
        now->maxv = max(now->lson->maxv, now->rson->maxv);
    }
}

long long query(node *now, int l, int r) {
    if(now->lside > r || now->rside < l) {
        return -INF;
    }
    if(now->lside >= l && now->rside <= r) {
//      cout << now->lside << " " << now->rside << " " << now->maxv << " " << now->lazyadd << " " << now->lazychange << " now." << endl;
        return now->maxv;
    } else {
        update_change(now);
        update_add(now);
        return max(query(now->lson, l, r), query(now->rson, l, r));
    }
}

int n, q, opt, x, y;
long long k;
node *root;

int main() {
    scanf("%d%d", &n, &q);
    root = new node;
    build(root, 1, n);
    for(int i = 1 ; i<= n ; i++) {
        scanf("%lld", &k);
        change(root, i, i, k);
    }
    while(q--) {
        scanf("%d", &opt);
        if(opt == 1) {
            scanf("%d%d%lld", &x, &y, &k);
            change(root, x, y, k);
        } else if(opt == 2) {
            scanf("%d%d%lld", &x, &y, &k);
            add(root, x, y, k);
        } else {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(root, x, y));
        }
    }
    return 0;
}

Wa on #7->#10


by 一扶苏一 @ 2023-04-12 12:25:12

@刘辰雨 下传和打 change tag 的时候要先把当前节点的 add tag 清空,不然 change 以前的 add 操作也会产生影响。


by zjx331 @ 2023-04-12 12:27:48

!扶苏换头像了!


by Imken @ 2023-04-12 13:51:23

你说得对,但是lz是男的(


by 刘辰雨 @ 2023-04-12 13:57:45

@immccn123

但你也不能肯定 title 就是错的


by Imken @ 2023-04-12 16:16:02

@刘辰雨 原来我一直看错你了


by 刘辰雨 @ 2023-04-12 21:04:10

@一扶苏一 谢谢,A了。

(这太让我受宠若惊了,虽然男朋友还是跟人跑了 (;′⌒`)


|