线段树区间合并——cf1217E

àì夳堔傛蜴生んèń 2023-10-11 09:04 11阅读 0赞

/* 定义：多重集s的元素和是sum，对于sum的第i位为x，如果s里找不到第i位也是x的元素，那么称这个多重集为bad， 现在给定一个 序列a 两种操作 1 i x：将序列第i个元素改为x 2 l r: a[l..r]组成的多重集中，找一个和最小的bad子集，如果没有这样的子集，输出-1 如果集合中有两个数A，B在某一位都不为0，那么这个集合必定为bad，那么在区间[l..r]里找一个最小的bad集合，必定是两个数之和 我们只要找在该区间最小的两个在某一位都不为0的数即可 线段树每个结点开数组Min[10][2]维护a[l..r]里第i位不为0的最小和次小数 */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    #define INF 0x3f3f3f3f3f
    #define ll long long
    ll n,a[N],m;
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    struct Node{ll x[10][2];}t[N<<2];
    ll buf[10];
    void calc(ll x){
        for(int i=0;i<10;i++)
            buf[i]=x%10,x/=10;
    }
    Node merge(Node a,Node b){
        Node res;
        for(int i=0;i<10;i++)
            res.x[i][0]=res.x[i][1]=INF;
        for(int i=0;i<10;i++){
            ll m1=a.x[i][0],m2=b.x[i][0];
            res.x[i][0]=min(m1,m2);
            res.x[i][1]=max(m1,m2);
            res.x[i][1]=min(res.x[i][1],a.x[i][1]);
            res.x[i][1]=min(res.x[i][1],b.x[i][1]);
        }
        return res;
    }
    void build(int l,int r,int rt){
        if(l==r){
            calc(a[l]);
            for(int i=0;i<10;i++){
                if(buf[i])t[rt].x[i][0]=a[l];
                else t[rt].x[i][0]=INF;
                t[rt].x[i][1]=INF;
            }
            return;
        }
        int m=l+r>>1;
        build(lson);build(rson);
        t[rt]=merge(t[rt<<1],t[rt<<1|1]);
    }
    void update(ll pos,ll v,int l,int r,int rt){
        if(l==r){
            calc(v);
            for(int i=0;i<10;i++){
                if(buf[i])t[rt].x[i][0]=v;
                else t[rt].x[i][0]=INF;
                t[rt].x[i][1]=INF;
            }
            return;
        }
        int m=l+r>>1;
        if(pos<=m)update(pos,v,lson);
        else update(pos,v,rson);
        t[rt]=merge(t[rt<<1],t[rt<<1|1]);
    }
    Node query(ll L,ll R,ll l,ll r,ll rt){
        if(L<=l && R>=r)return t[rt];
        int m=l+r>>1;
        Node res;
        for(int i=0;i<10;i++)
            res.x[i][0]=res.x[i][1]=INF;
        if(L<=m)res=merge(res,query(L,R,lson));
        if(R>m)res=merge(res,query(L,R,rson));
        return res;
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        build(1,n,1);
        
        while(m--){
            ll op,l,r;
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op==1)
                update(l,r,1,n,1);
            else {
                Node t=query(l,r,1,n,1);
                ll ans=INF;
                for(int i=0;i<10;i++)
                    ans=min(ans,t.x[i][0]+t.x[i][1]);
                if(ans>=INF)puts("-1");
                else cout<<ans<<'\n';
            }
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11475378.html