CF1217E Sum Queries?

@Pelom  September 26, 2019

题意

记$sum$为一个多重集的所有元素的和
对于$sum$的每一个数位,如果多重集中至少存在一个元素的同一数位与$sum$的此数位相同,我们称这个多重集是平衡的,否则称它是不平衡的
给出一个数组,有两种操作

  • 单点修改
  • 询问一个区间中所有不平衡的多重集的$sum$中的最小值

数据范围:$1 \le n,m \le 2 \cdot 10^5,1 \le a_i \le 10^9$

题解

首先通过给出的样例猜想:$sum$的每一位上只能对应有$1$个非$0$的数字
容易证明:若同一位上存在$2$个及以上非$0$数字,想要使$sum$中的对应位与其中一个相等,肯定需要进位;而进位后下一位又与$sum$中它的对应位不等,再次需要进位;以此类推,总位数一定会超过$sum$的总位数,矛盾
反之,若一个多重集是不平衡的,那它一定有某一位上存在$2$个及以上非$0$的数字;作为这个多重集的子集,我们只需要考虑该位上最小的$2$个元素的和;而对于其它数位,以同样的方式记录该值,最后的答案即为区间的最小值

inline void init(int v){
    int t=v;
    for(int i=1;i<L && t;i++,t/=10)
        if(t%10!=0)
            mi[i]=Min(mi[i],v);
}

因为取$min$满足区间和性质,可以用线段树维护;具体方法是:线段树的节点维护该区间的答案与该区间的每个数位上非$0$的数的最小值,合并区间时用同一位的最小值的和去更新区间的答案
注意回答询问的时候也需要合并答案,可以将区间合并重载为$+$,方便使用

inline node operator + (const node& x){
    node res;
    res.w=Min(w,x.w);
    for(int i=1;i<L;i++){
        res.mi[i]=Min(mi[i],x.mi[i]);
        if(mi[i]<INF && x.mi[i]<INF)
            res.w=Min(res.w,mi[i]+x.mi[i]);
    }
    return res;
}

代码:

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int N=2e5+10;
const int L=10;
const int INF=2e9;
int n,m,op,x,y;
int a[N];
template <typename T>
inline T Min(T a,T b){
    return a<b?a:b;
}
struct node{
    int w,mi[L];
    inline node(){
        w=INF;
        for(int i=1;i<L;i++)
            mi[i]=INF;
    }
    inline void init(int v){
        int t=v;
        for(int i=1;i<L && t;i++,t/=10)
            if(t%10!=0)
                mi[i]=Min(mi[i],v);
    }
    inline node operator + (const node& x){
        node res;
        res.w=Min(w,x.w);
        for(int i=1;i<L;i++){
            res.mi[i]=Min(mi[i],x.mi[i]);
            if(mi[i]<INF && x.mi[i]<INF)
                res.w=Min(res.w,mi[i]+x.mi[i]);
        }
        return res;
    }
} T[N<<2];
inline void pushUp(int rt){
    T[rt]=T[ls]+T[rs];
}
void build(int rt,int l,int r){
    if(l==r){
        T[rt].init(a[l]);
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushUp(rt);
}
void update(int rt,int l,int r,int p,int k){
    if(l==r){
        T[rt]=node();
        T[rt].init(k);
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid)
        update(ls,l,mid,p,k);
    else update(rs,mid+1,r,p,k);
    pushUp(rt);
}
node query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R){
        return T[rt];
    }
    node res;
    int mid=l+r>>1;
    if(L<=mid)
        res=res+query(ls,l,mid,L,R);
    if(R>mid)
        res=res+query(rs,mid+1,r,L,R);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(;m--;){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
            update(1,1,n,x,y);
        else{
            int t=query(1,1,n,x,y).w;
            printf("%d\n",t<INF?t:-1);
        }
    }
    return 0;
}

添加新评论