hdu 4027 Can you answer these queries?

线段树。

1、成段更新。每次把区间的每个值都变为它的平方根（如果区间都是一就不用再更新下去了）。

2、区间求和。

View Code

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 #define lson l , m , rt << 1
 9 #define rson m + 1 , r , rt << 1 | 1
10 
11 typedef __int64 ll;
12 const int maxn = 100010;
13 ll sum[maxn<<2];
14 ll len[maxn<<2];
15 
16 void PushUp(int rt)
17 {
18     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
19 }
20 void build(int l ,int r ,int rt)
21 {
22     len[rt] = r - l + 1;
23     if(l == r)
24     {
25         scanf("%I64d",&sum[rt]);
26         return ;
27     }
28     int m = (l + r) >> 1;
29     build(lson);
30     build(rson);
31     PushUp(rt);
32 }
33 void update(int L,int R,int l,int r,int rt)
34 {
35     if(l == r)
36     {
37         sum[rt] = (ll)sqrt(1.0*sum[rt]);
38         return ;
39     }
40     int m = (l + r) >> 1;
41     if(L <= m && (sum[rt<<1] != len[rt<<1]))update(L,R,lson);
42     if(m < R && (sum[rt<<1|1] != len[rt<<1|1]))update(L,R,rson);
43     PushUp(rt);
44 }
45 ll query(int L,int R,int l,int r,int rt)
46 {
47     if(L <= l && r <= R)
48     {
49         return sum[rt];
50     }
51     int m = (l + r) >> 1;
52     ll ret = 0;
53     if(L <= m)ret += query(L,R,lson);
54     if(m < R)ret += query(L,R,rson);
55     return ret;
56 }
57 int main()
58 {
59     #ifndef ONLINE_JUDGE
60     freopen("in","r",stdin);
61     #endif
62     int n;
63     int cas = 0;
64     while(scanf("%d",&n)!=EOF)
65     {
66         build(1 , n , 1);
67         int m,T,a,b;
68         printf("Case #%d:\n",++cas);
69         scanf("%d",&m);
70         while(m--)
71         {
72             scanf("%d%d%d",&T,&a,&b);
73             if(a>b)swap(a,b);
74             if(T == 0)update(a,b,1,n,1);
75             else printf("%I64d\n",query(a,b,1,n,1));
76         }
77         puts("");
78     }
79     return 0;
80 }