线段树60求调,悬赏关注!!!!!!!!!!!!!!!!!!!!!!!!

P1253 扶苏的问题

_Coffice_ @ 2023-04-30 07:33:22

#include<iostream>
using namespace std;
struct Tree
{
    long long l,r;
    long long d;
    long long tag1, // 区间赋值
        tag2; // 区间加
    bool flag1,flag2;
};
Tree t[4000005];
long long a[1000005];
long long lc(long long p)
{
    return p*2;
}
long long rc(long long p)
{
    return p*2+1;
}
long long mid(long long l,long long r)
{
    return (l+r)/2;
}
void js(long long p,long long l,long long r)
{
    t[p].l = l;
    t[p].r = r;
    t[p].tag1 = 0;
    t[p].tag2 = 0;
    t[p].flag1 = 0;
    t[p].flag2 = 0;
    if(l == r)
    {
        t[p].d = a[l];
        return ;
    }
    long long m = mid(l,r);
    js(lc(p),l,m);
    js(rc(p),m+1,r);
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
void f1(long long p,long long t1)
{
    t[p].tag1 = t1;
    t[p].flag1 = 1;
    t[p].d = t1;
    return ;
}
void f2(long long p,long long t2)
{
    t[p].tag2 += t2;
    t[p].flag2 = 1;
    t[p].d += t2;
    return ;
}
void down(long long p)
{
    if(t[p].flag1 != 0)
    {
        f1(lc(p),t[p].tag1);
        f1(rc(p),t[p].tag1);
        t[p].flag1 = 0;
        t[p].tag1 = 0;
    }
    if(t[p].flag2 != 0)
    {
        f2(lc(p),t[p].tag2);
        f2(rc(p),t[p].tag2);
        t[p].flag2 = 0;
        t[p].tag2 = 0;
    }
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
void upd(long long p,long long l,long long r,long long x) // 区间赋值
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].d = x;
        t[p].tag1 = x;
        t[p].flag1 = 1;
        return ;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    if(l <= m)
    {
        upd(lc(p),l,r,x);
    }
    if(r >= m+1)
    {
        upd(rc(p),l,r,x);
    }
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
void add(long long p,long long l,long long r,long long x) // 区间加
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].d += x;
        t[p].flag2 = 1;
        t[p].tag2 += x;
        return ;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    if(l <= m)
    {
        add(lc(p),l,r,x);
    }
    if(r >= m+1)
    {
        add(rc(p),l,r,x);
    }
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
long long max_(long long p,long long l,long long r) // 区间最值
{
    if(l <= t[p].l && r >= t[p].r)
    {
        return t[p].d;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    long long ans = -1000000000002;
    if(l <= m)
    {
        ans = max(ans,max_(lc(p),l,r));
    }
    if(r >= m+1)
    {
        ans = max(ans,max_(rc(p),l,r));
    }
    return ans;
}
int main()
{
    long long n,q;
    scanf("%lld%lld",&n,&q);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    js(1,1,n);
    for(long long i=1;i<=q;i++)
    {
        long long op;
        scanf("%lld",&op);
        if(op == 1)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            upd(1,l,r,x);
        }
        else if(op == 2)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            add(1,l,r,x);
        }
        else
        {
            long long l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",max_(1,l,r));
        }
    }
    return 0;
}

WA 6-10

by liqingyang @ 2023-04-30 10:02:04

@czw20110831 down 里的区间赋值应该得把区间加的 tag 给干掉？

by liqingyang @ 2023-04-30 10:04:06

建议仔细想想赋值和加的顺序与关系

by _Coffice_ @ 2023-04-30 10:34:02

@liqingyang

已关

by _Coffice_ @ 2023-04-30 10:39:45

改了，还是60 emmm----

#include<iostream>
using namespace std;
struct Tree
{
    long long l,r;
    long long d;
    long long tag1, // 区间赋值
        tag2; // 区间加
    bool flag1,flag2;
};
Tree t[4000005];
long long a[1000005];
long long lc(long long p)
{
    return p*2;
}
long long rc(long long p)
{
    return p*2+1;
}
long long mid(long long l,long long r)
{
    return (l+r)/2;
}
void js(long long p,long long l,long long r)
{
    t[p].l = l;
    t[p].r = r;
    t[p].tag1 = 0;
    t[p].tag2 = 0;
    t[p].flag1 = 0;
    t[p].flag2 = 0;
    if(l == r)
    {
        t[p].d = a[l];
        return ;
    }
    long long m = mid(l,r);
    js(lc(p),l,m);
    js(rc(p),m+1,r);
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
void f2(long long p,long long t2)
{
    t[p].tag2 += t2;
    t[p].flag2 = 1;
    t[p].d += t2;
    return ;
}
void f1(long long p,long long t1)
{
    t[p].tag1 = t1;
    t[p].flag1 = 1;
    t[p].d = t1;
    return ;
}
void down(long long p)
{
    if(t[p].flag2 != 0)
    {
        f2(lc(p),t[p].tag2);
        f2(rc(p),t[p].tag2);
        t[p].flag2 = 0;
        t[p].tag2 = 0;
    }
    if(t[p].flag1 != 0)
    {
        f1(lc(p),t[p].tag1);
        f1(rc(p),t[p].tag1);
        t[p].flag1 = 0;
        t[p].tag1 = 0;
    }
    return ;
}
void upd(long long p,long long l,long long r,long long x) // 区间赋值
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].d = x;
        t[p].tag1 = x;
        t[p].flag1 = 1;
        return ;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    if(l <= m)
    {
        upd(lc(p),l,r,x);
    }
    if(r >= m+1)
    {
        upd(rc(p),l,r,x);
    }
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
void add(long long p,long long l,long long r,long long x) // 区间加
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].d += x;
        t[p].flag2 = 1;
        t[p].tag2 += x;
        return ;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    if(l <= m)
    {
        add(lc(p),l,r,x);
    }
    if(r >= m+1)
    {
        add(rc(p),l,r,x);
    }
    t[p].d = max(t[lc(p)].d,t[rc(p)].d);
    return ;
}
long long max_(long long p,long long l,long long r) // 区间最值
{
    if(l <= t[p].l && r >= t[p].r)
    {
        return t[p].d;
    }
    down(p);
    long long m = mid(t[p].l,t[p].r);
    long long ans = -1000000000002;
    if(l <= m)
    {
        ans = max(ans,max_(lc(p),l,r));
    }
    if(r >= m+1)
    {
        ans = max(ans,max_(rc(p),l,r));
    }
    return ans;
}
int main()
{
    long long n,q;
    scanf("%lld%lld",&n,&q);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    js(1,1,n);
    for(long long i=1;i<=q;i++)
    {
        long long op;
        scanf("%lld",&op);
        if(op == 1)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            upd(1,l,r,x);
        }
        else if(op == 2)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            add(1,l,r,x);
        }
        else
        {
            long long l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",max_(1,l,r));
        }
    }
    return 0;
}

by _Coffice_ @ 2023-04-30 10:41:14

@liqingyang

by liqingyang @ 2023-04-30 10:55:27

@czw20110831 稍微仔细自己查查吧， upd 里的区间加还是没改啊

by _Coffice_ @ 2023-04-30 10:57:08

好的，谢谢！

by _Coffice_ @ 2023-04-30 11:06:04

@liqingyang

我太弱了，还没理解，您能详细帮我讲解下吗？？

万分感谢！！

%%%

by _Coffice_ @ 2023-04-30 11:12:19

带钩dalao带带小弟嘛~~~~

@liqingyang

by liqingyang @ 2023-04-30 12:39:34

？看不懂的话建议重学一下这题，理解一下 tag 与如何下传

上一页 | 下一页