https://cn.vjudge.net/problem/HDU-4027
题意
给一个有初始值的数组，存在两种操作，T=0时将[L,R]的值求平方根，T=1时查询[L,R]的和。
分析
显然不符合加法合并原理，只能考虑直接点更新，可这样就完蛋了。。突破口在于sqrt，2^63-1只需要sqrt了6、7次就变为1了，而1再sqrt也无意义。所以在更新时，只要这段区间的和等于区间长度，说明都为1，那么就不需要继续更新下去了。查询时就是区间求和。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = + ;
const int maxm = + ;
const int mod = ;
int n;
struct ND{
int l,r;
ll sum;
}tree[maxn<<];
int pre;
int ans[maxn];
void pushup(int rt){
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;
}
void pushdown(int rt){
if(tree[rt].l==tree[rt].r){
tree[rt].sum=1ll*sqrt(tree[rt].sum);
return;
}
pushdown(rt<<);
pushdown(rt<<|);
pushup(rt);
}
void build(int rt,int l,int r){
tree[rt].l=l,tree[rt].r=r;
if(l==r){
scanf("%lld",&tree[rt].sum);
return;
}
int mid=(l+r)>>;
build(rt<<,l,mid);
build(rt<<|,mid+,r);
pushup(rt);
}
void update(int rt,int L,int R){
if(L<=tree[rt].l&&tree[rt].r<=R){
if(tree[rt].r-tree[rt].l+==tree[rt].sum) return;
pushdown(rt);
return;
}
int mid=(tree[rt].l+tree[rt].r)>>;
if(mid>=L) update(rt<<,L,R);
if(mid<R) update(rt<<|,L,R);
pushup(rt);
} ll query(int rt,int L,int R){
if(L<=tree[rt].l&&tree[rt].r<=R){
return tree[rt].sum;
}
// pushdown(rt);
ll sum=;
int mid=(tree[rt].l+tree[rt].r)>>;
if(mid>=L) sum+=query(rt<<,L,R);
if(mid<R) sum+=query(rt<<|,L,R);
return sum;
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t,cas=;
// scanf("%d",&t);
while(~scanf("%d",&n)){
build(,,n);
int m;
scanf("%d",&m);
printf("Case #%d:\n",cas++);
while(m--){
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
if(x>y) swap(x,y);
if(t==){
printf("%lld\n",query(,x,y));
}else{
update(,x,y);
}
}
puts("");
}
return ;
}