题意：给你一段区间，，然后每个点的初始值都告诉你，现有两种操作，一种是给你一个小区间的左右端点，之后把这个区间内的所有值都开根号，另一种就是区间求值。方法：树状数组维护求和，巧妙开根号。(线段树)解析：这道是某次考试考的题- -。当时也没想到快的开根号方法，暴力开根号好像70分吧。首先要明确一个事情：被开根号的数最大是的第一个不为1的数的编号这样的话就能为我们节省很多的时间了。具体怎么操作呢？用如上的for循环进行开根号，如果当前已开到1以下了，需要把他的fa数组进行更改，即在for循环里填上一句话：后记：这种思想在很多题都有过应用，这种优化的方式也是一种需要牢记的方式。代码：;ll ;ll c[100001] ;ll p[100001] ;ll fa[100001] ;int n ;ll lowbit(ll x){return x & (-x) ;}ll getsum(ll x){ll sum = 0 ;while(x>0){sum += c[x] ;x -= lowbit(x) ;}return sum ;}void updata(int x , ll t){while(x <= n){c[x] += t ;x += lowbit(x) ;}}int find(int x){if(fa[x] == x) return x ;else{fa[x] = find(fa[x]) ;return fa[x] ;}}int main(){scanf(“%d” , &n) ;for(int i = 1 ; i <= n ; i++){scanf(“%d” , &p[i]) ;updata(i , p[i]) ;fa[i] = i ;}fa[n+1] = n+1 ;int q ;scanf(“%d” , &q) ;for(int i = 1 ; i <= q ; i++){int x , l , r;scanf(“%d%d%d” , &x , &l , &r) ;if(x==1){printf(“%lld\n” , getsum(r) – getsum(l-1)) ;}else{for(int i = find(l) ; i<=r ; i = find(i+1)){int t = (int)(sqrt(p[i])) ;updata(i , t – p[i]) ;p[i] = t ;if(p[i] <= 1) fa[i] = find(i+1) ;}}}}
我想一个人旅行，背上简单的行囊，踏上行程，
