CF 1439C Greedy Shopping

题目描述

https://codeforces.com/problemset/problem/1439/C

简要题意：给定一个长度为 $n$ 的非升序列 $a_i$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x,y$，对于所有 $i\in[1,x]$，修改 $a_i=\max(a_i,y)$；第二种操作给定 $x,y$，从左往右访问序列 $a_i$，如果 $a_i\le y$，则 $ans++,y = y-a_i$，求 $ans$

$n,m\le 2\times 10^5$

Solution

注意到修改操作不影响 $a_i$ 序列非升的性质，所以对于修改操作，我们只需要在线段树上二分找到第一个小于 $y$ 的位置，然后相当于做区间覆盖

对于查询操作，注意到 $y$ 每次做一段连续减之后大小至少除以 $2$，所以最多有 $O(\log a_i)$ 段，那么我们每次直接在线段树上二分这个东西即可，但是我们每次二分并不是从 $1$ 开始，可以通过将 $y$ 加上 $\sum_{i=1}^{l-1}a_i$ 然后从 $1$，这样会好写很多

时间复杂度 $O(n\log n\log a_i)$

#include <iostream>
#define maxn 200010
#define ll long long
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll v;
    int t, cov;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].t = T[rc].t;
    T[i].v = T[lc].v + T[rc].v;
}
void build(int i, int l, int r) {
    T[i].cov = -1;
    if (l == r) return T[i].v = T[i].t = a[l], void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}
inline void Update(int i, int l, int r, int v) {
    T[i].v = 1ll * (r - l + 1) * v;
    T[i].t = v; 
    T[i].cov = v; 
}
inline void pushdown(int i, int l, int r) {
    int &cov = T[i].cov, m = l + r >> 1; if (cov == -1) return ;
    Update(lc, l, m, cov); Update(rc, m + 1, r, cov);
    cov = -1;
}
int query(int i, int l, int r, int v) {
    if (T[i].t > v) return 0;
    if (l == r) return l;
    pushdown(i, l, r); int m = l + r >> 1, ls = query(lc, l, m, v);
    if (ls) return ls;
    else return query(rc, m + 1, r, v); 
}
void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, l, r, v);
    int m = l + r >> 1; pushdown(i, l, r);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i);
} 
int query(int i, int l, int r, int L, int R, int &rmx, int &v) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) {
        if (T[i].v <= v) return v -= T[i].v, rmx = r, r - l + 1;
        else if (T[i].t > v) return 0; 
    } pushdown(i, l, r); int m = l + r >> 1, ls = query(lc, l, m, L, R, rmx, v);
    if (rmx == L || rmx == m) return ls + query(rc, m + 1, r, L, R, rmx, v);
    else return ls;
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    int k = query(1, 1, n, y);
    if (1 <= k && k <= x) update(1, 1, n, k, x, y);
}

inline void solve_2() {
    int x, y, ans = 0; cin >> x >> y; 
    while (y && x <= n) { 
        int t = query(1, 1, n, x, n, x, y);
        if (!t) break; ans += t; ++x; 
    } cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    }
    return 0; 
}