HDU – 4027 Can you answer these queries? ([线段树] 区间开方修改（近似同值标记）+区间和查询)

• p为0时，将a~b区间的数更新为原来的平方根
• p为1时，求区间a~b的数的和

• 将单点修改部分改为
• if(l<=mid)change(p*2,l,r);
  if(r>mid)change(p*2+1,l,r);
• 防止超时，更新时判断当[t[p].l,t[p].r]中都为1则区间返回
• 即t[p].sum==t[p].r-t[p].l+1

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn=1e6+10;
ll a[maxn];
struct SegmentTree {
	int l,r;
	ll sum;
} t[maxn * 4];
void build(int p,int l,int r) { //build(1，1，n) 1为根节点
	t[p].l=l,t[p].r=r;
	if(l==r) {//1
		//t[p].sum=a[l];
		scanf("%lld", &t[p].sum);
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;//2
}
void change(int p,int l,int r) { //change(1,x,v) 1为根节点
	
	if(t[p].l==t[p].r) {//3
        t[p].sum=sqrt(t[p].sum);
		return ;
	}
	if(l<=t[p].l&&r>=t[p].r&&t[p].sum==t[p].r-t[p].l+1) return ;
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)change(p*2,l,r);
	if(r>mid)change(p*2+1,l,r);//4
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
ll ask(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r)
		return t[p].sum;
	ll sum=0;
	int mid = (t[p].l + t[p].r) / 2;
	if (l <= mid) {//5
		sum += ask(2 * p, l, r);
	}
	if (r > mid) {
		sum += ask(2 * p+1, l, r);
	}
	return sum;
}
int main()
{
    int n,m,t=0;
    while(scanf("%d",&n)==1)
    {
        int a,b,c;
        build(1,1,n);
        scanf("%d",&m);
        printf("Case #%d:\n",++t);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(b>c) swap(b,c);
            if(a)
                printf("%lld\n",ask(1,b,c));
            else
                change(1,b,c);
        }
        printf("\n");
    }
    return 0;
}