线段树求助,样例过不了!!!

P1253 扶苏的问题

卷王 @ 2022-08-13 18:41:34

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define maxn 1000001
#define INF 1e10
using namespace std;
typedef long long ll;
ll t1[maxn*4],t2[maxn*4],w[maxn*4],a[maxn]; //t1记录区间赋值为x,t2记录区间要加上x。 
int opt,n,q,l,r,k;
//=======================================================================
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
//=======================================================================
inline void push_up(int u) {w[u]=max(w[u<<1],w[u<<1|1]);}
inline bool in_range(int L,int R,int l,int r) {return (L>=l)&&(R<=r);}
inline bool outof_range(int L,int R,int l,int r) {return (L>r)||(R<l);}
inline void maketag1(int u,ll x) {w[u]=x; t1[u]=x; t2[u]=0;}
inline void build(int u,int L,int R)
{
    if(L==R) { w[u]=a[L]; return ;}
    int mid=(L+R)>>1;
    build(u,L,mid); build(u,mid+1,R);
    push_up(u);
}
inline void maketag2(int u,ll x)
{
    w[u]+=x;
    if(t1[u]!=INF) t1[u]+=x;
    else t2[u]+=x;
}
inline void pushdown(int u)
{
    if(t1[u]!=INF)
    {
        maketag1(u<<1,t1[u]);
        maketag1(u<<1|1,t1[u]);
        t1[u]=INF;
    }
    else if(t2[u]!=0)
    {
        maketag2(u<<1,t2[u]);
        maketag2(u<<1|1,t2[u]);
        t2[u]=0;
    }
}
inline ll query(int u,int L,int R,int l,int r)
{
    if(in_range(L,R,l,r)) return w[u];
    else if(!outof_range(L,R,l,r))
    {
        int mid=(L+R)/2;
        pushdown(u);
        return query(u<<1,L,mid,l,r)+query(u<<1|1,mid+1,R,l,r);
    }
    else return 0;
}
inline void update(int u,int L,int R,int l,int r,int opt,ll x)
{
    if(in_range(L,R,l,r))
    {
        if(opt==1) maketag1(u,x);
        else maketag2(u,x);
    }
    else if(outof_range(L,R,l,r))
    {
        int mid=(L+R)>>1;
        pushdown(u);
        update(u,L,mid,l,r,opt,x);
        update(u,mid+1,R,l,r,opt,x);
        push_up(u);
    }
}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d %d %d",&opt,&l,&r);
        if(opt==1 || opt==2)
        {
            k=read();
            update(1,1,n,l,r,opt,k);
        }
        else printf("%ld\n",query(1,1,n,l,r));
    }
    return 0;
}

程序输出:

0
0
-1

样例输出:

7
6
-1

|