MLE求调!

P3372 【模板】线段树 1

xuanzeiliza @ 2024-11-06 20:30:57

#include<iostream>
#define ll long long

using namespace std;
ll tree[400005];
int nums[100005];
int tag[400005];
ll t, _;

void buildtree(ll l, ll r, ll p)
{
    if (l == r) {
        tree[p] = nums[l];
    }
    else {
        ll mid = r + (l - r) >> 1;
        buildtree(l, mid, p << 1);
        buildtree(mid + 1, r, (p << 1) + 1);
        tree[p] = tree[p << 1] + tree[(p << 1) + 1];
    }
}
//对已经打上去的tag进行下放
void xiafang(ll l0, ll r0, ll p)
{
    tree[p] += tag[p] * (r0 + 1 - l0);
    ll m = tag[p];//存储
    tag[p] = 0;
    if (l0 == r0)return;
    ll mid = r0 + (l0 - r0) >> 1;
    tag[p << 1] = m;
    tag[(p << 1) + 1] = m;
}

void gaiqujian(ll l, ll r, ll l0, ll r0, ll p, ll x)
{
    if (tag[p]) xiafang(l0, r0, p);
    if (l == l0 && r == r0) {
        tag[p] = x;
        return;
    }
    tree[p] += x * (r + 1 - l);
    ll mid = l0 + (r0 - l0) >> 1;
    if (l <= mid)gaiqujian(l, mid, l0, mid, p << 1, x);
    if (r > mid)gaiqujian(mid + 1, r, mid + 1, r0, (p << 1) + 1, x);
}

ll queryqujian(ll l, ll r, ll l0, ll r0, ll p)
{
    if (tag[p]) xiafang(l0, r0, p);
    if (l == l0 && r == r0)return tree[p];
    ll mid = (r0 + l0) >> 1;
    ll sum = 0;
    if (l <= mid) sum += queryqujian(l, mid, l0, mid, p << 1);
    if (r > mid) sum += queryqujian(mid + 1, r, mid + 1, r0, (p << 1) + 1);
    return sum;
}

int main()
{
    cin >> t >> _;
    for (ll i = 1; i <= t; i++)
    {
        cin >> nums[i];
    }
    buildtree(1, t, 1);
    ll v, n, m, x;
    while (_--)
    {
        cin >> v;
        if (v == 1) {
            cin >> n >> m >> x;
            gaiqujian(n, m, 1, t, 1, x);
        }
        else if (v == 2) {
            cin >> n >> m;
            cout << queryqujian(n, m, 1, t, 1);
        }
    }

    return 0;
}

不管怎么调内存都会爆,求大佬帮帮忙


by yyyhy @ 2024-11-06 20:37:35

ll mid = l0 + (r0 - l0) >> 1; 改为 ll mid = l0 + r0 >> 1;


by yyyhy @ 2024-11-06 20:37:52

@xuanzeiliza


by yyyhy @ 2024-11-06 20:42:33

因为 >> 优先级小于 +-

所以先算 +- 再算 >>

就等价成 r0>>1


by xuanzeiliza @ 2024-11-07 07:26:11

@yyyhy 谢谢大佬提醒,但是改过来之后还是内存爆了怎么办啊啊啊


by yyyhy @ 2024-11-07 08:25:42

@xuanzeiliza 三处都改了吗


by xuanzeiliza @ 2024-11-07 10:33:51

@yyyhy 感谢大佬提醒,有一个改忘了,谢谢您已经ac


by CaoSheng_zzz @ 2024-11-10 19:02:09

必须留名


|