题解

问题分析

我们需要在每次成员数量变化后，判断是否存在一种方案，将成员分配到其可接受的冰鞋尺寸中，且：

• 每个成员分配到恰好一双冰鞋
• 每个冰鞋尺寸 $i$ 最多使用 $k$ 次
• 脚型为 $r$ 的成员只能选择尺寸 $[r, r+d]$ 的冰鞋

关键思路：Hall 定理

将问题建模为二分图匹配：

• 左部：所有成员（按脚型分组）
• 右部：冰鞋尺寸 $1 \dots n$
• 边：脚型 $r$ 的成员连接尺寸 $r \dots r+d$

根据 Hall 定理，存在完美匹配当且仅当：对于任意右部子集 $S$，其邻居集合的大小 $\ge |S|$。

在我们的问题中，右部的任意区间 $[L,R]$ 的邻居是脚型满足 $[r, r+d] \cap [L,R] \neq \emptyset$ 的所有成员。

条件转化

经过推导（具体过程略），Hall 条件等价于： 对于所有 $1 \le i \le n$，有：

其中 $\text{count}[j]$ 表示脚型为 $j$ 的成员数量。

解释：对于尺寸 $i$，能穿这个尺寸的成员来自脚型 $[i-d, i]$（因为脚型 $j$ 可接受 $[j, j+d]$，所以要 $j \le i$ 且 $j+d \ge i$，即 $j \ge i-d$）。

算法步骤

1. 维护数组 $\text{count}[1 \dots n]$，初始全 0
2. 对于每个事件 $(r, x)$：
   • 更新 $\text{count}[r] += x$
   • 检查对于所有 $i = r \dots r+d$（且 $i \le n$），是否满足：$$\sum_{j=\max(1, i-d)}^{i} \text{count}[j] \le k$$
   • 如果所有检查都通过，输出 TAK，否则输出 NIE

数据结构优化

直接计算区间和会超时，使用 Fenwick 树 或 线段树：

• 维护前缀和数组
• 支持单点更新
• 支持区间和查询
• 每次事件后，只需要检查 $i = r \dots r+d$ 这些位置的条件

复杂度分析

• 每次事件：更新 $O(\log n)$，检查 $d+1$ 个位置，每个检查 $O(\log n)$
• 总复杂度：$O(m \cdot d \cdot \log n)$

注意：当 $d$ 很大时可能超时，可以进一步优化：

• 维护每个位置 $i$ 的当前区间和值
• 只维护全局最大值，利用单调性减少检查次数
• 最优实现可达 $O(m \log n)$

样例验证

对于样例：$n=4, m=4, k=2, d=1$

1. $(1,3)$: count[1]=3，检查 $i=1,2$ 都满足条件 → TAK
2. $(2,3)$: count[2]=3，检查 $i=2,3$ 都满足条件 → TAK
3. $(3,3)$: count[3]=3，检查 $i=3,4$，发现 $i=3$ 时 sum=3+3=6>4 → NIE
4. $(2,-1)$: count[2]=2，检查 $i=2,3$ 都满足条件 → TAK

总结

本题核心是将冰鞋分配问题转化为二分图匹配，利用 Hall 定理得到简洁的判定条件，再通过数据结构高效维护动态更新。