题目传送门
Can you answer these queries?
题目大意
给你一个长度为n的序列，和序列中每个元素的值，和m次操作 分别给出op，x，y 如果op=0则更新区间x~y，更新操作为对每个值取平方根向下取整 op==1则查询区间x~y的元素和
思路
显然线段树（毕竟我是练习线段树才找的这个题），区间更新，区间查询，维护区间和 注意点比较多： 元素的范围是long long 每组数据后换行 区间均为1时特判一下，不进行后续更新 区间x不一定小于y，记得处理一下
AC Code
#include<bits/stdc++.h>
using namespace std
;
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N
=1e5 +9;
int n
, m
;
long long a
[N
];
int op
, x
, y
;
struct segtree
{
long long sum
;
}tr
[N
<<2];
inline int lc(int p
) {return p
<<1;}
inline int rc(int p
) {return p
<<1|1;}
inline void push_up(int p
) {tr
[p
].sum
=tr
[lc(p
)].sum
+ tr
[rc(p
)].sum
;}
inline void build(int p
, int l
, int r
){
if(l
==r
) {scanf("%lld", &tr
[p
].sum
); return ;}
int mid
=(l
+r
)>>1;
build(lc(p
), l
, mid
);
build(rc(p
), mid
+1, r
);
push_up(p
);
}
inline void updata(int p
, int l
, int r
, int x
, int y
){
if(x
==y
){
tr
[p
].sum
=sqrt(tr
[p
].sum
);
return ;
}
if(l
<=x
&& r
>=y
&& tr
[p
].sum
==y
-x
+1) return ;
int mid
=(x
+y
)>>1;
if(l
<=mid
) updata(lc(p
), l
, r
, x
, mid
);
if(r
>mid
) updata(rc(p
), l
, r
, mid
+1, y
);
push_up(p
);
}
inline long long query(int p
, int l
, int r
, int x
, int y
){
if(l
<=x
&& r
>=y
) return tr
[p
].sum
;
long long ans
=0;
int mid
=(x
+y
)>>1;
if(l
<=mid
) ans
+=query(lc(p
), l
, r
, x
, mid
);
if(r
>mid
) ans
+=query(rc(p
), l
, r
, mid
+1, y
);
return ans
;
}
signed main(){
int k
=0;
while(scanf("%d", &n
)!=EOF){
build(1,1,n
);
scanf("%d", &m
);
printf("Case #%d:\n", ++k
);
while(m
--){
scanf("%d%d%d", &op
, &x
, &y
);
if(x
>y
) swap(x
,y
);
if(op
) printf("%lld\n", query(1,x
,y
,1,n
));
else updata(1,x
,y
,1,n
);
}
printf("\n");
}
return 0;
}
