这道题是受到大犇MagHSK的启发我才得以想出来的，蒟蒻觉得自己的代码跟MagHSK大犇的代码完全比不上，所以这里蒟蒻就套用了MagHSK大犇的代码（大家可以关注下我的博客，友情链接就是大犇MagHSK的博客，大神是山东省队队员，他的博客中的题的质量都比我高几个档次）；
这是大神MagHSK的解释：因为10^9顶多开5~6次方就成了1了（当然这里的等于是向下取整的）因此对于修改操作，如果某一段不是1或不是0，就暴力修改，如果是1/0就不管他。修改完之后update一下就好了。
题目上说我们给出的是一个可修改（修改的规则就是对要修改的区间内每个数开平方）、可查询（就是求一段区间上所有数字的和）的一个数列。
显然我们直接暴力的效率是很低的，那么我们就采取了线段树——一种神奇的数据结构。
线段树作为可修改可查询的数据结构，基本操作就是点更新、区间更新和区间查询（包括最小值、最大值和区间和）这里因为是解题报告，所以就不跟大家讲基本思路了，直接进入正题，基本思路和代码板子请自己去看。
这里因为是对区间内的数开平方，所以区间更新就有点不大好用了（主要是没法直接标记区间然后开平方，这样会计算错误），然后数据范围也不算大，所以我们就考虑搜索线段树上的每一个在需要update（更新）的区间的所有点进行开方点更新，然后再push_up（往上面推，求出每个线段树上区间的和）上去。这样就可以完成更新任务了。（push_up和change（update）函数代码跟板子上不大一样，all数组就是标记这个区间内的数还值不值得进行开平方操作，显然如果这个区间内的和为1或者0的时候就不用开平方了，change的时候就可以省略了）。
区间查询的操作就是套板子，这个没什么需要思考的。
还是那句老话，要先考虑自己写，然后实在不会了再看题解，总是copy别人的代码自己的水平肯定上升得很慢。
废话不再说，上代码。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int INF = ;
int n;
LL sum[], A[];
bool all[];
void pu(int now) {
sum[now] = sum[now << ] + sum[now << | ];
all[now] = all[now << ] && all[now << | ];
}
void build(int now, int l, int r) {
if (l == r) {
sum[now] = A[l];
if (sum[now] == || sum[now] == )
all[now] = true;
return;
}
int mid = (l + r) >> ;
build(now << , l, mid);
build(now << | , mid + , r);
pu(now);
}
LL query(int now, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return sum[now];
}
int mid = (l + r) >> ;
LL ret = ;
if (ll <= mid) ret += query(now << , l, mid, ll, rr);
if (rr > mid) ret += query(now << | , mid + , r, ll, rr);
return ret;
}
void change(int now, int l, int r, int ll, int rr) {
if (all[now]) {
return;
}
if (l == r) {
sum[now] = sqrt(sum[now]);
if (sum[now] == || sum[now] == )
all[now] = true;
return;
}
int mid = (l + r) >> ;
if (ll <= mid) change(now << , l, mid, ll, rr);
if (rr > mid) change(now << | , mid + , r, ll, rr);
pu(now);
}
int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i)
scanf("%lld", A+i);
build(, , n);
int m, x, y, z;
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &x, &y, &z);
if (y > z) swap(y, z);
if (x==) {
printf("%lld\n", query(, , n, y, z));
} else {
change(, , n, y, z);
}
}
return ;
}
这次解题报告就完结啦，蒟蒻一般是在每周的星期三晚和星期天晚发解题报告，大家就不要在其他时间翻我的博客啦。