warn6 - 10,以及一个数据范围问题

P1253 扶苏的问题

Februrary @ 2024-03-16 15:36:29

#include <iostream>
#include <fstream>
using namespace std;
typedef long long ll;
const int maxn = 1000500;
ll a[maxn];
struct node {
    int l, r;
    ll w;               // 代表区间内最大的值
    ll tag1;            // 用于将区间均修改为x
    ll tag2;            // 用于将区间均加上x
    pair<int, int> q;   // 用于后面向下传标签时,确定两个标签的顺序
} stree[4 * maxn];
int n, q;
void pushup(const int u);
inline bool inRange(int L, int R, int l, int r) {return (l <= L) && (R <= r);}
inline bool outRange(int L, int R, int l, int r) {return (R < l) || (L > r);}

void build(const int u, int L, int R) {
    if(L == R) {
        stree[u].w = a[L];
        stree[u].l = stree[u].r = L;
        stree[u].tag1 = 1e9 + 1;                // 考虑数据范围<=1e9
        return;
    }

    stree[u].l = L;
    stree[u].r = R;
    stree[u].tag1 = 1e9 + 1;
    int M = (L + R) >> 1;
    build(2 * u, L, M);
    build(2 * u + 1, M + 1, R);
    pushup(u);
}

void maketag1(const int u, ll change_value) {
    // 防止下传标签被任意修改
    if(change_value == 1e9 + 1) return;
    stree[u].tag1 = change_value;
    stree[u].w = change_value;
    stree[u].q.first == 0 ? stree[u].q.first = 1 : stree[u].q.second = 1;
}

void maketag2(const int u, ll change_value) {
    stree[u].tag2 += change_value;
    stree[u].w += change_value;
    stree[u].q.first == 0 ? stree[u].q.first = 2 : stree[u].q.second = 2;
}

void pushdown(const int u) {
    // 两个标签的下传会有顺序,通过pair标记顺序
    if(stree[u].q.first == 1) {
        maketag1(2 * u, stree[u].tag1);
        maketag1(2 * u + 1, stree[u].tag1);
        maketag2(2 * u, stree[u].tag2);
        maketag2(2 * u + 1, stree[u].tag2);
    }
    else if(stree[u].q.first == 2) {
        maketag2(2 * u, stree[u].tag2);
        maketag2(2 * u + 1, stree[u].tag2);
        maketag1(2 * u, stree[u].tag1);
        maketag1(2 * u + 1, stree[u].tag1);
    }

    stree[u].tag1 = 1e9 + 1;
    stree[u].tag2 = 0;
    stree[u].q.first = 0;
    stree[u].q.second = 0;
}

void pushup(const int u) {
    stree[u].w = max(stree[2 * u].w, stree[2 * u + 1].w);
}

void update(const int u, int l, int r, ll change_value, int opt) {
    int L = stree[u].l;
    int R = stree[u].r;
    if(inRange(L, R, l, r)) {
        if(opt == 1) maketag1(u, change_value);
        else maketag2(u, change_value);
        return;
    }
    else if(!outRange(L, R, l, r)) {
        int M = (L + R) >> 1;
        // 下放标签
        pushdown(u);
        update(2 * u, l, r, change_value, opt);
        update(2 * u + 1, l, r, change_value, opt);
        // 上传数据
        pushup(u);
    }
}

ll query(const int u, int l, int r) {
    int L = stree[u].l;
    int R = stree[u].r;
    if(inRange(L, R, l, r)) {
        return stree[u].w;
    }
    else if(outRange(L, R, l, r)) {
        return -1e12;
    }
    pushdown(u);
    return max(query(2 * u, l, r), query(2 * u + 1, l, r)); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    for(int j = 0; j < q; j++) {
        int opt = 0;
        int l ,r, x;
        cin >> opt;
        if(opt == 1) {
            cin >> l >> r >> x;
            update(1, l, r, x, opt);
        }
        else if(opt == 2) {
            cin >> l >> r >> x;
            update(1, l, r, x, opt);
        }
        else {
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }

    return 0;
}

无法通过6-10,还有另外一个问题
对于第6个测试点,query()函数第二个情况的返回值如果修改为-1e9就无法通过,题目说明的数据范围为abs(x) <= 1e9


by Februrary @ 2024-03-16 16:28:28

已经解决了,还是标记下传顺序的问题


|