妹子刚学OI 50pts求调

u_lcp @ 2024-04-25 19:17:45

#include <bits/stdc++.h>
#define pc putchar(' ')
#define pe putchar('\n')
using namespace std;
template<typename T>void read(T& n)
{
    T f=1,k=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){f=-1;}c=getchar();}
    while(c<='9'&&c>='0'){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
    n=f*k;
}
template<typename T>void write(T x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int maxn=1e6+10;
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
typedef long long ll;
struct sgt
{
    int l,r;
    bool isfill;
    int lzyfill,lzyadd;
    ll mx;
}t[maxn<<2];
ll a[maxn];
int n,q;
void pushup(int rt)
{
    t[rt].mx=max(t[ls].mx,t[rs].mx);
}
void build(int rt,int l,int r)
{
    t[rt].l=l;
    t[rt].r=r;
    t[rt].isfill=false;
    t[rt].lzyadd=0;
    t[rt].lzyfill=0;
    if(l==r)
    {
        t[rt].mx=a[l];
        return;
    }
    build(ls,l    ,mid);
    build(rs,mid+1,r  );
    pushup(rt);
}
void makelzyfill(int rt,ll x)
{
    t[rt].isfill=true;
    t[rt].lzyfill=x;
    t[rt].lzyadd=0;
    t[rt].mx=x;
}
void makelzyadd(int rt,ll x)
{
    t[rt].mx+=x;
    t[rt].lzyadd+=x;
}
void pushdown(int rt)
{
    if(t[rt].isfill)
    {
        makelzyfill(ls,t[rt].lzyfill);
        makelzyfill(rs,t[rt].lzyfill);
        t[rt].isfill=false;
        t[rt].lzyfill=0;
    }
    if(t[rt].lzyadd)
    {
        makelzyadd(ls,t[rt].lzyadd);
        makelzyadd(rs,t[rt].lzyadd);
        t[rt].lzyadd=0;
    }
}
void cover(int rt,int ql,int qr,ll x)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        makelzyfill(rt,x);
        return;
    }
    pushdown(rt);
    if(ql<=mid)cover(ls,ql,qr,x);
    if(qr>mid) cover(rs,ql,qr,x);
    pushup(rt);
}
void update(int rt,int ql,int qr,ll x)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        makelzyadd(rt,x);
        return;
    }
    pushdown(rt);
    if(ql<=mid)update(ls,ql,qr,x);
    if(qr>mid) update(rs,ql,qr,x);
    pushup(rt);    
}
ll query(int rt,int ql,int qr)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        return t[rt].mx;
    }
    pushdown(rt);
    ll ans=-2e9;
    if(ql<=mid)ans=max(ans,query(ls,ql,qr));
    if(qr>mid) ans=max(ans,query(rs,ql,qr));
    return ans;
}
int main()
{
    read(n),read(q);
    for(int i=1;i<=n;i++)read(a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int o,l,r;ll x;
        read(o),read(l),read(r);
        if(o==1)read(x),cover(1,l,r,x);
        else if(o==2)read(x),update(1,l,r,x);
        else write(query(1,l,r)),pe;
    }
    return 0;
}

by scp020 @ 2024-04-25 20:47:00

@u_lcp 我来调教你了

by u_lcp @ 2024-04-25 21:11:54

@scp020 实力

by u_lcp @ 2024-04-25 21:13:32

@u_lcp 破案 pushdown写炸了+标记没开long long

by small_cabbage @ 2024-04-27 14:46:38

@u_lcp 新学OI是吧我的宝，晚上来我家我教你

by u_lcp @ 2024-04-28 13:10:38

@small_cabbage 那还是算了吧，不过...确实刚学OI哦[doge]。

by u_lcp @ 2024-04-28 13:12:47

贴份代码吧

#include <bits/stdc++.h>
#define pc putchar(' ')
#define pe putchar('\n')
using namespace std;
template<typename T>void read(T& n)
{
    T f=1,k=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){f=-1;}c=getchar();}
    while(c<='9'&&c>='0'){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
    n=f*k;
}
template<typename T>void write(T x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int maxn=1e6+10;
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define int long long
typedef long long ll;
struct sgt
{
    int l,r;
    bool isfill;
    int lzyfill,lzyadd;
    ll mx;
}t[maxn<<2];
ll a[maxn];
int n,q;
void pushup(int rt)
{
    t[rt].mx=max(t[ls].mx,t[rs].mx);
}
void build(int rt,int l,int r)
{
    t[rt].l=l;
    t[rt].r=r;
    t[rt].isfill=false;
    t[rt].lzyadd=0;
    t[rt].lzyfill=0;
    if(l==r)
    {
        t[rt].mx=a[l];
        return;
    }
    build(ls,l    ,mid);
    build(rs,mid+1,r  );
    pushup(rt);
}
void makelzyfill(int rt,ll x,ll d)
{
    t[rt].isfill=true;
    t[rt].lzyfill=x;
    t[rt].lzyadd=d;
    t[rt].mx=x+d;
}
void makelzyadd(int rt,ll x)
{
    t[rt].mx+=x;
    t[rt].lzyadd+=x;
}
void pushdown(int rt)
{
    if(t[rt].isfill)
    {
        makelzyfill(ls,t[rt].lzyfill,t[rt].lzyadd);
        makelzyfill(rs,t[rt].lzyfill,t[rt].lzyadd);
        t[rt].isfill=false;
        t[rt].lzyfill=0;
        t[rt].lzyadd=0;
        return;
    }
    makelzyadd(ls,t[rt].lzyadd);
    makelzyadd(rs,t[rt].lzyadd);
    t[rt].lzyadd=0;
}
void cover(int rt,int ql,int qr,ll x)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        makelzyfill(rt,x,0);
        return;
    }
    pushdown(rt);
    if(ql<=mid)cover(ls,ql,qr,x);
    if(qr>mid) cover(rs,ql,qr,x);
    pushup(rt);
}
void update(int rt,int ql,int qr,ll x)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        makelzyadd(rt,x);
        return;
    }
    pushdown(rt);
    if(ql<=mid)update(ls,ql,qr,x);
    if(qr>mid) update(rs,ql,qr,x);
    pushup(rt);    
}
ll query(int rt,int ql,int qr)
{
    int l=t[rt].l,r=t[rt].r;
    if(ql<=l&&r<=qr)
    {
        return t[rt].mx;
    }
    pushdown(rt);
    ll ans=LONG_LONG_MIN;
    if(ql<=mid)ans=max(ans,query(ls,ql,qr));
    if(qr>mid) ans=max(ans,query(rs,ql,qr));
    return ans;
}
signed main()
{
    read(n),read(q);
    for(int i=1;i<=n;i++)read(a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int o,l,r;ll x;
        read(o),read(l),read(r);
        if(o==1)read(x),cover(1,l,r,x);
        else if(o==2)read(x),update(1,l,r,x);
        else write(query(1,l,r)),pe;

    }
    return 0;
}