为什么re了!!!

P3372 【模板】线段树 1

LabmemNo_012LzTopic @ 2024-10-31 13:34:36

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std;

#define Max 100005

int tree[Max * 4] = { 0 }, a[Max] = { 0 }, k;

int creattree(int u, int l, int r)
{
    if (l == r)
    {
        return tree[u] = a[l];
    }
    int imd = (l + r) / 2;
    return tree[u] = creattree(u * 2, l, imd) + creattree(u * 2 + 1, imd + 1, r);
}

void treewh(int u, int l, int r, int x)
{
    tree[u] += k;
    if (u == x)return;
    int imd = (l + r) / 2;
    if (x >= l && x <= imd)treewh(u * 2, l, imd, x);
    else treewh(u * 2 + 1, imd + 1, r, x);
    return;
}

int querytree(int u, int l, int r, int L, int R)
{
    int imd = (l + r) / 2;
    if (l == L && r == R)return tree[u];
    if (imd < L)
    {
        return querytree(u * 2 + 1, imd + 1, r, L, R);
    }
    else if (imd + 1 > R)
    {
        return querytree(u * 2, l, imd, L, R);
    }
    else
    {
        return querytree(u * 2, l, imd, L, imd) + querytree(u * 2 + 1, imd + 1, r, imd + 1, R);
    }
}

int main()
{
    int n, m, t, x, y;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    creattree(1, 1, n);
    while (m--)
    {
        cin >> t >> x >> y;
        if (t == 1)
        {
            cin >> k;
            for (int i = x; i <= y; i++)
            {
                treewh(1, 1, n, i);
            }
        }
        else
        {
            printf("%d\n", querytree(1, 1, n, x, y));
        }
    }
    return 0;
}

by ljmmmmm @ 2024-10-31 14:11:56

27行改成

if (l == x&& l == r)return;

试试


by ljmmmmm @ 2024-10-31 14:13:29

帮你试了,70分tle,区间修改记得用懒惰标记


by 添哥 @ 2024-10-31 14:14:33

            for (int i = x; i <= y; i++)
            {
                treewh(1, 1, n, i);
            }

@LabmemNo_012LzTopic 做 n 次单点修改认真的?


by 添哥 @ 2024-10-31 14:15:22

去学下懒惰标记吧


by LabmemNo_012LzTopic @ 2024-10-31 20:16:54

@ljmmmmm 感谢!!!Orz


by LabmemNo_012LzTopic @ 2024-10-31 20:18:07

@添哥 好的!!!


|