HDU_4027
这个题目和HDU_3954有点像，由于开方这种运算我们没办法直接就将一段的和更新出来，但会发现即便是2^63能够被开方的次数也是很少的，因为一个数到1或者0之后我们就没必要再更新这个数了。所以，我们可以用num[]表示一个区间中不为0、1的整数的个数，如果我们要进行开方操作的区间内num[]的值不为0，我们就可以递归找到要更新的数并将其更新，同时更新路径上sum[]以及num[]的值。这样由于每个数被更新的次数不会超过10次，而每次找到一个需要更新的数的复杂度是O(logN)，所以总共的更新操作的复杂度约是O(10*N*logN)，是可以接受的。
此外，这个题目有个小trick，x有可能大于y，以后还是得多加小心了，题目中没有明确说明的情况还是考虑上为好。
#include<stdio.h> #include<string.h> #include<math.h> #define MAXD 100010 long long int sum[4 * MAXD], a[MAXD]; int N, M, num[4 * MAXD]; void update(int cur) { int ls = cur << 1, rs = (cur << 1) | 1; sum[cur] = sum[ls] + sum[rs]; num[cur] = num[ls] + num[rs]; } void build(int cur, int x, int y) { int mid = (x + y) / 2, ls = cur << 1, rs = (cur << 1) | 1; if(x == y) { sum[cur] = a[x]; if(sum[cur] == 1 || sum[cur] == 0) num[cur] = 0; else num[cur] = 1; return ; } build(ls, x, mid); build(rs, mid + 1, y); update(cur); } void init() { int i, j, k; for(i = 1; i <= N; i ++) scanf("%I64d", &a[i]); build(1, 1, N); } void change(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x == y) { long long int t = (long long int)sqrt((double)sum[cur] + 0.5); if(t * t > sum[cur]) -- t; sum[cur] = t; if(sum[cur] == 1 || sum[cur] == 0) num[cur] = 0; else num[cur] = 1; return ; } if(num[ls]) change(ls, x, mid); if(num[rs]) change(rs, mid + 1, y); update(cur); } void refresh(int cur, int x, int y, int s, int t) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t) { if(num[cur]) change(cur, x, y); return ; } if(mid >= s) refresh(ls, x, mid, s, t); if(mid + 1 <= t) refresh(rs, mid + 1, y, s, t); update(cur); } long long int query(int cur, int x, int y, int s, int t) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t) return sum[cur]; if(mid >= t) return query(ls, x, mid, s, t); else if(mid + 1 <= s) return query(rs, mid + 1, y, s, t); else return query(ls, x, mid, s, t) + query(rs, mid + 1, y , s, t); } void solve() { int i, j, k, T, x, y; scanf("%d", &M); for(i = 0; i < M; i ++) { scanf("%d%d%d", &T, &x, &y); if(x > y) k = x, x = y, y = k; if(!T) refresh(1, 1, N, x, y); else printf("%I64d\n", query(1, 1, N, x, y)); } } int main() { int t = 0; while(scanf("%d", &N) == 1) { init(); printf("Case #%d:\n", ++ t); solve(); printf("\n"); } return 0; }