cf1440 Greedy Shopping

传送门
操作：

• 区间([1, x])进行修改，把(a_i = max(a_i, y))
• 区间查询，求最大的(r)，满足(sum(x,r) leq y)

维护一下区间最大值和区间最小值，考虑到如果说某个区间的最大值(leq y),那么就变成了区间覆盖了，把区间的值都变成(y)。
如果说区间最小值都大于(y),那么这个区间就不需要进行更新。
对于操作2，就是线段树的定义吧，先访问左边，再访问右边，他肯定是从左边的一段区间进行查询，再查询右边的，所以直接在query那里用应用就行了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int a[N];
struct SegTree{
    struct Node{
        int l, r; ll sum, mx, mi, lazy;
        #define l(p) tree[p].l
        #define r(p) tree[p].r
        #define sum(p) tree[p].sum
        #define lazy(p) tree[p].lazy
        #define mx(p) tree[p].mx
        #define mi(p) tree[p].mi
        #define lson (p << 1)
        #define rson (p << 1 | 1)
    } tree[N << 2];
    void pushup(int p){
        sum(p) = sum(lson) + sum(rson);
        mi(p) = min(mi(lson), mi(rson));
        mx(p) = max(mx(lson), mx(rson));
    }
    void addtag(int p, int d){
        sum(p) = 1ll * (r(p) - l(p) + 1) * d;
        lazy(p) = mx(p) = mi(p) = d;
    }
    void pushdown(int p){
        if(lazy(p) != -1) addtag(lson, lazy(p)), addtag(rson, lazy(p)), lazy(p) = -1;
    }
    void build(int p, int l, int r){
        l(p) = l, r(p) = r, sum(p) = mx(p) = mi(p) = 0; lazy(p) = -1;
        if(l == r) {
            mi(p) = mx(p) = sum(p) = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
        pushup(p);
    }
    void change(int p, int l, int r, int y){ // [l, r]区间修改为y
        if(l <= l(p) && r(p) <= r) {
            if(mi(p) >= y) return; // 无需更新
            if(mx(p) < y) {addtag(p, y); return;} // 这段区间都更新为最大值
            if(l(p) == r(p)) return;
        }
        pushdown(p);
        int mid = (l(p) + r(p)) >> 1;
        if(l <= mid) change(lson, l, r, y);
        if(r > mid) change(rson, l, r, y);
        pushup(p);
    }
    ll query(int p, int l, int r,  int &x) {
        if(l <= l(p) && r(p) <= r) {
            if(mi(p) > x) return 0;
            if(x >= sum(p)) {x -= sum(p); return r(p) - l(p) + 1;}
            if(l(p) == r(p)) return 0;
        }
        pushdown(p);
        int mid = (l(p) + r(p)) >> 1; ll ans = 0;
        if(l <= mid) ans += query(lson, l, r, x);
        if(r > mid) ans += query(rson, l, r, x);
        return ans;
    }
} seg;
int n, m;
void task1(){
    int x, y; scanf("%d%d", &x, &y);
    seg.change(1, 1, x, y);
}
void task2(){
    int x, y; scanf("%d%d", &x, &y);
    printf("%lld
", seg.query(1, x, n, y));
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    seg.build(1, 1, n);
    for(int i = 1; i <= m; i++) {
        int op; scanf("%d", &op);
        if(op == 1) task1();
        if(op == 2) task2();
    }
    return 0;
}