线段树全WA求助
查看原帖
线段树全WA求助
366937
too_simple楼主2023/4/9 20:26

为啥答案一直报Wrong Answer.wrong answer Too short on line 1.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

const int N = 1e5 + 10, INF = 0x7fffffff;

int n, m;
int a[N];
char op[1];
int x, y, z;

struct node {
    int l, r;
    int ans, m_ans;
    int sum, val;
    int m_sum, m_val;
    bool vis;
}tr[N << 2];

void pushup(int u) {
    tr[u].ans = max(tr[u << 1].ans, tr[u << 1 | 1].ans);
    tr[u].m_ans = max(tr[u << 1].m_ans, tr[u << 1 | 1].m_ans);
}

void add_sum(int u, int k, int m_k) {
    if(tr[u].vis) {
        tr[u].m_val = max(tr[u].m_val, tr[u].val + m_k);
        tr[u].m_ans = max(tr[u].m_ans, tr[u].ans + m_k);
        tr[u].val += k;
        tr[u].ans += k;
    } else {
        tr[u].m_sum = max(tr[u].m_sum, tr[u].sum + m_k);
        tr[u].m_ans = max(tr[u].m_ans, tr[u].ans + m_k);
        tr[u].sum += k;
        tr[u].ans += k;
    }
}

void add_val(int u, int k, int m_k) {
    if(tr[u].vis) {
        tr[u].m_val = max(tr[u].m_val, m_k);
        tr[u].m_ans = max(tr[u].m_ans, m_k);
    } else {
        tr[u].vis = true;
        tr[u].m_val = m_k;
        tr[u].m_ans = max(tr[u].m_ans, m_k);
    }
    tr[u].val = tr[u].ans = k;
}

void pushdown(int u) {
    add_sum(u << 1, tr[u].sum, tr[u].m_sum);
    add_sum(u << 1 | 1, tr[u].sum, tr[u].m_sum);
    tr[u].sum = tr[u].m_sum = 0;
    if(tr[u].vis) {
        add_val(u << 1, tr[u].val, tr[u].m_val);
        add_val(u << 1 | 1, tr[u].val, tr[u].m_val);
        tr[u].vis = false;
        tr[u].val = tr[u].m_val = 0;
    }
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 0, 0, 0, 0, false};
    if(l == r) {
        tr[u].ans = tr[u].m_ans = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query(int u, int l, int r, int op) {
    if(l <= tr[u].l && tr[u].r <= r) {
        if(op == 1) return tr[u].ans;
        return tr[u].m_ans;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1, ans = -INF;
    if(l <= mid) ans = query(u << 1, l, r, op);
    if(mid < r) ans = max(ans, query(u << 1 | 1, l, r, op));
    return ans;
}

void modify(int u, int l, int r, int v, int op) {
    if(l <= tr[u].l && tr[u].r <= r) {
        if(op == 1) {
            add_sum(u, v, v);
        } else {
            add_val(u, v, v);
        }
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, v, op);
    if(mid < r) modify(u << 1 | 1, l, r, v, op);
    pushup(u);
}

signed main() {
    
    cin >> n;
    
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    
    build(1, 1, n);
    
    cin >> m;
    
    while(m -- ) {
        cin >> op;
        if(op[0] == 'Q') {
            scanf("%lld%lld", &x, &y);
            cout << query(1, x, y, 1) << endl;
        } else if(op[0] == 'A') {
            scanf("%lld%lld", &x, &y);
            cout << query(1, x, y, 2) << endl;
        } else if(op[0] == 'P') {
            scanf("%lld%lld%lld", &x, &y, &z);
            modify(1, x, y, z, 1);
        } else {
            scanf("%lld%lld%lld", &x, &y, &z);
            modify(1, x, y, z, 2);
        }
    }
    
    return 0;
}
2023/4/9 20:26
加载中...