Luogu P4145 하나님 이 문 제 를 푸 신 7 분 2 / 화신 이 각국 을 여행 하 다.

#include
#include
#include
#include
#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'&&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('
');
}

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 도 rQvQ 보다 클 수 있 음