90分 10 TLE 非输入输出的问题(试过了)求助!

P1253 扶苏的问题

lsc72 @ 2024-05-30 17:06:42

#include<bits/stdc++.h>
using namespace std;
inline long long maxx(long long a,long long b){
    if (a>=b) return a;
    else return b;
}
struct node{long long l,r,n,add=0,ccc=-1e17;};
node tree[5000010];
long long a[1000010];
long long build(int p,int l,int r){
    node temp;temp.l=l;temp.r=r;
    if (l==r) {temp.n=a[l];tree[p]=temp;return tree[p].n;}
    int mid=(l+r)/2;
    temp.n=maxx(build(p*2,l,mid),build(p*2+1,mid+1,r));
    tree[p]=temp;
    return tree[p].n;
}
void update(int s,int p){
    if (s==p) return;
    int mid=(tree[s].l+tree[s].r)/2;
    if (tree[p].l<=mid) update(s*2,p);
    if (tree[p].l>mid) update(s*2+1,p);
    tree[s].n=maxx(tree[s*2].n,tree[s*2+1].n);
}
void change(int s){
    if (tree[s*2].l!=0){
        if (tree[s].ccc!=-1e17) {
            tree[s*2].n=tree[s].ccc;
            tree[s*2].add=0;
            tree[s*2].ccc=tree[s].ccc;
        }
        tree[s*2].n+=tree[s].add;
        tree[s*2].add+=tree[s].add;
    }
    if (tree[s*2+1].l!=0){
        if (tree[s].ccc!=-1e17) {
            tree[s*2+1].n=tree[s].ccc;
            tree[s*2+1].add=0;
            tree[s*2+1].ccc=tree[s].ccc;
        }
        tree[s*2+1].n+=tree[s].add;
        tree[s*2+1].add+=tree[s].add;
    }
    tree[s].add=0; tree[s].ccc=-1e17;
    return;
}
void search(long long m,int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        tree[s].n+=m;
        tree[s].add+=m;
        update(1,s);
        return;
    }
    change(s);
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) search(m,l,min(mid,r),2*s);
    if (r>mid) search(m,max(mid+1,l),r,2*s+1);
    return;
}
void search2(long long m,int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        tree[s].n=m;
        tree[s].add=0;
        tree[s].ccc=m;
        update(1,s);
        return;
    }
    change(s);
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) search2(m,l,min(mid,r),2*s);
    if (r>mid) search2(m,max(mid+1,l),r,2*s+1);
    return;
}
long long find(int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        return tree[s].n;
    }
    change(s);
    long long ans=-1e17;
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) ans=maxx(ans,find(l,min(mid,r),2*s));
    if (r>mid) ans=maxx(ans,find(max(mid+1,l),r,2*s+1));
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) scanf("%ld",&a[i]);
    build(1,1,n);
    while (m--)
    {
        int a,x,y;
        long long k;
        cin>>a;
        if (a==1)
        {
            cin>>x>>y>>k;
            search2(k,x,y,1);
        }
        else if (a==2)
        {
            cin>>x>>y>>k;
            search(k,x,y,1);
        }
        else
        {
            cin>>x>>y;
            printf("%ld\n",find(x,y,1));
        }
    }
    return 0; 
}

by sulingfeng @ 2024-05-30 17:26:12

全改成 scanfprintf 试试


by lsc72 @ 2024-06-01 19:37:15

全改了,还是不行,不知道是哪里优化有问题


by liaoxingrui @ 2024-06-19 16:50:48

@xyszlsc72 改成快读快输即可


by liaoxingrui @ 2024-06-19 16:51:51

#include<bits/stdc++.h>
using namespace std;
inline long long maxx(long long a,long long b){
    if (a>=b) return a;
    else return b;
}
namespace IO{
    const int bif=1<<18;
    char buf[bif],*p1,*p2;
    inline char getc(){
        if(p1==p2){
            p2=(p1=buf)+fread(buf,1,bif,stdin);
            if(p1==p2)
                return EOF;
        }
        return *p1++;
    }
    inline int read(){
        int x=0,f=1;
        char c=getc();
        while(!isdigit(c)){
            if(c=='-')
                f=-1;
            c=getc();
        }
        while(isdigit(c)){
            x=(x<<1)+(x<<3)+(c^48);
            c=getc(); 
        }
        return x*f;
    }
}using namespace IO;
namespace FastIO{
    int p,p3=-1;
    char buf[1<<21],a[20];
    void write(){}
    inline void flush(){
        fwrite(buf,1,p3+1,stdout);
        p3=-1;
    }
    template<typename T,typename... T2>
    inline void write(T x,T2... oth){
        if(p3>1<<20)
            flush();
        if(x<0){
            buf[++p3]=45;
            x=-x;
        }
        do
            a[++p]=x%10+48;
        while(x/=10);
        do
            buf[++p3]=a[p];
        while(--p);
        write(oth...);
    }
}
#define write FastIO::write
#define flush FastIO::flush
struct node{long long l,r,n,add=0,ccc=-1e17;};
node tree[5000010];
long long a[1000010];
long long build(int p,int l,int r){
    node temp;temp.l=l;temp.r=r;
    if (l==r) {temp.n=a[l];tree[p]=temp;return tree[p].n;}
    int mid=(l+r)/2;
    temp.n=maxx(build(p*2,l,mid),build(p*2+1,mid+1,r));
    tree[p]=temp;
    return tree[p].n;
}
void update(int s,int p){
    if (s==p) return;
    int mid=(tree[s].l+tree[s].r)/2;
    if (tree[p].l<=mid) update(s*2,p);
    if (tree[p].l>mid) update(s*2+1,p);
    tree[s].n=maxx(tree[s*2].n,tree[s*2+1].n);
}
void change(int s){
    if (tree[s*2].l!=0){
        if (tree[s].ccc!=-1e17) {
            tree[s*2].n=tree[s].ccc;
            tree[s*2].add=0;
            tree[s*2].ccc=tree[s].ccc;
        }
        tree[s*2].n+=tree[s].add;
        tree[s*2].add+=tree[s].add;
    }
    if (tree[s*2+1].l!=0){
        if (tree[s].ccc!=-1e17) {
            tree[s*2+1].n=tree[s].ccc;
            tree[s*2+1].add=0;
            tree[s*2+1].ccc=tree[s].ccc;
        }
        tree[s*2+1].n+=tree[s].add;
        tree[s*2+1].add+=tree[s].add;
    }
    tree[s].add=0; tree[s].ccc=-1e17;
    return;
}
void search(long long m,int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        tree[s].n+=m;
        tree[s].add+=m;
        update(1,s);
        return;
    }
    change(s);
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) search(m,l,min(mid,r),2*s);
    if (r>mid) search(m,max(mid+1,l),r,2*s+1);
    return;
}
void search2(long long m,int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        tree[s].n=m;
        tree[s].add=0;
        tree[s].ccc=m;
        update(1,s);
        return;
    }
    change(s);
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) search2(m,l,min(mid,r),2*s);
    if (r>mid) search2(m,max(mid+1,l),r,2*s+1);
    return;
}
long long find(int l,int r,int s){
    if (tree[s].l==l&&r==tree[s].r){
        return tree[s].n;
    }
    change(s);
    long long ans=-1e17;
    int mid=(tree[s].l+tree[s].r)/2;
    if (l<=mid) ans=maxx(ans,find(l,min(mid,r),2*s));
    if (r>mid) ans=maxx(ans,find(max(mid+1,l),r,2*s+1));
    return ans;
}
int main()
{
    int n,m;
    n=read();
    m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    while (m--)
    {
        int a,x,y;
        long long k;
        a=read();
        x=read();
        y=read();
        if (a==1)
        {
            k=read();
            search2(k,x,y,1);
        }
        else if (a==2)
        {
            k=read();
            search(k,x,y,1);
        }
        else{
            write(find(x,y,1));
            flush();
            putchar('\n');
        }
    }
    return 0; 
}

by lsc72 @ 2024-06-20 13:10:50

@liaoxingrui 感谢


|