Can you answer these queries?(線分ツリーの単点更新)
2047 ワード
萌えるトランスポートドア
1つのlong long範囲内の数の開方は10回を超えないため、テーマは線分ツリーの単点更新問題に転化する.
1つのlong long範囲内の数の開方は10回を超えないため、テーマは線分ツリーの単点更新問題に転化する.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <cstdlib>
#include <algorithm>
#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int M = 1e5 + 100;
const int N = 1e7 + 100;
ll sum[M << 2];
void pushup(int u){
sum[u] = sum[ls] + sum[rs];
}
void build(int l,int r,int u){
if(l == r){
scanf("%I64d",sum + u);
}
else {
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(u);
}
}
void update(int L,int R,int l,int r,int u){
if(sum[u] == (r - l + 1)){
return;
}
if(l == r){
sum[u] = floor(sqrt((double)sum[u]));
}
else {
int mid = (l + r) >> 1;
if(L <= mid) update(L,R,lson);
if(R > mid) update(L,R,rson);
pushup(u);
}
}
ll query(int L,int R,int l,int r,int u){
if(L <= l && R >= r){
return sum[u];
}
else {
int mid = (l + r) >> 1;
ll res = 0;
if(L <= mid) res += query(L,R,lson);
if(R > mid) res += query(L,R,rson);
return res;
}
}
int main(){
//freopen("in","r",stdin);
int n,m,cnt = 0;
while(~scanf("%d",&n)){
build(1,n,1);
scanf("%d",&m);
printf("Case #%d:
",++cnt);
while(m--){
int t,l,r;
scanf("%d %d %d",&t,&l,&r);
if(l > r) swap(l,r);
if(!t) update(l,r,1,n,1);
else {
printf("%I64d
",query(l,r,1,n,1));
}
}
puts("");
}
return 0;
}