题目：
很多邪恶的战列舰在战斗前被安排在一条线上。我们的指挥官决定使用我们的秘密武器来消灭战列舰。每艘战列舰都可以被标记为耐力值。对于我们秘密武器的每次攻击，它都可以降低战列舰连续部分的耐力，使它们的耐力达到其原始耐力值的平方根。在我们的秘密武器的一系列攻击中，指挥官想要评估武器的效果，所以他向你寻求帮助。
您被要求回答的查询，即战列舰线连续部分的耐久性之和。
请注意，平方根运算应向下舍入为整数。请注意，平方根运算应向下舍入为整数。
Input
输入包含多个测试样例，由 EOF 终止。
对于每个测试样例，第一行包含单个整数N，表示一行中有N艘邪恶的战舰。(1≤N≤100000)(1≤N≤100000)
第二行包含N个整数Ei，表示每艘战列舰从行首到终点的续航值。您可以假设所有耐久性值的总和小于263263。
下一行包含一个整数 M，表示操作和查询的数量。(1≤M≤100000)(1≤M≤100000)
对于以下 M行，每行包含三个整数T、X和Y。T=0表示秘密武器的动作，这将降低第X和第Y战列舰之间的战列舰的续航价值。包括第X和第Y。T=1 表示指挥官的查询，该查询要求战列舰在第X和第Y之间的续航力值之和（包括第X和第Y*）。
Output
对于每个测试用例，在第一行打印用例编号。然后为每个查询打印一行。请记住在每个测试用例后遵循一个空行。
Sample
Sample
| 输入copy | 输出copy |
|---|---|
| 10 1 2 3 4 5 6 7 8 9 10 | Case #1: |
| 1 2 3 4 5 6 7 8 9 10 | 19 |
| 5 | 7 |
| 0 1 10 | 6 |
| 1 1 10 | |
| 1 1 5 | |
| 0 5 8 | |
| 1 4 8 |
思路：这道题是简单题，平方无法打标记，但1的开方为1，tr[p].sum==tr[p].r - tr[p].l+1时说明这一段全为1，就不用更新了，（L可能大于R,要交换，无语,记得开long long）
代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 2000010
#define M (int)1e8-3
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline ULL read() {
ULL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void print(ULL x) {
if (x > 9)print(x / 10);
putchar(x % 10 ^ 48);
}
struct node
{
LL l, r, sum;
}tr[4*N];
LL arr[N],n,m,cnt;
void pushup(LL p)
{
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void build(LL p, LL l, LL r)
{
tr[p] = { l,r,arr[l]};
if (l == r)return;
LL m = l + r >> 1;
build(lc, l, m);
build(rc, m + 1, r);
pushup(p);
}
void update(LL p, LL x, LL y)
{
if (tr[p].sum ==tr[p].r - tr[p].l + 1)return;
if (tr[p].l == tr[p].r) { tr[p].sum = sqrt(tr[p].sum); return; }
LL m = tr[p].l + tr[p].r >> 1;
if (x <= m)update(lc, x, y);
if (y > m)update(rc, x, y);
pushup(p);
}
LL query(LL p, LL x, LL y)
{
if (x <= tr[p].l && tr[p].r <= y)
{
return tr[p].sum;
}
LL m = tr[p].l + tr[p].r >> 1;
LL sum = 0;
if (x <= m)sum += query(lc, x, y);
if (y > m)sum += query(rc, x, y);
return sum;
}
int main()
{
while (scanf("%lld",&n)!=EOF)
{
cnt++;
for (int i = 1; i <= n; i++)
{
arr[i] = read();
}
build(1, 1, n);
scanf("%lld", &m);
printf("Case #%lld:\n", cnt);
while (m--)
{
LL a = 0, x = 0, y = 0;
scanf("%lld%lld%lld", &a,&x,&y);
if (x > y)swap(x, y);
if (!a)
{
update(1, x, y);
}
else
{
printf("%lld\n", query(1, x, y));
}
}
printf("\n");
}
return 0;
}