题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027
解题思路：
一个数组维护区间和。
另一个维护区间是否都小于等于1，如果全是小于等于1就不用往下修改了。
因为一个很大的数（2^63）开根号开不了几次就会等于1，所以就是这么暴力。
注意每组测试数据后面一个换行。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r #define ll long long #define mid int m=l+r>>1 #define al allone[rt<<1] #define ar allone[rt<<1|1] #define tl tree[rt<<1] #define tr tree[rt<<1|1] #define INF 0x3f3f3f3f using namespace std; const int N = 1e5+5; ll tree[N<<2]; bool allone[N<<2]; void push_up(int rt) { allone[rt] = al && ar; tree[rt] = tl + tr; } void update(int L,int R,int rt,int l,int r) { if (allone[rt]){ return ; } if (l==r){ tree[rt] = (ll)(sqrt(tree[rt])); if (tree[rt]<=1) allone[rt] = true; return ; } mid; if (L<=m) update(L,R,lson); if (R>m) update(L,R,rson); push_up(rt); } ll query(int L,int R,int rt,int l,int r) { if (L<=l && r<=R){ return tree[rt]; } ll ans = 0; mid; if (L<=m) ans += query(L,R,lson); if (R>m) ans += query(L,R,rson); return ans; } void build(int rt,int l,int r) { if (l==r){ scanf("%lld",&tree[rt]); if (tree[rt]<=1) allone[rt] = true; return ; } mid; build(lson); build(rson); push_up(rt); } int main() { int n,q; for (int kca=1;~scanf("%d",&n);kca++){ printf("Case #%d:\n",kca); memset(allone,false,sizeof allone); build(1,1,n); scanf("%d",&q); while (q--){ int op,l,r; scanf("%d %d %d",&op,&l,&r); if (l>r) swap(l,r); if (op==0) update(l,r,1,1,n); else printf("%lld\n",query(l,r,1,1,n)); } printf("\n"); } return 0; }
