60分线段树求调

P1253 扶苏的问题

dyh061011 @ 2023-10-17 09:33:36

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

#define pl (pos<<1)
#define pr (pos<<1|1)
#define ll long long

const int N=1e6+5;
ll n,q,a[N];

ll read(){
    ll x=0;
    char c;
    c=getchar();
    int f=1;
    while(c!='-'&&c<='0'&&c>='9'){
        c=getchar();
    }
    if(c=='-')f=-1,c=getchar();
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c-'0');
        c=getchar();
    }
    return x*f;
}

struct node{
    ll l,r,tag1,tag2;
    ll ma;
    bool f1;
    //int id1,id2;
}tree[N<<2];

void build(int pos,int l,int r){
    tree[pos].l=l,tree[pos].r=r;
    if(l==r){
        tree[pos].ma=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(pl,l,mid);
    build(pr,mid+1,r);
    tree[pos].ma=max(tree[pl].ma,tree[pr].ma);
}

void pd1(int pos){
    if(!tree[pos].f1)return ;

    tree[pl].ma=tree[pos].tag1;
    tree[pl].tag2=0;
    tree[pl].tag1=tree[pos].tag1;
    tree[pl].f1=1;

    tree[pr].ma=tree[pos].tag1;
    tree[pr].tag2=0;
    tree[pr].tag1=tree[pos].tag1;
    tree[pr].f1=1;

    // tree[pos].tag1=0;
    tree[pos].f1=0;
}

void pd2(int pos){
    if(!tree[pos].tag2)return ;
    tree[pl].ma+=tree[pos].tag2;
    tree[pl].tag2+=tree[pos].tag2;
    tree[pr].ma+=tree[pos].tag2;
    tree[pr].tag2+=tree[pos].tag2;
    tree[pos].tag2=0;
}

void change(int pos,int l,int r,ll x){
    if(tree[pos].l>=l&&tree[pos].r<=r){
        tree[pos].ma=x;
        tree[pos].tag1=x;
        tree[pos].f1=1;
        return ;
    }
    pd2(pos);
    pd1(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid>=l)change(pl,l,r,x);
    if(mid<r)change(pr,l,r,x);
    tree[pos].ma=max(tree[pl].ma,tree[pr].ma);
}

void add(int pos,int l,int r,ll x){
    if(tree[pos].l>=l&&tree[pos].r<=r){
        tree[pos].ma+=x;
        tree[pos].tag2+=x;
        return ;
    }
    pd1(pos);
    pd2(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid>=l)add(pl,l,r,x);
    if(mid<r)add(pr,l,r,x);
    tree[pos].ma=max(tree[pl].ma,tree[pr].ma);
}

ll Max;
void ask(int pos,int l,int r){
    if(tree[pos].l>=l&&tree[pos].r<=r){
        Max=max(Max,tree[pos].ma);
        return ;
    }
    // int ml,mr;
    pd1(pos);
    pd2(pos);

    int mid=(tree[pos].l+tree[pos].r)>>1;
    if(mid<l){
        ask(pr,l,r);
    }else if(mid>=r){
        ask(pl,l,r);
    }else{
        ask(pl,l,r);
        ask(pr,l,r);
    }
}

int main(){
    freopen("P1253_7.in","r",stdin);
    freopen("P1253_7.out","w",stdout);
    n=read();q=read();
    //cin>>n>>q;
    for(int i=1;i<=n;i++)a[i]=read();

    build(1,1,n);

    for(int i=1;i<=q;i++){
        int op=read();
        //cin>>op;
        int l=read(),r=read(),x;
        //int l,r,x;
        //cin>>l>>r;
        if(op==1){
            x=read();
            //cin>>x;
            change(1,l,r,x);
        }else if(op==2){
            x=read();
            //cin>>x;
            add(1,l,r,x);
        }else{
            Max=-9223372036854775807;
            ask(1,l,r);
            cout<<Max<<'\n';
        }
    }

    return 0;
}

不知道为什么加了快读第3个点就过不了了


by Double_Sheep @ 2023-10-28 12:11:10

因为您的快读写错了。

while(c!='-'&&c<='0'&&c>='9')

这行应该改为:

while(c!='-'&&(c<='0'||c>='9'))

by Double_Sheep @ 2023-10-28 12:11:52

@dyh061011


|