记录编号	606928	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	7.264 s
提交时间	2025-10-04 17:25:46	内存使用	53.65 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

int n;
int m;
int q;
vector<int> nums[N];
int log2m;
long long res;
vector<long long> ress[N];
int con[N];
long long sum[N];

int main () {
	
	freopen ("magic.in", "r", stdin);
	freopen ("magic.out", "w", stdout);

	// in >> n >> m >> q;
	scanf ("%d%d%d", &n, &m, &q);
	int len;
	int num;
	for (int i = 1; i <= n; i++) {
		nums[i].resize(m + 2);
		// in >> len;
		scanf ("%d", &len);
		for (int j = 1; j <= len; j++) {
			// in >> num;
			scanf ("%d", &num);
			nums[i][num] = 1;
		}
	}

	log2m = ceil (log2 (m));
	for (int i = 1; i <= m; i++) {
		res += 1ll * i * i;
	}

	for (int l = 1; l <= n; l++) {
		for (int i = 1; i <= m; i++) {
			con[i] = 0;
		}
		ress[l].resize(log2m + 2);
		for (int r = l; r <= min (l + log2m, n); r++) {
			for (int i = 1; i <= m; i++) {
				con[i] = (con[i] << 1) | nums[r][i];
				sum[con[i]] += 1ll * i * i;
			}
			long long tres = res;
			for (int i = 0; i < (1 << (r - l + 1)); i++) {
				tres = min (tres, sum[i]);
				sum[i] = 0;
			}
			ress[l][r - l] = res - tres;
		}
	}

	int l, r;
	while (q--) {
		// in >> l >> r;
		scanf ("%d%d", &l, &r);
		if (r - l + 1 > log2m) {
			// cout << res << endl;
			printf ("%lld\n", res);
		}
		else {
			// cout << res - ress[l][r - l] << endl;
			printf ("%lld\n", ress[l][r - l]);
		}
	}
	
	return 0;
}