四叉树,样例都没过,一直输出8,求调
查看原帖
四叉树,样例都没过,一直输出8,求调
464528
见贤思齐_Seakies楼主2023/1/21 12:48
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct Segment_Tree {
    int l, r, u, d, Max, lazy_tag;
    #define luson(o) tr[(o << 2) + 1]
    #define ruson(o) tr[(o << 2) + 2]
    #define ldson(o) tr[(o << 2) + 3]
    #define rdson(o) tr[(o << 2) + 4]
    #define midx ((tr[o].l + tr[o].r) >> 1)
    #define midy ((tr[o].u + tr[o].d) >> 1)
} tr[MAXN * MAXN * 4];
void push_up(int o) {
    tr[o].Max = max(max(luson(o).Max, ruson(o).Max), max(ldson(o).Max, rdson(o).Max));
}
void push_down(int o) {
    if (tr[o].lazy_tag) {
        luson(o).lazy_tag = tr[o].lazy_tag;
        luson(o).Max = tr[o].lazy_tag;
        if (tr[o].l != tr[o].r) {
            ruson(o).lazy_tag = tr[o].lazy_tag;
            ruson(o).Max = tr[o].lazy_tag;
        }
        if (tr[o].u != tr[o].d) {
            ldson(o).lazy_tag = tr[o].lazy_tag;
            ldson(o).Max = tr[o].lazy_tag;
        }
        if (tr[o].l != tr[o].r && tr[o].u != tr[o].d) {
            rdson(o).lazy_tag = tr[o].lazy_tag;
            rdson(o).Max = tr[o].lazy_tag;
        }
        tr[o].lazy_tag = 0;
    }
}
void build(int o, int l, int r, int u, int d) {
    tr[o].l = l, tr[o].r = r, tr[o].u = u, tr[o].d = d;
    if (l == r && u == d) {
        tr[o].Max = 0;
        return;
    }
    build((o << 2) + 1, l, midx, u, midy);
    if (l != r) build((o << 2) + 2, midx + 1, r, u, midy);
    if (u != d) build((o << 2) + 3, l, midx, midy + 1, d);
    if (l != r && u != d) build((o << 2) + 4, midx + 1, r, midy + 1, d);
    push_up(o);
}
void modify(int o, int l, int r, int u, int d, int v) {
    if (tr[o].l <= l && tr[o].r >= r && tr[o].u <= u && tr[o].d >= d) {
        tr[o].Max = v;
        tr[o].lazy_tag = v;
        return;
    }
    push_down(o);
    if (l <= midx && u <= midy) modify((o << 2) + 1, l, r, u, d, v);
    if (tr[o].l != tr[o].r && r > midx && u <= midy) modify((o << 2) + 2, l, r, u, d, v);
    if (tr[o].u != tr[o].d && l <= midx && d > midy) modify((o << 2) + 3, l, r, u, d, v);
    if (tr[o].l != tr[o].r && tr[o].u != tr[o].d && r > midx && d > midy) modify((o << 2) + 4, l, r, u, d, v);
    push_up(o);
}
int query(int o, int l, int r, int u, int d) {
    if (tr[o].l <= l && tr[o].r >= r && tr[o].u <= u && tr[o].d >= d) return tr[o].Max; 
    int ans = 0;
    push_down(o);
    if (l <= midx && u <= midy) ans = max(ans, query((o << 2) + 1, l, r, u, d));
    if (tr[o].l != tr[o].r && r > midx && u <= midy) ans = max(ans, query((o << 2) + 2, l, r, u, d));
    if (tr[o].u != tr[o].d && l <= midx && d > midy) ans = max(ans, query((o << 2) + 3, l, r, u, d));
    if (tr[o].l != tr[o].r && tr[o].u != tr[o].d && r > midx && d > midy) ans = max(ans, query((o << 2) + 4, l, r, u, d));
    return ans;
}
int D, S, N;
int main() {
    scanf("%d%d%d", &D, &S, &N);
    build(1, 1, D, 1, S);
    while (N--) {
        int d, s, h, x, y;
        scanf("%d%d%d%d%d", &d, &s, &h, &x, &y);
        h += query(1, x + 1, x + d, y + 1, y + s);
        modify(1, x + 1, x + d, y + 1, y + s, h);
    }
    printf("%d\n", query(1, 1, D, 1, S));
    return 0;
}
2023/1/21 12:48
加载中...