You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.
Notice that the square root operation should be rounded down to integer.
Input
The input contains several test cases, terminated by EOF.
For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)
The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 2 63.
The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)
For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.
Output
For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.
Sample Input
10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8
Sample Output
Case #1: 19 7 6
题目大意：
给你n个数，有m次询问，每次询问三个数t,x,y当t=0时，将第x个数到第y个数都进行开方运算。t=1时回答第x个数到第y个数的和。
1.题目没有说x和y的大小。需要进行比较
2.每次单点更新会超时。技巧（我的做法）：开一个标记数组，用flag[rt] = flag[ls]&flag[rs]更新标记状态。当flag[rt]=1代表以该节点为父节点的子树所代表的区间的值都为1，都为1不用更新，直接return
3.每个测试用例后跟一个换行。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ls rt<<1
#define rs rt<<1|1
#define push_up sum[rt] = sum[ls]+sum[rs], flag[rt] = flag[ls]&flag[rs]
using namespace std;
typedef long long ll;
const ll N = 100000+10;
ll num[N], sum[N<<2], flag[N<<2];
void build(ll rt, ll l, ll r){if(l == r){sum[rt] = num[l];if(sum[rt] == 1)flag[rt] = 1;return ;}ll mid = l+(r-l)/2;build(ls, l, mid);build(rs, mid+1, r);push_up;
}
void update(ll rt, ll l, ll r, ll ul, ll ur){if(flag[rt] == 1)return ;if(l == r){sum[rt] = sqrt(sum[rt]);if(sum[rt] == 1)flag[rt] = 1;return ;}ll mid = l+(r-l)/2;if(mid >= ul)update(ls, l, mid, ul, ur);if(mid < ur)update(rs, mid+1, r, ul, ur);push_up;
}
ll query(ll rt, ll l, ll r, ll ql, ll qr){if(ql <= l && r <= qr)return sum[rt];ll mid = l+(r-l)/2, ans = 0;if(mid >= ql)ans += query(ls, l, mid, ql, qr);if(mid < qr)ans += query(rs, mid+1, r, ql, qr);return ans;
}
int main(){ll n, m, cas=1;while(~scanf("%lld", &n)){printf("Case #%lld:\n", cas++);memset(flag, 0, sizeof(flag));for(ll i=0; i<n; ++i)scanf("%lld", num+i);build(1, 0, n-1);scanf("%lld", &m);while(m--){ll op;scanf("%lld", &op);if(op){ll ql, qr;scanf("%lld%lld", &ql, &qr);if(ql > qr)swap(ql, qr);printf("%lld\n", query(1, 0, n-1, ql-1, qr-1));continue;}ll ul, ur;scanf("%lld%lld", &ul, &ur);if(ul > ur)swap(ul, ur);update(1, 0, n-1, ul-1, ur-1);}printf("\n");}return 0;
}