线段树,求救
查看原帖
线段树,求救
1134636
FRZ_29楼主2024/5/27 22:16

关于本题我认为只有线段树数组和读入数组需要开long long
但是读入N,M不开long long会WA掉
为什么?求各位dalao解答
我的代码如下

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int MAXN = 1e5 + 5;

struct node
{
    ll mx, sum;
} tr[MAXN << 2];

int N, M, times;
ll a[MAXN];

void up(int rt)
{
    tr[rt].sum = tr[ls].sum + tr[rs].sum;
    tr[rt].mx = max(tr[ls].mx, tr[rs].mx);
}

void build(int rt, int l, int r)
{
    if (l == r)
    {
        tr[rt].mx = tr[rt].sum = a[l];
        return;
    }

    build(ls, l, mid), build(rs, mid + 1, r);
    
    up(rt);
}

void update(int rt, int l, int r, int L, int R)
{
    if (tr[rt].mx <= 1)
        return;
    
    if (l == r)
    {
        tr[rt].mx = sqrt(tr[rt].mx);
        tr[rt].sum = sqrt(tr[rt].sum);
        return;
    }

    if (mid >= L)
        update(ls, l, mid, L, R);
    if (mid < R)
        update(rs, mid + 1, r, L, R);
    
    up(rt);
}

ll query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return tr[rt].sum;
    
    ll ans = 0;
    if (mid >= L)
        ans += query(ls, l, mid, L, R);
    if (mid < R)
        ans += query(rs, mid + 1, r, L, R);
    return ans;
}

int main()
{
    while(scanf("%d", &N) != EOF)
    {
        memset(tr, 0, sizeof(tr));
        memset(a, 0, sizeof(a));
    
        ++times;
        printf("Case #%d:\n", times);
    
        for (int i = 1; i <= N; i++)
            scanf("%d", &a[i]);
    
        build(1, 1, N);
    
        scanf("%d", &M);
    
        for (int i = 1, op, x, y; i <= M; i++)
        {
            scanf("%d%d%d", &op, &x, &y);
    
            if (x > y)
                swap(x, y);
    
            switch (op)
            {
            case 0:
                update(1, 1, N, x, y);
                break;
    
            case 1:
                printf("%lld\n", query(1, 1, N, x, y));
                break;
            }
        }
    }
    return 0;
}
2024/5/27 22:16
加载中...