萌新线段树20tps求调

FIRESTARS @ 2024-08-19 20:46:57

#include<bits/stdc++.h>
using namespace std;
int a[1000005],t[4000005],b[40000005],b2[40000005];
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        t[v]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    t[v]=max(t[v*2],t[v*2+1]);
}
int getmax(int v,int tl,int tr,int l,int r)
{
    if(tl>=l&&tr<=r)return t[v];
    int tm=(tl+tr)/2;
    int s1=0,s2=0;
    if(tm>=l)s1=getmax(v*2,tl,tm,l,r);
    if(tm<r)s2=getmax(v*2+1,tm+1,tr,l,r);
    return max(s1,s2);
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
    if(l<=tl&&tr<=r)
    {
        t[v]=x;b[v]=1;
        return;
    }
    if(b[v]!=0)
    {
        t[v*2]=t[v];
        t[v*2+1]=t[v];
        b[v*2]=t[v];
        b[v*2+1]=t[v];
        b[v]=0;
    }
    int tm=(tl+tr)/2;
    if(tm>=l)updata(v*2,tl,tm,l,r,x);
    if(tm<r)updata(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
void updata2(int v,int tl,int tr,int l,int r,int x)
{
    if(l<=tl&&tr<=r)
    {
        t[v]+=x;b2[v]+=x;
        return;
    }
    int tm=(tl+tr)/2;
    if(b2[v]!=0)
    {
        t[v*2]+=b2[v]*(tm-tl+1);
        t[v*2+1]+=b2[v]*(tr-tm);
        b2[v*2]+=b2[v];
        b2[v*2+1]+=b2[v];
        b2[v]=0;
    }
    if(tm>=l)updata2(v*2,tl,tm,l,r,x);
    if(tm<r)updata2(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        int opt,l,r,x;
        cin>>opt;
        if(opt==1)
        {
            cin>>l>>r>>x;
            updata(1,1,n,l,r,x);
        }
        else if(opt==2)
        {
            cin>>l>>r>>x;
            a[l]=r;
            updata2(1,1,n,l,r,x);
        }
        else if(opt==3)
        {
            cin>>l>>r;
            cout<<getmax(1,1,n,l,r)<<'\n';
        }
    }
}

by woshiyida @ 2024-08-19 20:55:30

@FIRESTARS 哦，错了……

by FIRESTARS @ 2024-08-19 20:56:26

@General0826 我们遇到了困难，我们要找gengen队！

by FIRESTARS @ 2024-08-19 20:58:04

@General0826 gengen队，求助！

by Finner_forgeter @ 2024-08-19 20:58:15

@FIRESTARS wjr逆天

by FIRESTARS @ 2024-08-19 21:00:03

找到错误了（

by _joker_r @ 2024-08-19 21:01:41

@FIRESTARS 我当初也是20ptshttps://www.luogu.com.cn/discuss/895589 https://www.luogu.com.cn/discuss/897479

by FIRESTARS @ 2024-08-19 21:04:24

还是没A（

by FIRESTARS @ 2024-08-19 21:04:43

@Finner_forgeter 别™爆我真名

by FIRESTARS @ 2024-08-19 21:06:48

现在代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000005],t[4000005],b[40000005],b2[40000005];
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        t[v]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    t[v]=max(t[v*2],t[v*2+1]);
}
int getmax(int v,int tl,int tr,int l,int r)
{
    if(tl>=l&&tr<=r)return t[v];
    int tm=(tl+tr)/2;
    int s1=0,s2=0;
    if(tm>=l)s1=getmax(v*2,tl,tm,l,r);
    if(tm<r)s2=getmax(v*2+1,tm+1,tr,l,r);
    return max(s1,s2);
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
    if(l<=tl&&tr<=r)
    {
        t[v]=x;b[v]=1;
        return;
    }
    if(b[v]!=0)
    {
        t[v*2]=t[v];
        t[v*2+1]=t[v];
        b[v*2]=t[v];
        b[v*2+1]=t[v];
        b[v]=0;
    }
    int tm=(tl+tr)/2;
    if(tm>=l)updata(v*2,tl,tm,l,r,x);
    if(tm<r)updata(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
void updata2(int v,int tl,int tr,int l,int r,int x)
{
    if(l<=tl&&tr<=r)
    {
        t[v]+=x;b2[v]+=x;
        return;
    }
    int tm=(tl+tr)/2;
    if(b[v]!=0)
    {
        t[v*2]=t[v];
        t[v*2+1]=t[v];
        b[v*2]=t[v];
        b[v*2+1]=t[v];
        b[v]=0;
    }
    if(b2[v]!=0)
    {
        t[v*2]+=b2[v]*(tm-tl+1);
        t[v*2+1]+=b2[v]*(tr-tm);
        b2[v*2]+=b2[v];
        b2[v*2+1]+=b2[v];
        b2[v]=0;
    }
    if(tm>=l)updata2(v*2,tl,tm,l,r,x);
    if(tm<r)updata2(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        int opt,l,r,x;
        cin>>opt;
        if(opt==1)
        {
            cin>>l>>r>>x;
            updata(1,1,n,l,r,x);
        }
        else if(opt==2)
        {
            cin>>l>>r>>x;
            a[l]=r;
            updata2(1,1,n,l,r,x);
        }
        else if(opt==3)
        {
            cin>>l>>r;
            cout<<getmax(1,1,n,l,r)<<'\n';
        }
    }
}

by Finner_forgeter @ 2024-08-20 06:48:34

@FIRESTARS 我错了