SPOJ_2713
查询区间和很容易用线段树实现，而开方操作乍一看是没法用下传lazy标记的办法实现的，但仔细想一下，实际上每个数最多被开方的次数也是很有限的，只要最后开成1或者0，那么之后都不会再变了。
因此我们可以用一个finish标记表示当前区间内是否还有数在开方后发生变化，如果有的话finish为0，否则为1，每次开方都沿finish为0的区间更新到底，由于被开方次数有限，所以整体的复杂度还是可以承受的。
#include<stdio.h> #include<string.h> #include<math.h> #define MAXD 100010 long long sum[4 * MAXD], a[MAXD]; int N, finish[4 * MAXD]; void Swap(int &x, int &y) { int t; t = x, x = y, y = t; } void update(int cur) { int ls = cur << 1, rs = cur << 1 | 1; sum[cur] = sum[ls] + sum[rs]; if(finish[ls] && finish[rs]) finish[cur] = 1; else finish[cur] = 0; } void build(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; if(x == y) { sum[cur] = a[x]; if(a[x] == 0 || a[x] == 1) finish[cur] = 1; else finish[cur] = 0; return ; } build(ls, x, mid); build(rs, mid + 1, y); update(cur); } void init() { int i; for(i = 1; i <= N; i ++) scanf("%lld", &a[i]); build(1, 1, N); } void dfs(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; if(x == y) { sum[cur] = (long long)sqrt(sum[cur] + 0.5); if(sum[cur] == 0 || sum[cur] == 1) finish[cur] = 1; return ; } if(!finish[ls]) dfs(ls, x, mid); if(!finish[rs]) dfs(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(!finish[cur]) dfs(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 Search(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 Search(ls, x, mid, s, t); else if(mid + 1 <= s) return Search(rs, mid + 1, y, s, t); else return Search(ls, x, mid, s, t) + Search(rs, mid + 1, y, s, t); } void solve() { int i, j, k, q, x, y; scanf("%d", &q); for(i = 0; i < q; i ++) { scanf("%d%d%d", &k, &x, &y); if(x > y) Swap(x, y); if(k == 0) refresh(1, 1, N, x, y); else printf("%lld\n", Search(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; }