【LOJ6029】 雅礼集训 2017 Day1 市场

市场

题意

叫你搞一棵线段树，实现区间加法、区间向下取整的除法、查询区间min、查询区间和

Solution

区间加、区间Min、区间和都是板子

可是这个区间向下取整没有结合律啊？怎么搞？

我们设一个区间的max值为(max)，min值为(min)

我们知道当(x)递增时，(lfloor {x over d} floor)是单调不减的

于是当(lfloor {max over d} floor - max = lfloor {min over d} floor - min)时，我们可以直接当成一个区间减法来处理

所以我们把原有的向下取整除的询问拆成了多个区间减法，就可以维护了

然而有人会觉得奇怪：这要是拆出来的区间很多，这算法不就GG了？

我们分析一下：

对于每个区间，在没有加法影响的情况下，要(log)的整除次数才会变成0

那么我们的区间加法，每次只能将(log)个区间的整除次数恢复为原来的

所以每次加法，我们都需要(log log)级别的除法次数，才可以变成0

那这样的话，总共的修改的复杂度会是(O(n log_n log_d))的，其中d是除的值

这样复杂度就是对的了

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (o<<1)
#define rs (o<<1|1)
int minn[400010];
int maxn[400010];
int sum[400010];
int tag[400010];
void pushup(int o){
    minn[o]=min(minn[ls],minn[rs]);
    maxn[o]=max(maxn[ls],maxn[rs]);
    sum[o]=sum[ls]+sum[rs];
}
void pd(int o,int l,int r,int val){
    int len=(r-l+1);
    tag[o]+=val;
    sum[o]+=len*val;
    minn[o]+=val;
    maxn[o]+=val;
}
void pushdown(int o,int l,int r){
    if(tag[o]){
        int mid=(l+r)/2;
        pd(ls,l,mid,tag[o]),pd(rs,mid+1,r,tag[o]);
        tag[o]=0;
    }
}
int a[100010];
void build(int o,int l,int r){
    if(l==r){
        sum[o]=minn[o]=maxn[o]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(o);
}
void update1(int o,int l,int r,int L,int R,int val){
    if(L<=l&&r<=R){
        tag[o]+=val;
        sum[o]+=val*(r-l+1);
        minn[o]+=val;
        maxn[o]+=val;
        return;
    }
    pushdown(o,l,r);
    int mid=(l+r)/2;
    if(L<=mid)update1(ls,l,mid,L,R,val);
    if(mid<R)update1(rs,mid+1,r,L,R,val);
    pushup(o); 
}
int divww(int k,int val){
    if(k<0)return (k-val+1)/val;
    else return k/val;
}
void update2(int o,int l,int r,int L,int R,int val){
    if(L<=l&&r<=R){
        if((minn[o]-divww(minn[o],val))==(maxn[o]-divww(maxn[o],val))){
            int tmp=maxn[o]-divww(maxn[o],val);
            tag[o]-=tmp;
            minn[o]-=tmp;
            maxn[o]-=tmp;
            sum[o]-=(r-l+1)*tmp;
            return;
        }
    }
    pushdown(o,l,r);
    int mid=(l+r)/2;
    if(L<=mid)update2(ls,l,mid,L,R,val);
    if(mid<R)update2(rs,mid+1,r,L,R,val);
    pushup(o);
}
int query1(int o,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return sum[o];
    }
    pushdown(o,l,r);
    int mid=(l+r)/2;
    int tmp=0;
    if(L<=mid)tmp+=query1(ls,l,mid,L,R);
    if(mid<R)tmp+=query1(rs,mid+1,r,L,R);
    return tmp; 
}
int query2(int o,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return minn[o];
    }
    pushdown(o,l,r);
    int mid=(l+r)/2;
    int tmp=1e17;
    if(L<=mid)tmp=min(tmp,query2(ls,l,mid,L,R));
    if(mid<R)tmp=min(tmp,query2(rs,mid+1,r,L,R));
    return tmp; 
}
signed main(){
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,q;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=q;++i){
        int opt;
        scanf("%lld",&opt);
        if(opt==1){
            int l,r,c;
            scanf("%lld%lld%lld",&l,&r,&c);
            l++,r++;
            update1(1,1,n,l,r,c);
        }
        if(opt==2){
            int l,r,c;
            scanf("%lld%lld%lld",&l,&r,&c);
            l++,r++;
            update2(1,1,n,l,r,c);
        }
        if(opt==3){
            int l,r;
            scanf("%lld%lld",&l,&r);
            l++,r++;
            printf("%lld
",query2(1,1,n,l,r));
        }
        if(opt==4){
            int l,r;
            scanf("%lld%lld",&l,&r);
            l++,r++;
            printf("%lld
",query1(1,1,n,l,r));
        }
    }
}