又是线段树。
区间开平方求和，套路题。
如果开到了1就不用再开下去了，否则直接到底。
记得 l > r 时交换 l r
#include <cstdio>
#include <cmath>
#include <algorithm>
typedef long long LL;
const int N = ;
struct SegmentTree {
LL sum[N << ];
bool vis[N << ]; inline void pushup(int l, int r, int o) {
if(l == r) {
if(sum[o] == ) {
vis[o] = ;
}
return;
}
sum[o] = sum[o << ] + sum[o << | ];
vis[o] = (sum[o] == (r - l + ));
return;
}
void change(int L, int R, int l ,int r, int o) {
if(vis[o]) {
return;
}
int mid = (l + r) >> ;
if(l == r) {
sum[o] = (LL)(sqrt((long double)(sum[o])));
pushup(l, r, o);
return;
}
if(L <= mid) {
change(L, R, l, mid, o << );
}
if(mid < R) {
change(L, R, mid + , r, o << | );
}
pushup(l, r, o);
return;
}
LL ask(int L, int R, int l, int r, int o) {
if(L <= l && r <= R) {
return sum[o];
}
if(r < L || R < l) {
return ;
}
int mid = (l + r) >> ;
return ask(L, R, l, mid, o << ) + ask(L, R, mid + , r, o << | );
}
void build(int l, int r, int o) {
if(l == r) {
scanf("%lld", &sum[o]);
pushup(l, r, o);
return;
}
int mid = (l + r) >> ;
build(l, mid, o << );
build(mid + , r, o << | );
pushup(l, r, o);
return;
}
}SgT; int main() {
int n;
scanf("%d", &n);
SgT.build(, n, );
int m;
scanf("%d", &m);
int f, x, y;
while(m--) {
scanf("%d%d%d", &f, &x, &y);
if(x > y) {
std::swap(x, y);
}
if(f) {
printf("%lld\n",SgT.ask(x, y, , n, ));
}
else {
SgT.change(x, y, , n, );
}
}
return ;
}
AC代码