50pts求改,谢谢!

P1253 扶苏的问题

U_92_Uranium @ 2022-11-15 15:03:03

RT

//P1253 [yLOI2018] 扶苏的问题
//fusu
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <cstdlib>
#include <utility>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <list>
#include <set>
using namespace std;using ll=long long;
const int maxn=1e6;
const ll INF=0x3f3f3f3f3f3f3f3fll;//4557430888798830399 4e18, 

int n,q;
ll st[4*maxn+100],a[maxn+100],lz[4*maxn+100],lzt[4*maxn+100];//lz是加法标记;lzt是turn into 标记 

inline ll Rd() {
    ll res=0,f=1;
    char c=getchar();

    while(!isdigit(c)) {
        if(c=='-') {
            f=-1;
        }
        c=getchar();
    }

    while(isdigit(c)) {
        res=(res<<1)+(res<<3)+(c^48);
        c=getchar();
    }
    return res*f;
}
void Pshup(int k) {
    st[k]=max(st[k<<1],st[k<<1|1]);
}
void Bd(int l,int r,int k) {
    if(l==r) {
        st[k]=a[l];
        return ;
    }
    int  mid=l+(r-l>>1);
    Bd(l,mid,k<<1);
    Bd(mid+1,r,k<<1|1);
    Pshup(k);
}
void chge(int k,int v,int op)
{
    if(op==2)//操作2 :add
    {
        lz[k]+=v;
        st[k]+=v;
        return ;
    } 
    lzt[k]=v;
    st[k]=v;
}
int Pshd(int l,int r,int k)
{
    int res=l+(r-l>>1);
    if(lzt[k]!=INF) {//都改成lzt[k]; 
        chge(k<<1,lzt[k],1);
        chge(k<<1|1,lzt[k],1);
        lzt[k]=INF; 
    }
    if(lz[k]) {
        chge(k<<1,lz[k],2);
        chge(k<<1|1,lz[k],2);
        lz[k]=0;
    } 
    return res;
}
void Upd(int l,int r,int k,int x,int y,int v,int op)
{
    if(x<=l&&r<=y) {
        if(op==2) {
            if(lzt[k]!=INF) {
                lzt[k]+=v;
            } else {
                chge(k,v,2);
            }
        } else {//修改操作 
            chge(k,v,1);
            if(lz[k]) lz[k]=0;//清空add标记,因为都改成了v 
        }
        return;
    }
    int mid=Pshd(l,r,k);
    if(x<=mid) {
        Upd(l,mid,k<<1,x,y,v,op);
    }
    if(y>mid) {
        Upd(mid+1,r,k<<1|1,x,y,v,op); 
    }
    Pshup(k);
} 
ll Fd(int l,int r,int k,int x,int y)
{
    ll res=-INF;
    if(x<=l&&r<=y) {
        return st[k];
    }
    int mid=Pshd(l,r,k);
    if(x<=mid) {
        res=max(res,Fd(l,mid,k<<1,x,y));
    } 
    if(y>mid) {
        res=max(res,Fd(mid+1,r,k<<1|1,x,y));
    }
    return res;
} 

int main() {
//  freopen("fusu.in","r",stdin);
//  freopen("fusu.out","w",stdout);
//  printf("%lld",INF);
    for(int i=1; i<4*maxn+100; ++i) lzt[i]=INF; //可能要都修改为0;所以把lzt=INF代表是没有修改; 
    n=Rd();
    q=Rd();
    for(int i=1; i<=n; ++i) {
        a[i]=Rd();
    }
    Bd(1,n,1);

    for(int lp=1; lp<=q; ++lp) {
        int op=Rd(),l=Rd(),r=Rd(),x;
        switch(op) {
            case 1:
                x=Rd();
                Upd(1,n,1,l,r,x,op);
                break;
            case 2:
                x=Rd();
                Upd(1,n,1,l,r,x,op);
                break;
            case 3:
                printf("%lld\n",Fd(1,n,1,l,r));
                break;
        }
    }
    return 0;
}

|