[LOJ6029] 「雅礼集训 2017 Day1」市场

Solution

维护一个区间的最大值和最小值，如果下一次做除法时，二者的修改幅度相同，就直接修改，否则暴力递归下去

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6+5;
#define mid ((l+r)/2)
int n,m,a[N],mn[N],mx[N],tag[N],t[N];

void pushup(int p) {
    mn[p]=min(mn[p*2],mn[p*2+1]);
    mx[p]=max(mx[p*2],mx[p*2+1]);
    t[p]=t[p*2]+t[p*2+1];
}

void change(int p,int l,int r,int v) {
    tag[p]+=v;
    t[p]+=(r-l+1)*v;
    mn[p]+=v;
    mx[p]+=v;
}

void pushdown(int p,int l,int r) {
    change(p*2,l,mid,tag[p]);
    change(p*2+1,mid+1,r,tag[p]);
    tag[p]=0;
}

void build(int p,int l,int r) {
    if(l==r) {
        cin>>a[l];
        mn[p]=mx[p]=t[p]=a[l];
    }
    else {
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
}

void modify1(int p,int l,int r,int ql,int qr,int v) {
    if(l>qr || r<ql) return;
    if(l>=ql && r<=qr) {
        change(p,l,r,v);
    }
    else {
        pushdown(p,l,r);
        modify1(p*2,l,mid,ql,qr,v);
        modify1(p*2+1,mid+1,r,ql,qr,v);
        pushup(p);
    }
}

int divide(int x,int y) {
    return x/y - (x/y*y>x);
}

void modify2(int p,int l,int r,int ql,int qr,int v) {
    if(l>qr || r<ql) return;
    if(l>=ql && r<=qr && mx[p]-divide(mx[p],v)==mn[p]-divide(mn[p],v)) {
        change(p,l,r,divide(mx[p],v)-mx[p]);
    }
    else {
        pushdown(p,l,r);
        modify2(p*2,l,mid,ql,qr,v);
        modify2(p*2+1,mid+1,r,ql,qr,v);
        pushup(p);
    }
}

int query1(int p,int l,int r,int ql,int qr) {
    if(l>qr || r<ql) return 0;
    if(l>=ql && r<=qr) {
        return t[p];
    }
    else {
        pushdown(p,l,r);
        return query1(p*2,l,mid,ql,qr) + query1(p*2+1,mid+1,r,ql,qr);
    }
}

int query2(int p,int l,int r,int ql,int qr) {
    if(l>qr || r<ql) return 1e9;
    if(l>=ql && r<=qr) {
        return mn[p];
    }
    else {
        pushdown(p,l,r);
        return min(query2(p*2,l,mid,ql,qr), query2(p*2+1,mid+1,r,ql,qr));
    }
}

signed main() {
    cin>>n>>m;
    build(1,1,n);
    int opt,ql,qr,v;
    for(int i=1;i<=m;i++) {
        cin>>opt>>ql>>qr;
        ++ql;
        ++qr;
        if(opt<3) cin>>v;
        if(opt==1) modify1(1,1,n,ql,qr,v);
        if(opt==2) modify2(1,1,n,ql,qr,v);
        if(opt==3) cout<<query2(1,1,n,ql,qr)<<endl;
        if(opt==4) cout<<query1(1,1,n,ql,qr)<<endl;
    }
}