记录编号	606885	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	6.017 s
提交时间	2025-10-04 16:34:59	内存使用	98.97 MiB

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N = 2e6 + 5;
int n, m, q, a[N], luogu;
ll sum, val[N];
vector<int> v[N];
vector<ll> ans[N];
il int read() {
	int x, f = 1;
	char ch;
	_(!)ch == '-' ? f = -1 : f;
	x = ch ^ 48;
	_()x = (x << 1) + (x << 3) + (ch ^ 48);
	return f * x;
}
int main() {
	n = read();
	m = read();
	q = read();
	luogu = log2(m) + 1;
	for (int i = 1; i <= m; i++)sum += 1ll * i * i;
	for (int i = 1; i <= n; i++) {
		v[i].resize(m + 2);
		int x = read();
		for (int j = 1; j <= x; j++)v[i][read()] = 1;
	}

	for (int l = 1; l <= n; l++) {
		ans[l].resize(luogu + 1);
		for (int i = 1; i <= m; i++) a[i] = 0;
		for (int r = l; r <= min(n, l + luogu); r++) {
			for (int i = 1; i <= m; i++) a[i] = (a[i] << 1) | v[r][i], val[a[i]] += 1ll * i * i;
			ll res = sum;
			for (int i = 0; i < (1 << (r - l + 1)); i++) res = min(res, val[i]), val[i] = 0;
			ans[l][r - l] = sum - res;
		}
	}
	while (q--) {
		int l = read(), r = read();
		if (r - l + 1 > luogu)printf("%lld\n", sum);
		else printf("%lld\n", ans[l][r - l]);
	}
	return 0;
}