uoj228：基础数据结构练习题

题意：http://uoj.ac/problem/228

sol  ：线段树开根操作

　　　对于节点x，可以在max[x]-min[x]<=1时直接做，转化为区间减或区间覆盖

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#define int long long

using namespace std;

const int Mx=;

int n,m,a[Mx],Min[Mx],Max[Mx],sum[Mx];

int l[Mx],r[Mx],lson[Mx],rson[Mx],Add_tag[Mx],Cover_tag[Mx];

void pushup(int x)

{

    int L=lson[x],R=rson[x];

    Min[x]=min(Min[L],Min[R]);

    Max[x]=max(Max[L],Max[R]);

    sum[x]=sum[L]+sum[R];

}

void build(int x,int L,int R)

{

    l[x]=L,r[x]=R,lson[x]=x<<,rson[x]=x<<|;

    if(L==R) { Min[x]=a[L],Max[x]=a[L],sum[x]=a[L]; return ;}

    int mid=(L+R)>>;

    build(x<<,L,mid);

    build(x<<|,mid+,R);

    pushup(x);

}

void pushdown(int x)

{

    int LS=lson[x],RS=rson[x],LL=l[LS],LR=r[LS],RL=l[RS],RR=r[RS];

    if(Add_tag[x]!=)

    {

        Max[LS]+=Add_tag[x],Min[LS]+=Add_tag[x],sum[LS]+=(LR-LL+)*Add_tag[x];

        Max[RS]+=Add_tag[x],Min[RS]+=Add_tag[x],sum[RS]+=(RR-RL+)*Add_tag[x];

        if(Cover_tag[LS]<1e8) Cover_tag[LS]+=Add_tag[x];

        else Add_tag[LS]+=Add_tag[x];

        if(Cover_tag[RS]<1e8) Cover_tag[RS]+=Add_tag[x];

        else Add_tag[RS]+=Add_tag[x];

    }

    if(Cover_tag[x]<1e8)

    {

        Max[LS]=Cover_tag[x],Min[LS]=Cover_tag[x],sum[LS]=(LR-LL+)*Cover_tag[x];

        Max[RS]=Cover_tag[x],Min[RS]=Cover_tag[x],sum[RS]=(RR-RL+)*Cover_tag[x];

        Cover_tag[LS]=Cover_tag[x];

        Cover_tag[RS]=Cover_tag[x];

    }

    Add_tag[x]=,Cover_tag[x]=1e9;

}

void Add(int x,int ql,int qr,int val)

{

    int L=l[x],R=r[x];

    if(ql>R||qr<L) return ;

    if(ql<=L&&qr>=R)

    {

        if(Cover_tag[x]<1e8) Cover_tag[x]+=val;

        else Add_tag[x]+=val;

        Max[x]+=val,Min[x]+=val,sum[x]+=(R-L+)*val;

        return ;

    }

    pushdown(x);

    Add(lson[x],ql,qr,val);

    Add(rson[x],ql,qr,val);

    pushup(x);

}

void Cover(int x,int ql,int qr,int val)

{

    int L=l[x],R=r[x];

    Add_tag[x]=,Cover_tag[x]=val;

    Max[x]=val,Min[x]=val,sum[x]=(R-L+)*val;

}

void Sqrt(int x,int ql,int qr)

{

    int L=l[x],R=r[x];

    if(ql>R||qr<L) return ;

    if(ql<=L&&qr>=R&&Max[x]-Min[x]<=)

    {

        int mx=(int)sqrt(Max[x]),mn=(int)sqrt(Min[x]);

        if(mx==mn) Cover(x,L,R,mx);

        else Add(x,L,R,mx-Max[x]);

        return ;

    }

    pushdown(x);

    Sqrt(lson[x],ql,qr);

    Sqrt(rson[x],ql,qr);

    pushup(x);

}

int Query(int x,int ql,int qr)

{

    int L=l[x],R=r[x];

    if(ql>R||qr<L) return ;

    if(ql<=L&&qr>=R) return sum[x];

    pushdown(x);

    int ans=Query(lson[x],ql,qr)+Query(rson[x],ql,qr);

    pushup(x);

    return ans;

}

signed main()

{

    for(int i=;i<Mx;i++) Cover_tag[i]=1e9;

    scanf("%lld%lld",&n,&m);

    for(int i=;i<=n;i++) scanf("%lld",&a[i]);

    build(,,n);

    for(int i=,num,x,y,z;i<=m;i++)

    {

        scanf("%lld%lld%lld",&num,&x,&y);

        if(num==) scanf("%lld",&z),Add(,x,y,z);

        if(num==) Sqrt(,x,y);

        if(num==) printf("%lld\n",Query(,x,y));

    }

    return ;

}