题目链接： H - Can you answer these queries? HDU - 4027
给你N个数A[i]，给你M个操作，每次操作一个区间 [l,r] [ l , r ] ，有两种操作。
将区间内的数都变成自己的根号，取整求区间 [l,r] [ l , r ] 的和数据范围： N,M<105 N , M < 10 5
这题直接看的话非常会觉得非常复杂，因为这里的操作无法区间一起进行，每个数进行开根号都只能单个进行。但是有个规律，就在long long int 的范围里面数字最多只会开到7次，所以根据这个性质，我们就可以优化了。
记录每个点修改的次数，利用add延迟标记，在查询的时候修改。更新复杂度 O(logn) O ( l o g n ) ，查询复杂度 O(nlogn) O ( n l o g n ) ，但是在修改时记录每个点所修改的次数，如果次数大于7就修改为7，这样的复杂度其实毫无疑问就会T的。
方案一会T的原因就是如果有多次查询那么我们就会复杂度非常高。我们从另一个角度来考虑，就更新复杂度 O(nlogn) O ( n l o g n ) 查询复杂度 O(logn) O ( l o g n ) 虽然表面上看是一样的，但是因为每个点所修改最多只用7次，所以最多修改7*N次，最多修改所需要 7∗O(logn) 7 ∗ O ( l o g n ) ，这里非常有意思，我看大神的代码学会一种线段树的新型写法，就是分层写线段树，这里给出的代码二就这样，一般的线段树所用的是只用一个递归函数，而我这里需要两种递归，就是在一开始时有一个查找区间 [L,R] [ L , R ] 的Update，然后找到这个区间后使用Update2，将这个区间里面的值都修改为根号，并且将这个区间（包括所有的子区间）的标记add加上一。
这是一种属于这道题的专门的优化方案，就是如果一段区间无法在修改时，每个值一定都是一所以，在修改时，如果发现这个区间的sum是等于r-l+1的，那么就直接return这个区间的值即可。
优化方案二
#include <bits/stdc++.h> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define mmm(a,b) memset(a,b,sizeof(a)) #define debug(x) cerr<<#x<<":"<<x<<endl #define pb push_back typedef double db; typedef long long ll; const int MAXN = (int)1e5+7; const int INF = (int)0x3f3f3f3f; #define rson rt<<1|1 #define lson rt<<1 ll A[MAXN]; int N,M; struct SetTree{ ll sum; int add; }tree[MAXN<<2]; void Build(int l,int r,int rt){ if (l == r){ tree[rt].sum = A[l]; tree[rt].add = 0; return; } int m = l+r>>1; Build(l,m,lson); Build(m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } void PushDown(int rt){ if (tree[rt].add){ tree[lson].add = tree[rson].add = tree[rt].add; } } void Updates(int l,int r,int rt){ tree[rt].add ++; if (l == r) { tree[rt].sum = (ll)sqrt(tree[rt].sum); return; } int m = l+r>>1; Updates(l,m,lson); Updates(m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } void Update(int L,int R,int l,int r,int rt){ if (L <= l && r <= R) { if (tree[rt].add <= 7) Updates(l,r,rt);//tree[rt].add ++; return; } int m = l+r>>1; if (L <= m) Update(L,R,l,m,lson); if (R > m) Update(L,R,m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } ll Query(int L,int R,int l,int r,int rt){ if (L <= l && r <= R){ return tree[rt].sum; } int m = l+r>>1; ll res = 0; if (L <= m)res += Query(L,R,l,m,lson); if (R > m)res += Query(L,R,m+1,r,rson); return res; } int main() { int ca = 0; while (~scanf("%d",&N)){ printf("Case #%d:\n",++ca); rep(i,1,N) scanf("%lld",&A[i]); mmm(tree,0); Build(1,N,1); scanf("%d",&M); rep(i,1,M) { int op,l,r; scanf("%d %d %d",&op,&l,&r); if (l > r) swap(l,r); if (op){ printf("%lld\n",Query(l,r,1,N,1)); }else { Update(l,r,1,N,1); } } printf("\n"); } }