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
必须留名