#P5476. [CCO2015] 挖掘

[CCO2015] 挖掘

题目描述

本题译自 CCO 2015 Day2 T3「Eggscavation

度假时间到了!你厌倦了 C shell(编程语言),所以你决定去收集贝壳(Seashell,与 C Shell 同音)。

你决定去游览 Cartesia 国的岛度假。该岛以拥有优美的方形沙滩而著名。该沙滩被划分成 N×NN\times N 的矩阵组成,你带上了你可靠的铲子,你可以用铲子在岛上挖最多 K×KK\times K的正方形子矩阵。为了保证你的铲子是可靠的,你所挖的正方形子矩阵要保证所挖的 K×KK\times K 的范围都在沙滩上。

在岛下,有 MM 种未探索过的贝壳种类。具体来说,对于每个贝壳种类 ii,有 SiS_i 个贝壳在不同的位置。对于每个不同的种类的贝壳,你把它挖出来,然后带回家,然后以每个 11 美元的价格卖给一个科学家。多个同种类的贝壳没有附加价值。

麻烦的是,一种华丽的渡渡鸟在沙滩上跑来跑去。在一个给定时刻,他可能会在一个网格里埋一个蛋,包括那些已经有蛋或者网格的网格。坏消息是,如果你铲子挖出来的 K×KK\times K 的子正方形矩阵里包含渡渡鸟的蛋,科学家会因为你正在危害濒危物种而非常着急,因此没人会给你钱。

想到这些,你决定坐下来,开始写程序,进行模拟挖掘。你将会去计算你的挖掘的可能性,当你在不同时间点以均等可能性选择一个挖掘方案时,需要保证至少一个收入值来偿还你的学生贷款。谁想白忙活一场呢?

输入格式

第一行包括两个整数 N,KN,K,表示岛和铲子的尺寸

第二行一个数 MM,表示贝壳种类数。接下来 MM 行每行表示一个种类 ii,包含一个整数 SiS_i,接着 2×Si2\times S_i 个数,为一些在 (1,1)(1,1)(N,M)(N,M) 之间的坐标,表示 SiS_i 个贝壳埋的位置。

接下来 TT 行每行表示一个时间点,按时间由最远到最近排序,每行为如下格式之一:

  • 11 AiA_i BiB_i,表示渡渡鸟在 (Ai,Bi)(A_i,B_i) 下了一个蛋
  • 22 ViV_i,表示我们想计算一个在该时间点获利 Vi\geq V_i 的随机挖掘的可能性。注意贝壳和蛋在计算时都没有没有被真正地挖出来。

输出格式

对于每个询问,输出一行表示一次获得至少指定利润的随机挖掘的可能性。你的答案与标准答案之间的差值的绝对值不能大于 10410^{-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
0.88889
0.33333
0.44444
0.11111
0.00000

提示

【样例解释】

初始时,贝壳的排布如下所示:

CCO2015D2T3Pic1

我们将用铲子挖至多 2×22\times 2 的格子,因此我们有 99 种可能的挖掘。 当没有蛋出现时,88 种挖掘包含至少两种贝壳,33 种挖掘包含三种贝壳。

一个蛋掉进了有贝壳 1,21,2 的方格。

在这种情况下,49\frac{4}{9} 的挖掘包含至少两种贝壳且没有蛋,仅有一种挖掘会包含所有种类的贝壳并且没有蛋,那就是挖掘左下角。最终输出指明没有任何一种挖掘包含四种贝壳。

【数据范围】

对于至少 15%15\% 的数据,1N401\le N \le 40

对于另外 25%25\% 的数据,所有的更新操作在询问操作前出现;

对于 100%100\% 的数据,1KN2500,1\le K \le N\le 2500, 0M105,0\le M \le 10^5, 1Si4,1\le S_i\le 4, 0T10000,0\le T\le 10000, 1Ai,BiN,1\le A_i,B_i \le N, 1Vi1091\le V_i\le 10^9