记录编号	606903	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	梦那边的美好AC	是否通过	通过
代码语言	C++	运行时间	6.715 s
提交时间	2025-10-04 16:52:00	内存使用	31.94 MiB

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
const int M = 1e6 + 10;

int n, m, q, B;
ll sum;
vector<int> c[N];
ll p[N][21];
ll f[1 << 20];
ll w[M];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    B = m ? ceil(log2(m)) : 0;
    for(int i = 1;i <= n;i ++){
        int x; cin >> x;
        c[i].resize(m + 1, 0);
        for(int j = 0;j < x;j ++){
            int v; cin >> v;
            c[i][v] = 1;
        }
    }
    sum = 0;
    for(int i = 1;i <= m;i ++) sum += (ll)i * i;
    for(int i = 1; i <= n;i ++){
        memset(w, 0, sizeof(ll) * (m + 1));
        for (int j = i, l = 1;j <= min(i + B - 1, n);j ++, l ++){
            memset(f, 0, sizeof(ll) * (1 << l));
            for(int k = 1;k <= m;k ++){
                w[k] = (w[k] << 1) | c[j][k];
                f[w[k]] += (ll)k * k;
            }
            ll minx = sum;
            for(int k = 0;k < (1 << l);k ++) minx = min(minx, f[k]);
            p[i][l] = sum - minx;
        }
    }
    while(q --){
        int l, r; cin >> l >> r;
        int len = r - l + 1;
        if (len > B) cout << sum << '\n';
        else cout << p[l][len] << '\n';
    }
    return 0;
}