数据水建议加强

rt。本题我使用数据分治就 AC 了，建议卡一下珂朵莉树或加强 opt=1 的点

#include<bits/stdc++.h>
#define int long long
using namespace std;

void read(int &x)
{
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            w=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=s*10+ch-'0';
        ch=getchar();
    }
    x=w*s;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x%10+'0');
        return ;
    }
    write(x/10);
    putchar(x%10+'0');
}

const int maxn=1000005;

int n,q;
int Ar[maxn];

namespace ChthollyTree
{
    struct Node{
        int l,r;
        mutable long long val;
        Node(int a=-1,int b=-1,long long c=0)
        {
            l=a,r=b,val=c;
        }
        bool operator<(const Node &a)const{
            return l<a.l;
        }
    };

    set<Node> st;

    set<Node>::iterator split(int pos)
    {
        set<Node>::iterator it=st.lower_bound(Node(pos));
        if (it!=st.end() && it->l==pos)
        {
            return it;
        }
        --it;
        Node tmp=*it;
        st.erase(it);
        st.insert(Node(tmp.l,pos-1,tmp.val));
        return st.insert(Node(pos,tmp.r,tmp.val)).first;
    }

    void assign(int l,int r,long long val)
    {
        set<Node>::iterator itr=split(r+1),itl=split(l);
        st.erase(itl,itr);
        st.insert((Node){l,r,val});
    }

    void add(int l,int r,long long val)
    {
        set<Node>::iterator itr=split(r+1),itl=split(l);
        for(set<Node>::iterator it=itl; it!=itr; ++it)
        {
            it->val+=val;
        }

    }
    long long queryMax(int l,int r)
    {
        set<Node>::iterator itr=split(r+1),itl=split(l);
        long long ans=-0x3f3f3f3f3f;
        for(set<Node>::iterator it=itl;it!=itr;it++)
        {
            ans=max(ans,it->val);
        }
        return ans;
    }
    struct node{
        int l,r,val;
        node(int L,int R,int v)
        {
            l=L,r=R,val=v;
        }
    };
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            int x;
            read(x);
            st.insert((Node){i,i,x});
        }
        int Opttag=0;
        while(q--)
        {
            int opt,l,r;
            read(opt);
            read(l);
            read(r);
            if(opt==1)
            {
                int x;
                read(x);
                assign(l,r,x);
            }else if(opt==2){
                int x;
                read(x);
                add(l,r,x);
            }else{
                printf("%lld\n",queryMax(l,r));
            }
        }
    }
}

signed main()
{
    read(n),read(q);
    if(n>100000 && q>100000)
    {
        ChthollyTree::solve();
        return 0;
    }
    for(register int i=1;i<=n;i++)
    {
        read(Ar[i]);
    }
    while(q--)
    {
        int opt,l,r,w;
        read(opt),read(l),read(r);
        if(opt==1)
        {
            read(w);
            for(register int i=l;i<=r;++i)
            {
                Ar[i]=w;
            }

        }else if(opt==2){
            read(w);
            for(register int i=l;i<=r;++i)
            {
                Ar[i]+=w;
            }
        }else{
            int ans=-1e18;
            for(register int i=l;i<=r;++i)
            {
                ans=max(ans,Ar[i]);
            }
            write(ans);
            putchar('\n');
        }
    }
    return 0;
}