蛋迹挖掘 - 問題

假期到了！你已经厌倦了 C 语言的 shell，所以你决定成为一名贝壳收藏家。

为了度假，你决定前往美丽的岛国 Cartesia。这里以其可爱的方形沙滩而闻名，沙滩由一个 $N \times N$ 的网格组成。你带了一把可靠的铲子，它能够挖出沙滩上一个 $K \times K$ 的方形子网格。你的铲子非常可靠，只能挖出完全位于沙滩内的 $K \times K$ 子网格。

沙滩的某些网格下隐藏着 $M$ 种未被发现的贝壳。具体来说，对于每种 $i$，在 $S_i$ 个网格位置上有第 $i$ 种贝壳，其中 $1 \le S_i \le 4$。对于你挖出并带回家的每一种不同的贝壳，你可以将其以一美元的价格卖给家乡的科学家。同一种类的多个贝壳不会增加额外价值。

更复杂的是，沙滩上有一只顽皮的渡渡鸟在跑来跑去。在某个时刻，它可能会决定在一个网格单元中埋下一枚蛋（包括已经有蛋或贝壳的网格单元）。坏消息是，如果你的铲子挖出的 $K \times K$ 子网格中包含渡渡鸟的蛋，科学家们会因为你伤害了濒危物种而感到恼火，并且不会付给你任何钱。

一切尘埃落定后，你决定坐下来，回到编程中，模拟挖掘过程。你需要计算在不同时间点，随机选择一个合法的挖掘位置时，能够获得至少给定最低利润（以偿还你的学生贷款）的概率。毕竟，谁想在沙滩上铲沙子弄得满身大汗呢？

第一行包含两个整数 $N$ 和 $K$ ($1 \le N \le 2500; 1 \le K \le N$)，分别表示沙滩的大小和铲子的大小。

第二行包含整数 $M$ ($0 \le M \le 10^5$)，表示贝壳的种类数。

接下来的 $M$ 行，每行代表一种贝壳 $i$，包含整数 $S_i$ ($1 \le S_i \le 4$)，随后是 $2 * S_i$ 个整数，表示埋有该种贝壳的 $S_i$ 个网格位置（坐标在 $(1, 1)$ 到 $(N, N)$ 之间）。

下一行包含 $T$ ($1 \le T \le 10\,000$)。接下来的 $T$ 行，每行代表一个特定的时间点（按时间先后顺序），每行具有以下两种形式之一：

$1\ A_i\ B_i$ ($1 \le A_i, B_i \le N$)，表示渡渡鸟刚刚在网格单元 $(A_i, B_i)$ 埋下了一枚蛋；或者
$2\ V_i$ ($1 \le V_i \le 10^9$)，表示我们想要计算在当前时间点，随机挖掘获得利润（美元）$\ge V_i$ 的概率。注意，计算此概率时，实际上不会移除或添加任何贝壳或蛋。

对于本题至少 15% 的分数，$N \le 40$，且所有更新操作都在所有查询操作之前发生。

对于另外 25% 的分数，所有更新操作都在所有查询操作之前发生。

对于每个查询操作，输出一行，表示随机挖掘包含至少所需数量的不同种类贝壳的概率。

你的答案与标准答案的误差必须在 $10^{-4}$ 以内。

4 2
3
3 1 1 2 3 4 2
3 1 4 2 3 3 2
4 2 1 2 4 4 1 4 4
6
2 2
2 3
1 2 3
2 2
2 3
2 4

最初，我们有以下贝壳排列（输入中的第一组贝壳标记为 1，依此类推）：

我们的铲子将挖出一个 $2 \times 2$ 的网格。因此，共有 9 种可能的挖掘方式。

在没有蛋的情况下，9 种挖掘方式中有 8 种包含至少两种贝壳，有 3 种包含三种贝壳。

随后，一枚蛋被放入包含 1 和 2 的单元格中。

此时，9 种挖掘方式中有 4 种包含至少两种贝壳且没有蛋，只有 1 种挖掘方式（左下角的挖掘）包含所有三种贝壳且没有蛋。最终输出表明没有挖掘方式包含 4 种不同的贝壳。

QOJ.ac