题解：P17738 [ICPC 2019 Xuzhou R] Yuuki and a problem

__Lavender__ · 2026-10-22 21:17:56 · 题解

考虑将硬币面值 a 按升序插入集合，若当前答案为 ans，进行分类讨论。

• a\leq ans

  本来可以凑出 [1,ans-1]，全部加上 a 之后得到 [a+1,ans+a-1]，两个区间显然相交，得到新的答案 ans+a。

• a> ans

  新区间与原区间不交，当前无贡献，因为按升序加入硬币，以后的 ans 永远凑不出，永远不会有贡献。

于是考虑静态的答案，记录答案 ans 初始为 1，每次加上在区间内小于等于 ans 的所有 a 的和，这份东西的时间复杂度证明见本题严格弱化版 P4587，这里不再赘述。这个可以用主席树维护，有单点修改写树套树就行了。

时间复杂度 \mathcal{O}(n \log^2 n)。

#include<iostream>
#define ll long long 
using namespace std;
const int N=2e5+5;
int n,q,a[N];
int root[N],cnt;
struct node{
    int ls,rs;
    ll sum;
}tree[N*600];
int lowbit(const int& x){return x&(-x);}
void push_up(const int& p){tree[p].sum=tree[tree[p].ls].sum+tree[tree[p].rs].sum;}
void update(const int& p,const int& x,const int& v,const int& l,const int &r){
    if(l==r){
        tree[p].sum+=1LL*x*v;
        return;
    }
    int mid=(l+r>>1);
    if(x<=mid){
        if(tree[p].ls==0)   tree[p].ls=++cnt;
        update(tree[p].ls,x,v,l,mid);
    }
    else{
        if(tree[p].rs==0)   tree[p].rs=++cnt;
        update(tree[p].rs,x,v,mid+1,r);
    }
    push_up(p); 
}
void build(){
    for(int i=1;i<=n;i++){
        int l=i-lowbit(i)+1,r=i;
        root[i]=++cnt;
        for(int x=l;x<=r;x++)   update(root[i],a[x],1,1,2e5);
    }
}
ll query(const int& p,const int& ql,const int& qr,const int& l,const int& r){
    if(!p)  return 0;
    if(ql<=l&&r<=qr)    return tree[p].sum;
    int mid=(l+r>>1);
    ll ret=0;
    if(ql<=mid) ret+=query(tree[p].ls,ql,qr,l,mid);
    if(mid<qr)  ret+=query(tree[p].rs,ql,qr,mid+1,r);
    return ret;
}
void Update(const int& x,const int& v){
    for(int i=x;i<=n;i+=lowbit(i)){
        update(root[i],a[x],-1,1,2e5);
        update(root[i],v,1,1,2e5);
    }
    a[x]=v;
}
ll Query(const int& l,const int& r,const int& vl,const int& vr){
    ll ret=0;
    for(int i=r;i>=1;i-=lowbit(i))  ret+=query(root[i],vl,vr,1,2e5);
    for(int i=l-1;i>=1;i-=lowbit(i))    ret-=query(root[i],vl,vr,1,2e5);
    return ret;
}
ll solve(const int& l,const int& r){
    ll ret=1;
    ll pre=0;
    while(1){
        if(200000<pre+1)    return ret;
        ll tmp=Query(l,r,pre+1,min(ret,200000LL));
        if(tmp==0)  return ret;
        pre=ret;
        ret+=tmp;
    }
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>a[i];
    build();
    while(q--){
        int typ,l,r;
        cin>>typ>>l>>r;
        if(typ==1)  Update(l,r);
        else    cout<<solve(l,r)<<"\n";
    }
    return 0;
}