https://vjudge.net/contest/66989#problem/H
此题真是坑到爆！！说好的四舍五入害我改了一个多小时，不用四舍五入！！有好几个坑点，注意要交换l，r的位置，还有输出格式问题
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 const int maxn=100010; ll value[maxn<<2]; void pushup(int rt)//pushup应该随题目变化情况改变而改变 { value[rt]=value[rt<<1]+value[rt<<1|1]; } void btree(int l,int r,int rt) { if(l==r) { scanf("%lld",&value[rt]); return ; } int m=(l+r)>>1; btree(ls); btree(rs); pushup(rt); } void update(int L,int R,int l,int r,int rt) { if(value[rt]==r-l+1)return;//没有这句就会超时 if(l==r) { value[rt]=(ll)(sqrt(value[rt]));//不四舍五入 return; } int m=(l+r)>>1; if(L<=m)update(L,R,ls); if(R>m)update(L,R,rs); pushup(rt); } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R)return value[rt]; int m=(l+r)>>1; ll ans=0; if(L<=m)ans+=query(L,R,ls); if(R>m)ans+=query(L,R,rs); return ans; } int main() { int n,m,cnt=0; while(~scanf("%d",&n)){ printf("Case #%d: ",++cnt); btree(1,n,1); scanf("%d",&m); while(m--){ int t,l,r; scanf("%d%d%d",&t,&l,&r); if(l>r)swap(l,r);//这一点也是容易被坑的！！ if(t==0)update(l,r,1,n,1); if(t==1)printf("%lld ",query(l,r,1,n,1)); } printf(" "); } return 0; } /* 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 */