10 TLE

P1253 扶苏的问题

Story_of_CT @ 2024-03-02 11:17:47

请问线段树有什么误区会导致常数大幅增加吗?
10 2.19s结束
代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long  dat;
dat input[2000005];
int n,q;
struct node{
    node*lchild,*rchild;
    int lnum,rnum;
    bool isseet,isadd;
    dat num;
    dat maxunder;

    node(int l,int r){
        lnum=l;rnum=r;isseet=isadd=false;
        if(l==r)
            {maxunder=num=input[l];lchild=rchild=NULL;isseet=true;return;}
        int t=(l+r-1)/2;

        if(l>n)return;

        lchild=new node(l,t);rchild=new node(t+1,r);
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    void sink(){
        //system("pause");
        if((!(isseet||isadd))||lnum==rnum)return;
        if(isseet){
            isseet=false;
            node*t=lchild;
            t->isadd=false;t->isseet=true;t->num=t->maxunder=num;
            t=rchild;
            t->isadd=false;t->isseet=true;t->num=t->maxunder=num;
            return;
            }
        if(isadd){
            isadd=false;
            node*t=lchild;
            if(!(t->isseet||t->isadd)){t->isadd=true;t->num=0;}
            t->num+=num;t->maxunder+=num;
            t=rchild;
            if(!(t->isseet||t->isadd)){t->isadd=true;t->num=0;}
            t->num+=num;t->maxunder+=num;
            return;
        }
    }

    void seet(int l,int r,dat x){
        if(l==lnum&&r==rnum){
            isseet=true;isadd=false;num=maxunder=x;return;
        }
        sink();
        int t=(lnum+rnum-1)/2;
        if(l<=t)lchild->seet(l,min(t,r),x);
        if(r>=t+1)rchild->seet(max(t+1,l),r,x);
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    void add(int l,int r,dat x){
        if(l==lnum&&r==rnum){
            if(!(isseet||isadd)){isadd=true;num=0;}
            num+=x;maxunder+=x;return;
        }
        sink();
        int t=(lnum+rnum-1)/2;
        if(l<=t)lchild->add(l,min(t,r),x);
        if(r>=t+1)rchild->add(max(t+1,l),r,x);
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    dat search(int l,int r){
        if(l==lnum&&r==rnum)return maxunder;
        sink();
        int t=(lnum+rnum-1)/2;
        dat ans;
        if(l<=t)ans=lchild->search(l,min(t,r));
        if(r>=t+1){
            if(l>t)ans=rchild->search(max(t+1,l),r);
            else ans=max(ans,rchild->search(max(t+1,l),r));
        }
        return ans; 
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>input[i];
    int l,r,x=1;
    for(x=1;x<n;x*=2);
    node tree(1,x);

    for(int i=1;i<=q;i++){
        int op;cin>>op;
        if(op==1){cin>>l>>r>>x;tree.seet(l,r,x);continue;}
        if(op==2){cin>>l>>r>>x;tree.add(l,r,x);continue;}
        if(op==3){cin>>l>>r;cout<<tree.search(l,r)<<endl;continue;}
    }
}

by Story_of_CT @ 2024-03-03 13:53:33

AC 修改内容主要是搜索时可以不下沉标记 代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long dat;
dat input[2000005];
int n,q;
struct node{
    node*lchild,*rchild;
    int lnum,rnum;
    bool isadd;
    dat num;
    dat maxunder;

    node(int l,int r){
        lnum=l;rnum=r;isadd=true;num=0;
        if(l==r)
            {maxunder=num=input[l];lchild=rchild=NULL;isadd=false;return;}
        int t=(l+r-1)/2;

        if(l>n)return;

        lchild=new node(l,t);rchild=new node(t+1,r);
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    void sink(){
        //system("pause");
        if((isadd&&num==0)||lnum==rnum)return;
        if(!isadd){
            isadd=true;
            node*t=lchild;
            t->isadd=false;t->num=t->maxunder=num;
            t=rchild;
            t->isadd=false;t->num=t->maxunder=num;
            num=0;
            return;
            }
        if(isadd){
            node*t=lchild;
            t->num+=num;t->maxunder+=num;
            t=rchild;
            t->num+=num;t->maxunder+=num;
            num=0;
            return;
        }
    }

    void seet(int l,int r,dat x){
        if(l==lnum&&r==rnum){isadd=false;num=maxunder=x;return;}
        sink();
        int t=(lnum+rnum-1)/2;
        //cout<<1<<endl;system("pause");
        if(l<=t)lchild->seet(l,min(t,r),x);
        //cout<<2<<endl;system("pause");
        if(r>=t+1)rchild->seet(max(t+1,l),r,x);
        //cout<<3<<endl;system("pause");
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    void add(int l,int r,dat x){
        if(l==lnum&&r==rnum){num+=x;maxunder+=x;return;}
        sink();
        int t=(lnum+rnum-1)/2;
        if(l<=t)lchild->add(l,min(t,r),x);
        if(r>=t+1)rchild->add(max(t+1,l),r,x);
        maxunder=max(lchild->maxunder,rchild->maxunder);
    }

    dat search(int l,int r){
        if((l==lnum&&r==rnum)||!isadd)return maxunder;
        int t=(lnum+rnum-1)/2;
        dat ans;
        if(l<=t)ans=lchild->search(l,min(t,r));
        if(r>=t+1){
            if(l>t)ans=rchild->search(max(t+1,l),r);
            else ans=max(ans,rchild->search(max(t+1,l),r));
        }
        return ans+num; 
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>input[i];
    int l,r,x=1;
    for(x=1;x<n;x*=2);
    node tree(1,x);

    for(int i=1;i<=q;i++){
        int op;cin>>op;
        if(op==1){cin>>l>>r>>x;tree.seet(l,r,x);continue;}
        if(op==2){cin>>l>>r>>x;tree.add(l,r,x);continue;}
        if(op==3){cin>>l>>r;cout<<tree.search(l,r)<<endl;continue;}
    }
}

by Bamboo2022 @ 2024-04-10 15:58:18

同问


|