#2223. 0418 t3

    ID: 2223 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1727来源:qoj.ac数据:公开样例线段树并查集

0418 t3

0418 t3

题目描述

时间限制:1s 空间限制:512MB 题面描述 度假时间到了!你厌倦了 C shell(编程语言),所以你决定去收集贝壳(Seashell,与 C Shell 同音)。 你决定去游览 Cartesia 国的岛度假。该岛以拥有优美的方形沙滩而著名。该沙滩被划分成 的矩 阵组成,你带上了你可靠的铲子,你可以用铲子在岛上挖最多 的正方形子矩阵。为了保证你的 铲子是可靠的,你所挖的正方形子矩阵要保证所挖的 的范围都在沙滩上。 在岛下,有 种未探索过的贝壳种类。具体来说,对于每个贝壳种类 ,有 个贝壳在不同的位置。 对于每个不同的种类的贝壳,你把它挖出来,然后带回家,然后以每个 美元的价格卖给一个科学家。 多个同种类的贝壳没有附加价值。 麻烦的是,一种华丽的渡渡鸟在沙滩上跑来跑去。在一个给定时刻,他可能会在一个网格里埋一个蛋, 包括那些已经有蛋或者网格的网格。坏消息是,如果你铲子挖出来的 的子正方形矩阵里包含渡 渡鸟的蛋,科学家会因为你正在危害濒危物种而非常着急,因此没人会给你钱。 想到这些,你决定坐下来,开始写程序,进行模拟挖掘。你将会去计算你的挖掘的可能性,当你在不同 时间点以均等可能性选择一个挖掘方案时,需要保证至少一个收入值来偿还你的学生贷款。谁想白忙活 一场呢? 输入格式 第一行包括两个整数 ,表示岛和铲子的尺寸 第二行一个数 ,表示贝壳种类数。接下来 行每行表示一个种类 ,包含一个整数 ,接着 个数,为一些在 与 之间的坐标,表示 个贝壳埋的位置。 接下来 行每行表示一个时间点,按时间由最远到最近排序,每行为如下格式之一: ,表示渡渡鸟在 下了一个蛋 ,表示我们想计算一个在该时间点获利 的随机挖掘的可能性。注意贝壳和蛋在计算时都没 有没有被真正地挖出来。 输出格式 对于每个询问,输出一行表示一次获得至少指定利润的随机挖掘的可能性。你的答案与标准答案之间的 差值的绝对值不能大于 。 样例1输入 1 4 2 2 3 3 3 1 1 2 3 4 2 4 3 1 4 2 3 3 2 5 4 2 1 2 4 4 1 4 4 6 6 7 2 2 8 2 3 9 1 2 3 10 2 2 11 2 3 12 2 4 样例1输出 1 0.88889 2 0.33333 3 0.44444 4 0.11111 5 0.00000 样例1解释 初始时,贝壳的排布如下所示: 我们将用铲子挖至多 的格子,因此我们有 种可能的挖掘。 当没有蛋出现时, 种挖掘包含至少两种贝壳, 种挖掘包含三种贝壳。 一个蛋掉进了有贝壳 的方格。 的挖掘包含至少两种贝壳且没有蛋,仅有一种挖掘会包含所有种类的贝壳并且没有 在这种情况下, 蛋,那就是挖掘左下角。最终输出指明没有任何一种挖掘包含四种贝壳。 数据范围和提示 对于 的数据, ; 对于另外 的数据,所有的更新操作在询问操作前出现; 对于 的数据, 。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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