#include#include #include #include #define int long longusing 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也可能大于rQvQ