22.8.19

ABC256_H

题意:

要求实现三种操作

• 将区间 \(L\) 到 \(R\) 中的数变为 \(\lfloor \frac{a_i}{x}\rfloor\)
• 将区间 \(L\) 到 \(R\) 中的数变为 \(x\)
• 查询 \(L\) 到 \(R\) 的区间和

思路:

\(x\geq2\), 那么考虑一个数最多做 \(log\) 次操作一, 对于操作二, 最多将势能升高 \(log\), 但是由于操作二推平了区间, 对于整个相同的区间, 没有必要每个数去改, 只需要改一个, 其他的数是相同的, 那么升高的势能的位置其实是常数级

所以此时直接势能线段树即可

#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
const int INF=1e16,mod=998244353,N=5e5+10;
int sum[N<<2],dep[N<<2],a[N];
void pushup(int p) {
    if(dep[ls(p)]==dep[rs(p)]&&dep[ls(p)]>=0) {
        dep[p]=dep[ls(p)];
    } else dep[p]=-1;
    sum[p]=sum[ls(p)]+sum[rs(p)];
}
void build(int p,int l,int r) {
    dep[p]=-1;
    if(l==r) {
        dep[p]=sum[p]=a[l];
        return;
    }
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
void pushdown(int l,int r,int p) {
    if(dep[p]!=-1) {
        dep[ls(p)]=dep[rs(p)]=dep[p];
        sum[ls(p)]=dep[p]*(mid-l+1);
        sum[rs(p)]=dep[p]*(r-mid);
        dep[p]=-1;
    }
}
void update1(int p,int l,int r,int nl,int nr,int x) {
    if(l>=nl&&r<=nr) {
        if(dep[p]!=-1) {
            dep[p]/=x;
            sum[p]=dep[p]*(r-l+1);
        } else {
            pushdown(l,r,p);
            update1(ls(p),l,mid,nl,nr,x);
            update1(rs(p),mid+1,r,nl,nr,x);
            pushup(p);
        }
        return;
    }
    pushdown(l,r,p);
    if(mid>=nl) update1(ls(p),l,mid,nl,nr,x);
    if(mid+1<=nr) update1(rs(p),mid+1,r,nl,nr,x);
    pushup(p);
}
void update2(int p,int l,int r,int nl,int nr,int x) {
    if(l>=nl&&r<=nr) {
        dep[p]=x;
        sum[p]=x*(r-l+1);
        return;
    }
    pushdown(l,r,p);
    if(mid>=nl) update2(ls(p),l,mid,nl,nr,x);
    if(mid+1<=nr) update2(rs(p),mid+1,r,nl,nr,x);
    pushup(p);
}
int query(int p,int l,int r,int nl,int nr) {
    if(l>=nl&&r<=nr) return sum[p];
    pushdown(l,r,p);
    int ret=0;
    if(mid>=nl) ret+=query(ls(p),l,mid,nl,nr);
    if(mid+1<=nr) ret+=query(rs(p),mid+1,r,nl,nr);
    return ret;
}
void solve() {
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,1,n);
    while(q--) {
        int op;
        cin>>op;
        if(op==1) {
            int l,r,x;
            cin>>l>>r>>x;
            update1(1,1,n,l,r,x);
        } else if(op==2) {
            int l,r,x;
            cin>>l>>r>>x;
            update2(1,1,n,l,r,x);
        } else {
            int l,r;
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
}