hdu 4027 线段树

我只想说   在初始更新是别一个个更新     就这样 超时了一次     用数组存起来   跑lg（n）就行   其他的都差不多；

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

__int64 num[4*100000],map[100010];
int deal(int L,int R,int point)
{
    if(L==R)
    {
        num[point]=map[L];
        return 0;
    }    
    int mid=(L+R)/2;
    deal(L,mid,LL(point));
    deal(mid+1,R,RR(point));
    num[point]=num[LL(point)]+num[RR(point)];
    return 0;
}
int update(int L,int R,int left,int right,int point)
{
    int mid=(L+R)/2;
    if(num[point]==R-L+1) return 0;
    if(L==R) 
    {
        num[point]=sqrt(num[point]);
        return 0;
    }    
        if(right<=mid)
        {
            update(L,mid,left,right,LL(point));
        }
        else if(left>mid)
        {
            update(mid+1,R,left,right,RR(point));
        }
        else
        {
            update(L,mid,left,mid,LL(point));
            update(mid+1,R,mid+1,right,RR(point));
        }
    num[point]=num[LL(point)]+num[RR(point)];
    return 0;
}
__int64 find(int L,int R,int left,int right,int point)
{
    if(num[point]==R-L+1) return right-left+1;
    if(L==left&&R==right)
    {
        return num[point];
    }    
    int mid=(L+R)/2;
    __int64 s=0;
    if(right<=mid)
    {
        s+=find(L,mid,left,right,LL(point));
    }
    else if(left>mid)
    {
        s+=find(mid+1,R,left,right,RR(point));
    }
    else
    {
        s+=find(L,mid,left,mid,LL(point));
        s+=find(mid+1,R,mid+1,right,RR(point));
    }
    return s;
}
int main()
{
    int n,i,j,a,left,right,m,d=1;
    while(~scanf("%d",&n))
    {
        memset(num,0,sizeof(num));
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&map[i]);        
        }
        deal(1,n,1);
        scanf("%d",&m);
        printf("Case #%d:\n",d++);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&left,&right);
            if(left>right)
            {
                int k=left;
                left=right;
                right=k;
            }
            if(a==0)
            {
                update(1,n,left,right,1);
            }
            else printf("%I64d\n",find(1,n,left,right,1));
        }
        printf("\n");
    }
}

hdu 4027 线段树

原文：http://blog.csdn.net/zxf654073270/article/details/44624489