hdu4027（线段树）

/* translation: 给出一列数列，有两种操作，一种是将数列的连续一部分的值变为原来的平方根。 另外一种是查询连续一段的和。 solution: 线段树即可 note: #: 一开始纠结怎么更新节点上的和，因为是将每一个值都变为原来的平方根，所以不可能在常数时间内更新完连续的 一段和。想了好久没有头绪，看了题解才知道关键是发现一个很重要的隐藏条件：只要一段连续区间的和等于r-l+1 那么这段区间就不需要再开平方根了。因为这时候这个区间每一个元素都是1,再开平方根已经没有意义了。如果是递归更新 到叶子节点上面，就更好办了，直接开平方根就好了。然后在通过push_up操作更新到其所有父节点的值。 date: 2016.11.19 */ #include <iostream> #include <cstdio> #include <cmath> using namespace std; const int maxn = 100000 + 5; typedef long long ll; int n, q; int s[maxn*4], e[maxn*4]; ll sum[maxn*4]; inline void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void build(int l, int r, int rt) { s[rt] = l; e[rt] = r; sum[rt] = 0; if(l == r){ scanf("%lld", &sum[rt]); return; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m+1, r, rt << 1 | 1); push_up(rt); } void update(int l, int r, int rt) { if(s[rt] == e[rt]){ sum[rt] = sqrt((double)sum[rt]); return; } if(s[rt] == l && e[rt] == r && sum[rt] == r-l+1) return; int m = (s[rt] + e[rt]) >> 1; if(r <= m) update(l, r, rt << 1); else if(l > m) update(l, r, rt << 1 | 1); else{ update(l, m, rt << 1); update(m+1, r, rt << 1 | 1); } push_up(rt); } ll query(int l, int r, int rt) { if(s[rt] == l && e[rt] == r) return sum[rt]; ll res = 0; int m = (s[rt] + e[rt]) >> 1; if(r <= m) res += query(l, r, rt << 1); else if(l > m) res += query(l, r, rt << 1 | 1); else{ res += query(l, m, rt << 1); res += query(m+1, r, rt << 1 | 1); } return res; } int main() { //freopen("in.txt", "r", stdin); int kase = 0; while(~scanf("%d", &n)){ build(1, n, 1); scanf("%d", &q); printf("Case #%d:\n", ++kase); int op, x, y; while(q--){ scanf("%d%d%d", &op, &x, &y); if(y < x) swap(x, y); if(op == 0){ update(x, y, 1); }else if(op == 1){ printf("%lld\n", query(x, y, 1)); } } printf("\n"); } return 0; }