题目大意

有一个 $N \times N$ 的沙滩，可以挖 $K \times K$ 的子矩阵。有 $M$ 种贝壳，每种贝壳分布在若干位置。渡渡鸟会在某些格子下蛋。如果挖到蛋，则收益为 $0$。每次询问：随机挖一个 $K \times K$ 子矩阵，收益严格大于 $V$ 的概率。

算法思路

核心思想

二维差分 + 并查集维护被蛋破坏的区域 + 容斥原理。

关键步骤

1. 贝壳覆盖统计

对每种贝壳的 $S_i$ 个位置（$S_i \le 4$），用容斥原理计算包含该种类所有贝壳的 $K \times K$ 子矩阵数量

使用二维差分数组快速标记覆盖情况

2. 蛋的影响处理

每个蛋会破坏包含它的所有 $K \times K$ 子矩阵

用并查集维护每行中被蛋破坏的连续区间

快速查询未被破坏的子矩阵数量

3. 概率计算

总子矩阵数：$(N-K+1)^2$

对每个收益值 $v$，统计包含至少 $v+1$ 种贝壳且无蛋的子矩阵数

概率 = 有效子矩阵数 / 总子矩阵数

算法流程

预处理贝壳覆盖

对每种贝壳的所有位置子集进行容斥

计算该子集对应的最小覆盖矩形

用二维差分标记覆盖情况

处理操作序列

下蛋操作：更新并查集，标记被破坏的子矩阵

查询操作：用树状数组统计满足收益要求的子矩阵数

输出答案

计算概率并输出，精度要求 $10^{-4}$

复杂度分析

预处理：$O(M \cdot 2^4 + N^2)$，容斥 + 二维前缀和

查询处理：$O(T \cdot N \log N)$，并查集 + 树状数组操作

空间复杂度：$O(N^2)$

总结

本题是组合计数 + 数据结构维护的复杂问题：

容斥原理：处理多种贝壳的覆盖统计

二维差分：高效标记矩形区域

并查集优化：维护被蛋破坏的区间，避免重复计算

概率计算：结合组合计数和实时更新

该解法通过巧妙的数据结构组合，在 $N \le 2500, T \le 10000$ 的规模下高效处理动态查询，体现了解决复杂计数问题的综合能力。