一道比较有趣的线段树题目,因为数字不大,而且采取的开平方的操作,所以每个数字最多被开6次平方,再开方也不会变得更小了因为已经变成1了，
也就是说,当一个区间的最大值是1的时候,我们已经没有必要去更改这些区间,尝试加入这种优化后,是否能ac题目呢,答案是可以的.虽然我并不会计算复杂度,
/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/ #include using namespace std; const int maxn = 1e6+5; const int INF = 1e9+7; typedef long long ll; typedef pair<int,int> pii; #define all(a) (a).begin(), (a).end() #define pb(a) push_back(a) vector<int> G[maxn]; ll tree[maxn],mx[maxn];ll a[maxn]; #define L (idx<<1) #define R (idx<<1|1) #define MID (start+end>>1) void push_up(int idx){ tree[idx] = (tree[L]+tree[R]); mx[idx] = max(mx[L],mx[R]); } void build(int idx,int start,int end){ if(start==end){ tree[idx] = mx[idx] = a[start]; return ; } build(L,start,MID);build(R,MID+1,end); push_up(idx); } void update(int idx,int start,int end,int l,int r){ if(mx[idx]==1||start>r||end<l) return ; if(start==end){ tree[idx] = mx[idx] = (ll)sqrt(tree[idx]); return ; } update(L,start,MID,l,r); update(R,MID+1,end,l,r); push_up(idx); } ll query(int idx,int start,int end,int l,int r){ if(start>r||end<l) return 0; if(start>=l&&end<=r) return tree[idx]; ll ans = 0; ans += query(L,start,MID,l,r) + query(R,MID+1,end,l,r); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); int m;cin>>m; while(m--){ int op,l,r;cin>>op>>l>>r; if(r<l) swap(l,r); if(op==0) update(1,1,n,l,r); else cout<<query(1,1,n,l,r)<<"\n"; } }
