【题解】[UOJ 228] 基础数据结构练习题【线段树 均摊数据结构】

题目链接

题意

维护序列：

• 区间求和；
• 区间加；
• 区间开根并下取整。

(n,mleq 10^5)，(a_ileq 10^5)。

题解

注意到开根并下取整会让一个区间的数的差变小。于是额外维护区间最大最小值，当所有数相同时转化为区间减。

特殊情况：(n^2,n^2-1,n^2,n^2-1) 这样的序列反复进行操作 2,3 会一直保持极差为 1，于是特判一下，同样化为区间减。

复杂度均摊一下就对了。

#include<bits/stdc++.h>
using namespace std;
const int BUF_LEN=1<<19;
struct FastIO{
    char bufi[BUF_LEN+10],*PTi=bufi+BUF_LEN,*PTENDi=bufi+BUF_LEN;
    inline char gc(){
        (PTi==PTENDi)&&(bufi[fread(bufi,1,BUF_LEN,stdin)]=0,PTi=bufi);
        return *(PTi++);
    }
    char bufo[BUF_LEN+10],*PTo=bufo,*PTENDo=bufo+BUF_LEN;
    inline void pc(char c){
        (PTo==PTENDo)&&(fwrite(bufo,1,BUF_LEN,stdout),PTo=bufo);
        *(PTo++)=c;
    }
    void flush(){
        fwrite(bufo,1,PTo-bufo,stdout);
        PTo=bufo;
    }
    ~FastIO(){
        flush();
    }

    template<class T>inline void getint(T &x=0){
        char c=gc();
        int f=1;x=0;
        while(c<'0'||c>'9'){
            if(c=='-')f=-1;
            c=gc();
        }
        while(c>='0'&&c<='9'){
            x=x*10+c-'0'; 
            c=gc();
        }
        if(f==-1)x=-x;
    }
    operator int(){
        int v;getint(v);return v;
    }
    operator long long(){
        long long v;getint(v);return v;
    }
    template<class T>inline void putint(T x=0,char sep=' '){
        char tmp[20],len=0;
        if(x<0)pc('-'),x=-x;
        if(x==0){ pc('0');pc(sep);return; }
        while(x)tmp[len++]=x%10,x/=10;
        for(int i=len-1;~i;--i)pc(tmp[i]|'0');
        pc(sep);
    }
}io;

const int N=2e5+10;
#define ll long long
#define int long long
ll mx[N<<2],mn[N<<2],sum[N<<2],tag[N<<2];
void pushup(int x){
    sum[x]=sum[x<<1]+sum[x<<1|1];
    mx[x]=max(mx[x<<1],mx[x<<1|1]);
    mn[x]=min(mn[x<<1],mn[x<<1|1]);
}
void pushdown(int x,int l,int r){
    int mid=l+r>>1;
    mx[x<<1]+=tag[x];
    mx[x<<1|1]+=tag[x];
    mn[x<<1]+=tag[x];
    mn[x<<1|1]+=tag[x];
    sum[x<<1]+=tag[x]*(mid-l+1);
    sum[x<<1|1]+=tag[x]*(r-mid);
    tag[x<<1]+=tag[x];
    tag[x<<1|1]+=tag[x];
    tag[x]=0;
}

void mdf1(int l,int r,int v,int x,int nl,int nr){
    if(nr<l||nl>r)return;
    if(l<=nl&&nr<=r){
        mx[x]+=v;
        mn[x]+=v;
        sum[x]+=(nr-nl+1ll)*v;
        tag[x]+=v;
        return ;
    }
    pushdown(x,nl,nr);
    int mid=nl+nr>>1;
    mdf1(l,r,v,x<<1,nl,mid);
    mdf1(l,r,v,x<<1|1,mid+1,nr);
    pushup(x);
}
void mdf2(int l,int r,int x,int nl,int nr){
    if(nr<l||nl>r)return;
    pushdown(x,nl,nr);
    if(l<=nl&&nr<=r){
        if(mx[x]==mn[x]){
            mdf1(nl,nr,(ll)(sqrt(mx[x]))-mx[x],x,nl,nr);
            return;
        }
        if(mx[x]==mn[x]+1&&(ll)(sqrt(mx[x]))==(ll)(sqrt(mn[x]))+1){
            mdf1(nl,nr,(ll)(sqrt(mx[x]))-mx[x],x,nl,nr);
            return;
        }
    }
    int mid=nl+nr>>1;
    mdf2(l,r,x<<1,nl,mid);
    mdf2(l,r,x<<1|1,mid+1,nr);
    pushup(x);
}
ll query(int l,int r,int x,int nl,int nr){
    if(nr<l||nl>r)return 0;
    if(l<=nl&&nr<=r)return sum[x];
    pushdown(x,nl,nr);
    int mid=nl+nr>>1;
    return query(l,r,x<<1,nl,mid)+query(l,r,x<<1|1,mid+1,nr);
}
int a[N];
void build(int x,int l,int r){
    if(l==r){
        mx[x]=mn[x]=sum[x]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
signed main(){
    int n=io,m=io;
    for(int i=1;i<=n;i++)a[i]=io;
    build(1,1,n);
    while(m--){
        int tp=io;
        if(tp==1){
            int l=io,r=io,x=io;
            mdf1(l,r,x,1,1,n);
        }
        if(tp==2){
            int l=io,r=io;
            mdf2(l,r,1,1,n);
        }
        if(tp==3){
            int l=io,r=io;
            io.putint(query(l,r,1,1,n),'
');
        }
    }
}