Luogu P4145 上帝造题的七分钟2 / 花神游历各国

我就是我 2023-06-02 13:59 7阅读 0赞

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #define int long long
    using namespace std;
    
    inline void input(int &x){
        int ans=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            ans=ans*10+c-48;
            c=getchar();
        }
        x=ans*f;
    }
    
    inline void output(int x){
        if(x<0)x=-x,putchar('-');
        if(x>9)output(x/10);
        putchar(x%10+48);
    }
    
    inline void writeln(int x){
        output(x);
        putchar('\n');
    }
    
    int n,m,a[100005],c[400005],maxi[400005];
    
    inline void build(int k,int l,int r){
        if(l==r){
            c[k]=a[l];maxi[k]=c[k];
            return;
        }
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        c[k]=c[k<<1]+c[k<<1|1];
        maxi[k]=max(maxi[k<<1],maxi[k<<1|1]);
    }
    
    inline void fix(int k,int l,int r,int xl,int xr){
        if(maxi[k]<=1)return;   
        if(l==r){
            c[k]=sqrt(c[k]);maxi[k]=c[k];
            return;
        }
        int mid=(l+r)>>1;
        if(xl<=mid)fix(k<<1,l,mid,xl,xr);
        if(xr>=mid+1)fix(k<<1|1,mid+1,r,xl,xr);
        c[k]=c[k<<1]+c[k<<1|1];
        maxi[k]=max(maxi[k<<1],maxi[k<<1|1]);
    }
    
    inline int query(int k,int l,int r,int xl,int xr){  
        if(xl<=l&&r<=xr){
            return c[k];
        }
        int mid=(l+r)>>1,ans=0;
        if(xl<=mid)ans+=query(k<<1,l,mid,xl,xr);
        if(xr>=mid+1)ans+=query(k<<1|1,mid+1,r,xl,xr);
        return ans;
    }
    
    signed main(){
        input(n);
        for(int i=1;i<=n;i++)input(a[i]);
        build(1,1,n);
        input(m);
        for(int i=1;i<=m;i++){
            int opt,x,y;
            input(opt);input(X);input(y);
            if(x>y)swap(x,y);
            if(opt==0){
                fix(1,1,n,x,y);
            }
            else{
                writeln(query(1,1,n,x,y));
            }
        }
    }

AC之路：

1.树改（lazytag）暴（单点）查：30ptsTLE

2.树改（lazytag）树查 WA 后意识到sqrt(x)+sqrt(y)!=sqrt(x+y)

3.参考题解后，暴（单点）改树查：40ptsTLE

4.仔细参考题解后，优化单点改（维护区间最大值maxi\[k\]，若为1就不改了），树查，50pts

5.崩溃放松后发现**即使是在查询时l也可能大于r**QvQ

转载于:https://www.cnblogs.com/Y15BeTa/p/11430098.html