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

Gcysnd · 2026-10-22 15:08:44 · 题解

题目要你维护一种数据结构，支持：

• 单点修改 a_x\leftarrow y。
• 将 a_l,a_{l+1},\dots,a_{r-1},a_r 视作硬币面值，让你求最小的无法被这些基础面值拼成的面额。

先不管这些不太聪明的修改和区间查询，我们有个超级弱化版：给你一堆硬币，让你求无法凑出的最小面额。

这个问题的求解很显然了，维护答案变量 ans 表示从 1 到 ans-1 都能凑出来。可以证明 ans 的下界是 1 因为最坏情况下一个硬币不选也可以凑出 0。所以：

• 给 ans 赋一个初值 1 表示现在连 1 都凑不出。
• 不断如下这个过程。去看手里所有的硬币面额 a_1 到 a_n，把 a_i\leq ans 的 a_i 做个累加，得到 \sum_{a_i\leq ans} a_i。分类讨论一下：
  • 如果 sum<ans，就说明把 a_i<ans 的硬币都用上也凑不够，那你 ans 也肯定凑不出了，答案就是 ans。
  • 否则这些硬币能凑出 sum 这个数，答案就被推到了 sum+1，即 ans\leftarrow sum+1。

然后考虑区间查询和单点修改。瓶颈在于快速求出区间 [l,r] 的 \sum_{i\in[l,r],a_i\leq ans} a_i，即区间内不大于 ans 的数的和，还要支持单点修改。

树状数组套树状数组即可，做完了。很轻松，不需要卡常。

搞笑的是我曾经尝试分块套树然后被卡爆了吃了 3 发罚时。

赛时代码，可读性为滚木：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=2e5+5;
const int MV=4e6+5;
int n,q;
int a[MX];
struct Op{
    int t,x,y;
}o[MX];
int vc[MV],vo[MX],vn[MX];
long long fw[MV+MX];
int fo[MX];
void cl(int pos,int val){
    for(int i=pos;i<=n;i+=i&-i){
        vc[vo[i]+vn[i]++]=val;
    }
}
void up(int pos,int val,long long delta){
    for(int i=pos;i<=n;i+=i&-i){
        int p=lower_bound(vc+vo[i],vc+vo[i]+vn[i],val)-(vc+vo[i])+1;
        for(int j=p;j<=vn[i];j+=j&-j){
            fw[fo[i]+j]+=delta;
        }
    }
}
long long qp(int p,long long x){
    long long res=0;
    for(int i=p;i>0;i-=i&-i){
        int idx=upper_bound(vc+vo[i],vc+vo[i]+vn[i],x)-(vc+vo[i]);
        for(int j=idx;j>0;j-=j&-j){
            res+=fw[fo[i]+j];
        }
    }
    return res;
}
long long qr(int l,int r,long long x){
    return qp(r,x)-qp(l-1,x);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >>n >>q;
    for(int i=1;i<=n;++i) cin >>a[i];
    for(int i=0;i<q;++i){
        cin >>o[i].t >>o[i].x >>o[i].y;
    }
    int tc[MX];
    for(int i=1;i<=n;i++) tc[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=j&-j) tc[j]++;
    }
    for(int i=0;i<q;i++){
        if(o[i].t==1){
            int p=o[i].x;
            for(int j=p;j<=n;j+=j&-j) tc[j]++;
        }
    }
    int off=0;
    for(int i=1;i<=n;i++){
        vo[i]=off;
        off+=tc[i];
    }
    for(int i=1;i<=n;i++) vn[i]=0;
    for(int i=1;i<=n;i++) cl(i,a[i]);
    for(int i=0;i<q;i++){
        if(o[i].t==1) cl(o[i].x,o[i].y);
    }
    for(int i=1;i<=n;i++){
        sort(vc+vo[i],vc+vo[i]+vn[i]);
        vn[i]=unique(vc+vo[i],vc+vo[i]+vn[i])-(vc+vo[i]);
    }
    for(int i=1;i<=n;i++) fo[i]=vo[i]+i-1;
    int sz=vo[n]+vn[n]+n;
    for(int i=0;i<sz;i++) fw[i]=0;
    for(int i=1;i<=n;i++) up(i,a[i],a[i]);
    for(int i=0;i<q;i++){
        if(o[i].t==1){
            int p=o[i].x,v=o[i].y;
            if(a[p]!=v){
                up(p,a[p],-a[p]);
                up(p,v,v);
                a[p]=v;
            }
        }else{
            int l=o[i].x,r=o[i].y;
            long long an=1;
            while(1){
                long long s=qr(l,r,an);
                if(s<an){
                    cout <<an <<'\n';
                    break;
                }
                an=s+1;
            }
        }
    }
    return 0;
}