前言

一种与众不同的思路，不需要单调栈、分块等巧妙算法。

该题解使用 DeepSeek 润色。

模拟赛忘记 pushdown 挂了 87 分（捆绑）。

一、题意回顾

有 $N$ 个学生，第 $i$ 个学生只能接受大小在 $[A_i, B_i]$ 之间的小组。
接下来 $Q$ 天，每天给出 $M$ 个项目，第 $j$ 个项目恰好需要 $K_j$ 个学生组成小组。
问每天是否存在一种分配方案，使每个项目都得到满足，且每个学生每天最多参加一个项目。

二、贪心策略

我们将一天内的项目按需要人数 $K$ 从小到大处理。
对于当前需要 $K$ 个学生的项目，所有满足 $A_i \le K \le B_i$ 的学生都是“候选者”。为了给后续更大 $K$ 的项目留下更多机会，我们应该优先选择 $B_i$ 尽可能小的学生。

正确性简述：若存在一个可行方案没有选 $B$ 最小的学生，我们可以用 $B$ 更小的学生替换当前所选，不会破坏任何约束（因为被替换者的 $B$ 更大，更灵活）。因此贪心选择 $B$ 最小的 $K$ 个可行学生一定是最优的。

于是问题转化为：维护一个 可用的学生集合，支持：

1. 快速查询 $A \le K$ 且 $B \ge K$ 的学生中 $B$ 最小的 $K$ 个，并把它们从集合中删去；
2. 高效处理每天多个 $K$ 的连续操作。

三、数据结构总览

使用三种数据结构协同工作：

• 主席树：按 $A$ 值将学生插入主席树，键值为 $B$。rt[i] 存储所有 $A \le i$ 的学生的 $B$ 值集合。
• 线段树 1（s, A）：维护“已被完整删除”的学生数量。懒惰标记 A 存储对应的主席树节点指针，实现区间覆盖。
• 线段树 2（d, A2）：维护“部分删除的修正值”，只会在某个 $B$ 值位置产生剩余。支持单点修改与区间清零。
• 时间戳数组（Array 类）：为线段树节点附加时间戳，避免每次询问后全部清空，只需递增时间戳 $T$ 即可。

核心思想：主席树提供原始的二维偏序信息（$A\le K$ 的学生的 $B$ 分布），而两颗动态线段树在主席树的“骨架”上记录删除情况，通过 c[y] - s[k] + d[k] 实时计算某段区间内当前可用的学生数。

四、数据结构详解

4.1 主席树

for (int i = 1; i <= n; i++) {
    rt[i] = rt[i - 1];
    for (int x : e[i]) update(rt[i], 1, n, x);
}

e[i] 存储所有 $A = i$ 的学生的 $B$ 值。
update 在值域 $[1, n]$ 上插入 $B$，形成前缀持久化线段树。查询 rt[K] 即可得到 $A \le K$ 的所有学生的 $B$ 分布。

4.2 惰性清空的线段树数组

struct Array {
    int a[maxn << 2], t[maxn << 2];
    inline int& operator[](int i) {
        if (t[i] < T) { t[i] = T; a[i] = 0; }
        return a[i];
    }
} s, d, A, A2;

全局时间戳 $T$ 每进入一个新询问就自增。访问任意下标时，若该位置时间戳不是当前 $T$，就自动置零并更新戳。这样 4 棵大小为 $4N$ 的线段树可以在 $O(1)$ 的代价下“清零”，非常高效。

4.3 线段树 1 —— 区间覆盖删除

• s[k]：当前节点对应区间内已被完全删除的学生总数。
• A[k]：懒惰标记，若不为 0 则表示该区间被整体赋值为某棵主席树节点的值（即该区间全被删光）。

void add1(int k, int y, int l, int r, int R) {
    if (r <= R) { s[k] = c[y]; A[k] = y; return; }
    pushdown(k);
    ...
}

当我们要把 $[1, p]$ 的所有可用学生全部取走时，直接在主席树 rt[K] 对应的线段树上截取前缀，将 $s$ 节点的值设为 $c[y]$（即原本存在的人数），并打上 $A$ 标记。这样 $c[y] - s[k]$ 就变为 0，表示这些学生已不存在。

4.4 线段树 2 —— 临界修正

• d[k]：修正量。用于在“部分取走”的边界位置存储剩余人数。
• A2[k]：区间清零标记，表示整个区间的 $d$ 值被置 0。

void add2(int k, int l, int r, int p, int v) { ... } // 单点加
void add3(int k, int l, int r, int L, int R) { ... } // 区间清零

当一次操作只用到 $p$ 位置的一部分时，剩余人数记录在 $d[p]$ 中。下一次查询会先消耗这里的剩余。
若某次操作将 $[1, p]$ 全部覆盖（通过 add1），则 $p$ 之前的位置不再需要修正值，此时用 add3 将 $[1, p-1]$ 的 $d$ 清零。

4.5 查询可用人数

int getsum(int k, int y, int l, int r, int R) {
    ...
    return c[y] - s[k] + d[k]; // 真实可用 = 原始 - 完全删除 + 修正
}

这里 $k$ 是动态线段树的节点，$y$ 是主席树对应节点。返回值就是当前区间 $[l, r]$ 内还剩下多少学生。

4.6 寻找第 $K$ 个可用学生

int query(int k, int y, int l, int r, int v, int v2) {
    if (l == r) return l;
    int mid = (l + r) >> 1; pushdown(k); pushdown2(k);
    if (c[ls[y]] - s[lson] + d[lson] >= v + v2)
        return query(lson, ls[y], l, mid, v, v2);
    return query(rson, rs[y], mid + 1, r, v - c[ls[y]] + s[lson] - d[lson], v2);
}

该函数在混合结构（主席树 + 动态线段树）上查找第 $(v + v2)$ 个可用学生的 $B$ 值。
调用时 $v = K_i$（需要的人数），$v2 = \text{无效人数}$（$B < K_i$ 的学生数）。因为 $B < K_i$ 的学生即使可用也无法服务当前项目，必须跳过。两者相加即可定位到需要的边界 $p$。

五、单次询问流程

1. 读入 $M$ 和数组 $K$，若 $\sum K_i > N$ 直接无解。
2. 将 $K$ 从小到大排序。
3. 依次处理每个 $K_i$：
   • 计算无效人数 $v = \text{getsum}(1, rt[K_i], 1, n, K_i-1)$；
   • 若 $c[rt[K_i]] - s[1] + d[1] - v < K_i$，有效人数不足，标记无解；
   • 否则，通过 query 找到位置 $p$；
   • 在 $p$ 处修正 $d$ 值：add2(p, 当前可用总数 - v - K_i)，记录剩余；
   • 将 $[1, p]$ 完全标记删除：add1(1, rt[K_i], 1, n, p)；
   • 清空 $[1, p-1]$ 的旧修正值：add3(1, 1, n, 1, p-1)。
4. 输出是否有解。

六、复杂度分析

• 主席树建树：$\mathcal{O}(N \log N)$。
• 每个询问：$K$ 排序 $\mathcal{O}(M \log M)$，每个 $K_i$ 需要常数次线段树操作，每次 $\mathcal{O}(\log N)$。
• 总复杂度：$\mathcal{O}(N \log N + \sum M \log N + Q)$，在 $N \le 5 \times 10^5$，$\sum M \le 2\times 10^5$ 时非常安全。

七、代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define lson (k << 1)
#define rson (k << 1 | 1)
const int maxn = 5e5 + 10;
int n, m, q, tot, T = 1, k[maxn], rt[maxn], c[maxn << 5], ls[maxn << 5], rs[maxn << 5];
vector<int> e[maxn];
struct Array {
    int a[maxn << 2], t[maxn << 2];
    inline int& operator[](int i) {
        if (t[i] < T) {t[i] = T; a[i] = 0;}
        return a[i];
    }
} s, d, A, A2;
void update(int& k, int l, int r, int p) {
    ++tot; c[tot] = c[k] + 1; ls[tot] = ls[k]; rs[tot] = rs[k]; k = tot;
    if (l == r) return; int mid = (l + r) >> 1;
    if (p <= mid) update(ls[k], l, mid, p);
    else update(rs[k], mid + 1, r, p);
}
void pushdown(int k) {
    if (A[k]) {
        s[lson] = c[ls[A[k]]]; s[rson] = c[rs[A[k]]];
        A[lson] = ls[A[k]]; A[rson] = rs[A[k]];
        A[k] = 0;
    }
}
void pushdown2(int k) {
    if (A2[k]) {
        d[lson] = d[rson] = A2[k] = 0;
        A2[lson] = A2[rson] = 1;
    }
}
void add1(int k, int y, int l, int r, int R) {
    if (r <= R) {s[k] = c[y]; A[k] = y; return;}
    int mid = (l + r) >> 1; pushdown(k);
    add1(lson, ls[y], l, mid, R);
    if (R > mid) add1(rson, rs[y], mid + 1, r, R);
    s[k] = s[lson] + s[rson];
}
void add2(int k, int l, int r, int p, int v) {
    if (l == r) {d[k] = v; return;}
    int mid = (l + r) >> 1; pushdown2(k);
    if (p <= mid) add2(lson, l, mid, p, v);
    else add2(rson, mid + 1, r, p, v);
    d[k] = d[lson] + d[rson];
}
void add3(int k, int l, int r, int L, int R) {
    if (L <= l && r <= R) {d[k] = 0; A2[k] = 1; return;}
    int mid = (l + r) >> 1; pushdown2(k);
    if (L <= mid) add3(lson, l, mid, L, R);
    if (R > mid) add3(rson, mid + 1, r, L, R);
    d[k] = d[lson] + d[rson];
}
int getsum(int k, int y, int l, int r, int R) {
    if (!R) return 0;
    if (r <= R) return c[y] - s[k] + d[k]; pushdown(k); pushdown2(k);
    int mid = (l + r) >> 1, res = getsum(lson, ls[y], l, mid, R);
    if (R > mid) res += getsum(rson, rs[y], mid + 1, r, R);
    return res;
}
int query(int k, int y, int l, int r, int v, int v2) {
    if (l == r) return l;
    int mid = (l + r) >> 1; pushdown(k); pushdown2(k);
    if (c[ls[y]] - s[lson] + d[lson] >= v + v2) return query(lson, ls[y], l, mid, v, v2);
    return query(rson, rs[y], mid + 1, r, v - c[ls[y]] + s[lson] - d[lson], v2);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1, l, r; i <= n; i++)
        cin >> l >> r, e[l].push_back(r);
    for (int i = 1; i <= n; i++) {
        rt[i] = rt[i - 1];
        for (int x : e[i]) update(rt[i], 1, n, x);
    } cin >> q;
    for (; T <= q; T++) {
        cin >> m; int S = 0;
        if (!m) {cout << 1 << '\n'; continue;}
        for (int i = 1; i <= m; i++) cin >> k[i], S += k[i];
        if (S > n) {cout << 0 << '\n'; continue;}
        sort(k + 1, k + m + 1); bool F = true;
        for (int i = 1; i <= m; i++) {
            int v = getsum(1, rt[k[i]], 1, n, k[i] - 1);
            if (c[rt[k[i]]] - s[1] + d[1] - v < k[i]) {F = false; break;}
            int p = query(1, rt[k[i]], 1, n, k[i], v);
            add2(1, 1, n, p, getsum(1, rt[k[i]], 1, n, p) - v - k[i]);
            add1(1, rt[k[i]], 1, n, p);
            if (p > 1) add3(1, 1, n, 1, p - 1);
        } cout << F << '\n';
    } return 0;
}

八、总结

这种“利用树状数据结构在原树上进行修改操作”应用广泛，在非永久性区间操作与前缀继承类树状数据结构的前缀删除操作要求下表现良好，其不局限于可持久化线段树，可持久化平衡树、可持久化并查集等数据结构上均可使用。（需满足操作可差分性质）

我称这种思想为“复制树”，若有其它相关题目，或该思想之前出现过，欢迎评论。