国庆第二天

第二题的代码

// 029 - Long Bricks（★5）
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
  int N;
  vector<int> maxv, setv; // maxv: 区间最大值, setv: 懒惰标记(-1表示无)
  SegTree(int n) : N(n), maxv(4 * n + 2), setv(4 * n + 2, -1) {}

// 下推懒惰标记：将父节点的更新任务传递给子节点
  void pushdown(int o) {
    int lc = 2 * o, rc = 2 * o + 1, &s = setv[o];
    if (s > -1) { // 如果当前节点有“待办”更新
      maxv[lc] = maxv[rc] = setv[lc] = setv[rc] = s; // 执行更新并传递任务
      s = -1; // 清除当前节点的“待办”
    }
  }

// 查询区间 [ql, qr] 的最大值
  int query(int ql, int qr, int o = 1, int L = 1, int R = -1) {
    if (R == -1) R = N;
    if (ql <= L && R <= qr) return maxv[o]; // 区间完全覆盖，直接返回结果
    int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2, ans = 0;
    pushdown(o); // 查询子节点前，先处理懒惰任务
    if (ql <= m) ans = max(ans, query(ql, qr, lc, L, m));
    if (m < qr) ans = max(ans, query(ql, qr, rc, m + 1, R));
    return ans;
  }

// 更新区间 [ql, qr] 的值为 v
  int update(int ql, int qr, int v, int o = 1, int L = 1, int R = -1) {
    if (R == -1) R = N;
    if (ql <= L && R <= qr) { // 区间完全覆盖，打上懒惰标记
      return setv[o] = maxv[o] = v;
    }
    int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2;
    pushdown(o); // 更新子节点前，先处理懒惰任务
    if (ql <= m) update(ql, qr, v, lc, L, m);
    if (m < qr) update(ql, qr, v, rc, m + 1, R);
    return maxv[o] = max(maxv[lc], maxv[rc]); // 用子节点信息更新自己
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int W, N;
  cin >> W >> N;
  SegTree T(W + 1); // 建立覆盖 [1, W] 的线段树
  for (int i = 0, l, r; i < N and cin >> l >> r; i++) {
    int h = T.query(l, r) + 1; // 1. 查询最大高度
    T.update(l, r, h);         // 2. 区间更新为新高度
    cout << h << "\n";
  }
  return 0;
}

第三题

// USACO2023 Dec S, Bovine Acrobatics
#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i < (int)(b); i++)
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, M, K;
  cin >> N >> M >> K;
  struct Cow {
    int w, a;
  };
  vector<Cow> C(N);
  for (Cow &c : C) cin >> c.w >> c.a;
  sort(C.begin(), C.end(),
       [&](const Cow &a, const Cow &b) { return a.w > b.w; });
  long long ans = 0;
  map<int, int, greater<int>> T{{int(2e9), M}};
  for (const Cow &c : C) {  // 从大到小枚举每一种牛
    int a = c.a;            // 这种牛的数量, 从塔顶最大的开始
    for (auto it = begin(T); a > 0 and it != end(T) and it->first - c.w >= K;) {
      // 如果该重量的牛数量为0，或者与当前塔顶不能满足题意要求(后续塔肯定也不满足),就准备操作下一种重量的牛
      int &w = it->second, x = min(w, a);  // 当前塔最多能叠放多少奶牛
      w -= x, a -= x;
      if (w == 0) it = T.erase(it);  // 这个塔顶全部放了牛c，等于被替代了
    }
    // c.a-a个奶牛就会有c.w个塔
    if (a < c.a) T[c.w] += c.a - a, ans += c.a - a;
  }
  cout << ans;
  return 0;
}