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

shuqiang · 2026-10-22 20:41:30 · 题解

算法 1

我会暴力！

考虑若当前硬币集合可以表示 1 \sim x，那么若加入 y 满足 y \le x+1，那么使用 y 可以表示 1+y \sim x+y，不使用 y 可以表示 1 \sim x，取交集后变为 1 \sim x+y，于是考虑从小到大排序区间内的数字，一个一个扫，当扫到 y \le x+1，令 x \leftarrow x+y，否则输出 x+1。

时间复杂度 \mathcal{O}(nq \log n)，无法通过。

:::success[参考代码]

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
int n, q, a[N], b[N], op, l, r;
ll ans;

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    while(q--){
        cin >> op >> l >> r;
        if(op == 1){
            a[l] = r;
        }
        else{
            for(int i = 1; i <= n; i++) b[i] = a[i];
            sort(b + l, b + r + 1);
            ans = 0;
            for(int i = l; i <= r; i++){
                if(ans+1 >= b[i]) ans += b[i];
                else break;
            }
            cout << ans+1 << '\n';
        }
    }
    return 0;
}

:::

算法 2

我会分块！请注意，这个方法不能通过这题，不建议学习。

看到 a_i,y \le 2 \times 10^5，想到分块。

先仅考虑数字 a_i \le B，可以建 B 个树状数组，第 i 个树状数组存前 j 个数字中有多少个 i，然后就可以暴力扫，这部分复杂度为 \mathcal{O}(B \log n)。

考虑 a_i > B，此时可以发现若 x \ge \max_{i=l}^ra_i，答案就是 \sum_{i=l}^r a_i+1，因为所有硬币都可以使用，于是可以建堆，初始堆仅有 [l,r]，这里令 b_i 为：

b_i= \begin{cases} \infty & a_i \le B\\ a_i & a_i > B \end{cases}

然后取出其中 \min_{i=l}^rb_i 最小的堆，设该位置为 p，然后判断这个硬币，并如果存在则加入 [l,p-1]，[p+1,r]，这样，最多判断 \frac{V}{B} 即可达到 \max_{i=l}^ra_i \le V 的上界，并且每次最多有 \max_{i=l}^ra_i \le V 个区间。这部分复杂度为 \mathcal{O}(\frac{V}{B} \log \frac{V}{B} \log n)。

最终时间复杂度为 \mathcal{O}(n+qB \log n+ q\frac{V}{B} \log \frac{V}{B} + q\frac{V}{B} \log n)，无法通过。

:::success[参考代码]

#include<iostream>
#include<cmath>
#include<queue>

using namespace std;
typedef long long ll;

const int N = 2e5 + 10, M = 460, B = 450, inf = 1e9+1;
int n, q, a[N], op, x, y;
ll ans = 0;

struct piii{
    int l, r, mn;

    bool operator < (const piii & o) const{
        return a[mn] > a[o.mn];
    }
};
priority_queue<piii> pq;

struct Tree1{
    int t[N];

    void upd(int x, int v){
        while(x <= n){
            t[x] += v;
            x += x & -x;
        }
    }

    int qry(int x){
        int res = 0;
        while(x){
            res += t[x];
            x -= x & -x;
        }
        return res;
    }

} c[M];

struct Tree2{
    int mx[N*4], mn[N*4], L, R; ll s[N*4];

    inline void mg(int & u){
        mx[u] = max(mx[u*2], mx[u*2+1]);
        s[u] = s[u*2] + s[u*2+1];
        if(a[mn[u*2]] <= a[mn[u*2+1]]){
            mn[u] = mn[u*2];
        }
        else{
            mn[u] = mn[u*2+1];
        }
    }

    inline void setnd(int & u, int & i){
        mx[u] = s[u] = a[i];
        if(a[i] <= B) mn[u] = n+1;
        else mn[u] = i;
    }

    void build(int u, int l, int r){
        if(l == r){
            setnd(u, l);
            return;
        }
        int mid = (l + r) / 2;
        build(u*2, l, mid);
        build(u*2+1, mid+1, r);
        mg(u);
    }

    void update(int u, int l, int r){
        if(l == r){
            setnd(u, l);
            return;
        }
        int mid = (l + r) / 2;
        if(L <= mid) update(u*2, l, mid);
        else update(u*2+1, mid+1, r);
        mg(u);
    }

    int query1(int u, int l, int r){
        if(L <= l && r <= R) return mx[u];
        int mid = (l + r) / 2, res = 0;
        if(L <= mid) res = max(res, query1(u*2, l, mid));
        if(mid < R) res = max(res, query1(u*2+1, mid+1, r));
        return res;
    }

    int query2(int u, int l, int r){
        if(L <= l && r <= R) return mn[u];
        int mid = (l + r) / 2, res = n+1;
        if(L <= mid){
            int mnp = query2(u*2, l, mid);
            if(a[mnp] <= a[res]) swap(mnp, res);
        }
        if(mid < R){
            int mnp = query2(u*2+1, mid+1, r);
            if(a[mnp] <= a[res]) swap(mnp, res);
        }
        return res;
    }

    ll query3(int u, int l, int r){
        if(L <= l && r <= R) return s[u];
        int mid = (l + r) / 2; ll res = 0;
        if(L <= mid) res += query3(u*2, l, mid);
        if(mid < R) res += query3(u*2+1, mid+1, r);
        return res;
    }

    inline void upd(int p){
        L = p;
        update(1, 1, n);
    }

    inline int qry1(int p1, int p2){
        L = p1; R = p2;
        return query1(1, 1, n);
    }

    inline int qry2(int p1, int p2){
        L = p1; R = p2;
        return query2(1, 1, n);
    }

    inline ll qry3(int p1, int p2){
        L = p1; R = p2;
        return query3(1, 1, n);
    }
} d;

inline void delnum(int i){
    if(a[i] <= B) c[a[i]].upd(i, -1);
}

inline void addnum(int i){
    if(a[i] <= B) c[a[i]].upd(i, 1);
}

void add_ls(int l, int r){
    if(l > r) return;
    int res = d.qry2(l, r);
    if(a[res] == inf) return;
    pq.push({l, r, res});
}

ll qry(int l, int r){
    ll s = 0; int mx = d.qry1(l, r); bool fg = 0;
    for(int i = 1; i <= B; i++){
        if(s+1 < i) return s+1;
        s += ((ll)c[i].qry(r) - c[i].qry(l-1))*i;
        if(s >= mx) return d.qry3(l, r)+1;
    }
    while(pq.size()) pq.pop();
    add_ls(l, r);
    while(pq.size()){
        piii tp = pq.top();
        pq.pop();
        if(s+1 < a[tp.mn]) return s+1;
        s += a[tp.mn];
        if(s >= mx) return d.qry3(l, r)+1;
        add_ls(tp.l, tp.mn-1);
        add_ls(tp.mn+1, tp.r);
    }
    return s+1;
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        addnum(i);
    }
    a[n+1] = inf;
    d.build(1, 1, n);
    while(q--){
        cin >> op >> x >> y;
        if(op == 1){
            delnum(x);
            a[x] = y;
            addnum(x);
            d.upd(x);
        }
        else{
            cout << qry(x, y) << '\n';
        }
    }
    return 0;
}

:::

不知名优化

观察到测试点只有 2 个，说明数据很水，如果数据随机，那么大概率处理 a_i \le B 的部分即可通过，实测过了。

算法 3

我会正解！

观察到如果 a_i 不重复，x 是可以增长得很快的，考虑一次性处理多个一定可以使用的 a_i。

先考虑序列 1,2,3，初始 x=0。

此时 2,3 均满足 x+1 \ge y，于是都可以加入。

然后扩展一下可以发现，我们可以将所有的 a_i 按照以下方式分组：

[2^0,2^1-1],[2^1,2^2-1],[2^2,2^3-1],\cdots,[2^{\lfloor \log n \rfloor },2^{\lfloor \log n \rfloor+1}-1]

也就是

[1,1],[2,3],[4,7],\cdots

然后对于每一组分别建一棵可以区间查最小值和求区间和的线段树，然后扫一遍所有线段树。

设查得的最小值为 m，和为 s。
若 x+1 \ge m，令 x \leftarrow x+s
若 x+1 < m 且区间内的值不是空的，结束并输出 x+1。

为什么这个是对的呢？

设当前的线段树为 b：

当 b=0 时，1+x=1 \ge 1

时间复杂度为 \mathcal{O}(n+q \log n \log V)，可以通过。

:::success[参考代码]

#include<iostream>
#include<cmath>
#include<queue>

using namespace std;
typedef long long ll;

const int N = 2e5 + 10, M = 20, B = 17, V = (1 << 18) + 10, inf = 1e9+1;
int n, q, a[N], g[V], op, x, y;
ll ans = 0;

struct Tree{
    int mn[N*4], L, R, id; ll s[N*4];

    inline void setnd(int & u, int & i){
        if(g[a[i]] == id) mn[u] = s[u] = a[i];
        else mn[u] = inf, s[u] = 0;
    }

    inline void mg(int & u){
        s[u] = s[u*2] + s[u*2+1];
        mn[u] = min(mn[u*2], mn[u*2+1]);
    }

    void build(int u, int l, int r){
        if(l == r){
            setnd(u, l);
            return;
        }
        int mid = (l + r) / 2;
        build(u*2, l, mid);
        build(u*2+1, mid+1, r);
        mg(u);
    }

    void update(int u, int l, int r){
        if(l == r){
            setnd(u, l);
            return;
        }
        int mid = (l + r) / 2;
        if(L <= mid) update(u*2, l, mid);
        else update(u*2+1, mid+1, r);
        mg(u);
    }

    int query1(int u, int l, int r){
        if(L <= l && r <= R) return mn[u];
        int mid = (l + r) / 2, res = inf;
        if(L <= mid) res = min(res, query1(u*2, l, mid));
        if(mid < R) res = min(res, query1(u*2+1, mid+1, r));
        return res;
    }

    ll query2(int u, int l, int r){
        if(L <= l && r <= R) return s[u];
        int mid = (l + r) / 2; ll res = 0;
        if(L <= mid) res += query2(u*2, l, mid);
        if(mid < R) res += query2(u*2+1, mid+1, r);
        return res;
    }

    inline void upd(int p){
        L = p;
        update(1, 1, n);
    }

    inline int qry1(int p1, int p2){
        L = p1; R = p2;
        return query1(1, 1, n);
    }

    inline ll qry2(int p1, int p2){
        L = p1; R = p2;
        return query2(1, 1, n);
    }
} t[M];

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i <= B; i++){
        for(int j = (1 << i); j < (1 << (i+1)); j++) g[j] = i;
    }
    for(int i = 0; i <= B; i++){
        t[i].id = i; t[i].build(1, 1, n);
    }
    while(q--){
        cin >> op >> x >> y;
        if(op == 1){
            swap(a[x], y);
            t[g[y]].upd(x);
            t[g[a[x]]].upd(x);
        }
        else{
            ll s = 0;
            for(int i = 0; i <= B; i++){
                if(s+1 < t[i].qry1(x, y)) break;
                s += t[i].qry2(x, y);
            }
            cout << s+1 << '\n';
        }
    }
    return 0;
}

:::