hdu4027-Can you answer these queries? -（线段树+剪枝）
题意：给n个数，m个操作，分两种操作，一种是将一段区间的每个数都开根号，另一种是查询区间和。
解题：显然对每个数开根号不能用lazy的区间更新。一个一个更新必然爆时间，对1开根号还是1，如果一段区间都是1，就不用更新了，判断r-l+1 = query()。其他都是线段树的模板。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; ll sum[100086*4]; ll a[100086]; int n,m; void build(int l,int r,int rt) { if(l==r) { sum[rt]=a[l]; return; } int mid=(l+r)/2; build(l,mid,rt*2); build(mid+1,r,rt*2+1); sum[rt]=sum[rt*2]+sum[rt*2+1]; } void update(int L,int R,int l,int r,int rt) { if(l==r) { sum[rt]=sqrt(sum[rt]); return ; } if( L<=l && r<=R && sum[rt]==(ll)(r-l+1) )///当前区间整个都在要修改的L和R之间，并且该区间里都是1 return ;///直接返回，对每个1开根号后也是1，不变 int mid=(l+r)/2; if(L<=mid) update(L,R,l,mid,rt*2); if(mid+1<=R) update(L,R,mid+1,r,rt*2+1); sum[rt]=sum[rt*2]+sum[rt*2+1]; } ll query(int L,int R,int l,int r,int rt) { if( L<=l && r<=R ) return sum[rt]; int mid=(l+r)/2; ll res=0; if(L<=mid) res+=query(L,R,l,mid,rt*2); if(mid+1<=R) res+=query(L,R,mid+1,r,rt*2+1); return res; } int main() { int cnt=1; while( scanf("%d",&n)!=EOF ) { memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); printf("Case #%d: ",cnt++); scanf("%d",&m); int T,L,R; for(int i=1;i<=m;i++) { scanf("%d%d%d",&T,&L,&R); if(L>R) swap(L,R); if(T==0) update(L,R,1,n,1); else printf("%lld ",query(L,R,1,n,1)); } printf(" ");///坑 } return 0; }