UOJ #228. 基础数据结构练习题线段树 + 均摊分析 + 神题

今天药忘吃喽~ 2021-11-17 16:14 191阅读 0赞

[题目链接 ][Link 1]

一个数被开方

#include<bits/stdc++.h> 
    #define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)        
    #define maxn 300003 
    #define ll long long 
    using namespace std;   
    int n,m;
    ll mx[maxn<<2],mn[maxn<<2],arr[maxn],sum[maxn<<2],lazy[maxn<<2];  
    void pushup(int now,int l,int r) 
    { 
        int mid=(l+r)>>1;        
        mn[now]=mn[now<<1], mx[now]=mx[now<<1], sum[now]=sum[now<<1];   
        if(r>mid) 
            mn[now]=min(mn[now], mn[(now<<1)|1]), mx[now]=max(mx[now], mx[(now<<1)|1]), sum[now]+=sum[(now<<1)|1];   
    }    
    void mark(int l,int r,int now,ll delta) 
    {    
        mx[now]+=delta,mn[now]+=delta,lazy[now]+=delta, sum[now]+=1ll*(r-l+1)*delta; 
    }   
    void pushdown(int l,int r,int now) 
    {  
        if(lazy[now]) 
        {
            int mid=(l+r)>>1;  
            if(mid>=l) mark(l,mid,now<<1,lazy[now]);  
            if(r>mid) mark(mid+1,r,(now<<1)|1,lazy[now]);     
            lazy[now]=0;    
        }
    } 
    void build(int l,int r,int now) 
    {
        if(l==r) 
        {
            mn[now]=mx[now]=sum[now]=arr[l]; 
            return;  
        } 
        int mid=(l+r)>>1;   
        if(l<=mid) build(l,mid,now<<1); 
        if(r>mid ) build(mid+1,r,(now<<1)|1);   
        pushup(now,l,r); 
    }     
    void change(int l,int r,int now,int L,int R,ll delta) 
    { 
        if(l>=L&&r<=R) 
        { 
            mark(l,r,now,delta);  
            return; 
        } 
        pushdown(l,r,now); 
        int mid=(l+r)>>1;  
        if(L<=mid) change(l,mid,now<<1,L,R,delta);  
        if(R>mid) change(mid+1,r,(now<<1)|1,L,R,delta);   
        pushup(now,l,r);     
    } 
    void update(int l,int r,int now,int L,int R) 
    {   
        if(l>=L&&r<=R&&(ll)(mx[now]-(ll)sqrt(mx[now])) == (ll)(mn[now]-(ll)sqrt(mn[now])))
        {
            mark(l,r,now,(ll)((ll)sqrt(mx[now])-mx[now]));        
            return;   
        }  
        pushdown(l,r,now);   
        int mid=(l+r)>>1; 
        if(L<=mid)update(l,mid,(now<<1),L,R);  
        if(R>mid) update(mid+1,r,(now<<1)|1,L,R);   
        pushup(now,l,r);     
    }   
    long long query(int l,int r,int now,int L,int R) 
    {
        if(l>=L&&r<=R) return sum[now]; 
        pushdown(l,r,now);    
        int mid=(l+r)>>1; 
        ll tmp=0;   
        if(L<=mid) tmp+=query(l,mid,now<<1,L,R);  
        if(R>mid)  tmp+=query(mid+1,r,(now<<1)|1,L,R);   
        return tmp;     
    }
    int main()
    {
        // setIO("input");        
        scanf("%d%d",&n,&m);  
        for(int i=1;i<=n;++i) scanf("%lld",&arr[i]);  
        build(1,n,1);               
        for(int i=1;i<=m;++i) 
        {
            int opt,l,r; 
            ll x; 
            scanf("%d",&opt);              
            if(opt==1) 
            { 
                scanf("%d%d%lld",&l,&r,&x);   
                change(1,n,1,l,r,x);  
            }
            if(opt==2) 
            { 
                scanf("%d%d",&l,&r);   
                update(1,n,1,l,r);   
            }
            if(opt==3) 
            {
                scanf("%d%d",&l,&r); 
                printf("%lld\n",query(1,n,1,l,r));  
            }
        }
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11225243.html

[Link 1]: http://uoj.ac/problem/228