这道题挺有代表性，考点为线段树开方。
题意：
k=0表示给[l,r]中的每个数开平方(下取整)k=1表示询问[l,r]中各个数的和
线段树做法：
手动开方的时候，你会发现1e16的数字，开6次就为1了，当我们思考如何下传tag时，我一开始想的是tag记录开方次数，但是在区间求和的时候不好判断或者说还需要update，但是我们考虑每个结点最多被开方6次，有n个结点，那么我们把所有结点开方到1的时间复杂度为6*n*log(n)，这个时间复杂度是可以接受的，所有点都开方6次之后，无论怎么开方都为1，所以我们完全可以加个剪枝，我们的线段树维护的是区间和，如果tree[p]==r-l+1，即区间内全部被开方为1的话，就不需要开方了，直接return就好了。
我犯的错误：一开始TLE,我就去思考怎么传tag，结果发现自己if(tree[p]==r-l+1)的判断被我写成了if(tree[p]==1)，忘记了tree[p]是维护的区间和。
代码：
#include<bits/stdc++.h> #define R register #define ll long long int using namespace std; const int N=100000+5; ll n,m,a[N],tree[N<<2]; inline void build(R ll l,R ll r,R ll p){ if(l==r){ tree[p]=a[l]; return; } R int mid=(l+r)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); tree[p]=tree[p<<1]+tree[p<<1|1]; } void update(R ll l,R ll r,R ll x,R ll y,R ll p){ if(tree[p]==(r-l+1))return; if(l==r){ tree[p]=sqrt(tree[p]); return; } R ll mid=(l+r)>>1; if(x<=mid)update(l,mid,x,y,p<<1); if(y>mid)update(mid+1,r,x,y,p<<1|1); tree[p]=tree[p<<1]+tree[p<<1|1]; } ll query(R ll l,ll r,ll x,ll y,ll p){ ll tot=0; if(l>=x&&r<=y)return tree[p]; ll mid=(l+r)>>1; if(x<=mid)tot+=query(l,mid,x,y,p<<1); if(y>mid)tot+=query(mid+1,r,x,y,p<<1|1); return tot; } int main(){ scanf("%lld",&n); for(R int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); scanf("%lld",&m); for(R int i=1;i<=m;i++){ R ll k,l,r; scanf("%lld%lld%lld",&k,&l,&r); if(l>r)swap(l,r); if(k==0) update(1,n,l,r,1); else printf("%lld ",query(1,n,l,r,1)); } return 0; }
分块做法：
尚未填坑...