记录编号	607020	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	6.539 s
提交时间	2025-10-04 21:15:39	内存使用	7.56 MiB

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 10;

int n, m, q;
ll T_all, sq[MAXN], L;
int pat[MAXN], present[MAXN];
ll w[1 << 20];
ll ans[MAXN][21];

int main() {
  freopen("magic.in", "r", stdin);
  freopen("magic.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(false), cout.tie(0);
  cin >> n >> m >> q;
  vector<vector<int>> visable(n + 1);
  for (int i = 1, x; i <= n; ++i) {
    cin >> x;
    visable[i].resize(x);
    for (int j = 1, num; j <= x; ++j) {
      cin >> num;
      visable[i].push_back(num);
    }
  }
  
  for (int i = 1; i <= m; ++i) {
    sq[i] = 1LL * i * i;
    T_all += sq[i];
  }
  
  while ((1LL << (L + 1)) <= m) L++;
  
  if (L > 0) {
    for (int l = 1; l <= n; ++l) {
      memset(pat, 0, (m + 1) * sizeof(int));
      for (int k = 1; k <= L; ++k) {
        int r = l + k - 1;
        if (r > n) break;
        memset(present, 0, (m + 1) * sizeof(int));
        memset(w, 0, ((1 << k) * sizeof(ll)));
        for (int x : visable[r]) present[x] = 1;
        for (int x = 1; x <= m; ++x) {
          pat[x] = pat[x] << 1 | present[x];
          w[pat[x]] += sq[x];
        }
        ll T_min = T_all;
        for (int i = 0; i <= (1 << k) - 1; ++i) {
          if (w[i] < T_min) T_min = w[i];
        }
        ans[l][k] = T_all - T_min;
      }
    }
  }
  
  for (int l, r; q--; ) {
    cin >> l >> r;
    int len = r - l + 1;
    if (len <= L) cout << ans[l][len] << '\n';
    else cout << T_all << '\n';
  }
  return 0;
}