Skip to content

1006: 奇妙的卡片

题目

题目描述

桌面上有 $n$ 张卡片。每一张卡片上,都写有 $1$ 到 $m$ 的所有正整数各一次,不过有的数字被写在正面,有的数字被写在反面。

下面给出 $q$ 次询问,每次询问给出 $l$ 和 $r$。你可以自由决定从第 $l$ 张卡片到第 $r$ 张卡片中的每一张卡片的摆放方式(正面朝上或者反面朝上)。我们给定这样一个方法来计算一种摆放方式的得分:对于 $1$ 到 $m$ 的每一个正整数 $x$,如果它出现在第 $l$ 张到第 $r$ 张卡片中任意一张卡片的朝上一面,则能够带来 $x ^ 2$ 的分数。

请最大化每个询问的分数。

输入格式

第一行三个整数 $n, m, q$。

接下来 $n$ 行,每行开头一个 $x_i$ 表示第 $i$ 张卡片正面的数字的总数,紧接着 $x_i$ 个数表示正面的这些数字。

接下来 $q$ 行,每行两个整数 $l, r$。

输出格式

$q$ 行,对于每个询问输出答案。

样例输入

``` 2 5 1 3 4 2 1 2 4 3 1 2

```

样例输出

50

数据范围

对于所有数据,我们保证:

$1 \leq n\times m\leq 10 ^ 6$

$1 \leq q \leq 10 ^ 6$

$0 \leq x_i \leq m$

$1\leq l \leq r \leq n$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!