最后一个点RE,数据范围从4倍改到8倍后AC

P1253 扶苏的问题

Bodhi @ 2022-07-17 23:36:15

请问为什么开4倍不行呢?

测评结果

源代码:

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

#define ls k << 1
#define rs k << 1 | 1
#define MIN -1e14
using ll = long long;
const int R = 1e6 + 10;
ll ma[R << 3], rep[R << 3], add[R << 3], t[R];
inline void pushup(int k)
{
    ma[k] = max(ma[ls], ma[rs]);
}
inline void repdown(int k)
{
    if (rep[k] != MIN)
    {
        add[ls] = add[rs] = 0;
        rep[ls] = rep[rs] = rep[k];
        ma[ls] = ma[rs] = rep[k];
        rep[k] = MIN;
    }
}
inline void adddown(int k)
{
    if (add[k])
    {
        repdown(k);
        ma[ls] += add[k], ma[rs] += add[k];
        add[ls] += add[k], add[rs] += add[k];
        add[k] = 0;
    }
}
inline void pushdown(int k)
{
    repdown(k);
    adddown(k);
}
void build(int k, int l, int r)
{
    // cout << k;
    if (l == r)
    {
        ma[k] = t[l];
        // rep[k] = LLONG_MIN; //这句可不写,因为后面会将rep[j]赋值为LLONG_MIN
        return; //不要忘记return
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(k);
}
void repupdate(int k, int l, int r, int x, int y, int v)
{
    if (l >= x && r <= y)
    {
        add[k] = 0;
        rep[k] = v;
        ma[k] = v;
        return;
    }
    pushdown(k);
    int mid = l + r >> 1;
    if (x <= mid)
    {
        repupdate(ls, l, mid, x, y, v);
    }
    if (y > mid)
    {
        repupdate(rs, mid + 1, r, x, y, v);
    }
    pushup(k);
}
void addupdate(int k, int l, int r, int x, int y, int v)
{
    if (l >= x && r <= y)
    {
        repdown(k);
        ma[k] += v;
        add[k] += v;
        return;
    }
    pushdown(k);
    int mid = l + r >> 1;
    if (x <= mid)
    {
        addupdate(ls, l, mid, x, y, v);
    }
    if (y > mid)
    {
        addupdate(rs, mid + 1, r, x, y, v);
    }
    pushup(k);
}
ll query(int k, int l, int r, int x, int y)
{
    if (l >= x && r <= y)
    {
        return ma[k];
    }
    pushdown(k);
    ll res = MIN;
    int mid = l + r >> 1;
    if (x <= mid)
    {
        res = max(res, query(ls, l, mid, x, y));
    }
    if (y > mid)
    {
        res = max(res, query(rs, mid + 1, r, x, y));
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    register int j;
    for (j = 1; j <= n; ++j)
    {
        cin >> t[j];
    }
    build(1, 1, n);
    int t = n << 2;
    for (j = 1; j <= t; ++j)
    {
        rep[j] = MIN;
    }
    int x, y, k;
    char c;
    for (j = 1; j <= q; ++j)
    {
        cin >> c >> x >> y;
        if (c == '1')
        {
            cin >> k;
            repupdate(1, 1, n, x, y, k);
        }
        else if (c == '2')
        {
            cin >> k;
            addupdate(1, 1, n, x, y, k);
        }
        else
        {
            cout << query(1, 1, n, x, y) << "\n";
        }
    }
    // for (j = 1; j <= n * 4; ++j)
    // {
    //  cout << rep[j] << "\n";
    // }
    return 0;
}

by Bodhi @ 2022-07-17 23:44:46

补充链接https://www.luogu.com.cn/record/list?pid=P1253&user=364848


by Xeqwq @ 2022-07-17 23:44:58

@Bodhi 随着越来越多的人通过开大数组ac这道题(包括我) 我开始怀疑是不是数据点的锅(


by Xeqwq @ 2022-07-17 23:45:21

这道题这个问题看到少说三回了(


by Dr_Gilbert @ 2022-07-18 07:30:51

@Bodhi @整活队长xeq 我数组开 4\times 10^6 过了本题,建议从自己代码上找找原因。


by BHY123 @ 2022-07-18 09:58:29

pushdown操作如果在叶子结点上进行就会访问到无效内存,解决方法可以是空间开大一倍或者在pushdown前先判断节点是否为叶子节点


by Bodhi @ 2022-07-19 14:17:11

@BHY123 明白了,谢谢


by JEB_Bem @ 2022-08-26 21:36:58

我开 1e6+100 * 4能过的,以前我也是在叶子节点上 pushdown 过,所以 if 里面最好不要写 pushdown,血的教训啊


|