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

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MS = 1<<20;
const int N = 1000010;
int n,m,q,ans[N][21],sum,tot[21][MS+500],num,now,ql,qr,S,mn,p;
queue<int>qu[30];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    freopen("magic.in", "r", stdin);freopen("magic.out", "w", stdout);
    cin>>n>>m>>q;
    int MM = m+1;
    vector<char> front((n+1)*MM, 0);
    for(int i=1;i<=m;++i)sum+=(i*i);
    for(int i=1;i<=n;++i){
        int basei = i * MM;
        cin>>num;
        for(int j=1;j<=num;++j){
            cin>>p;
            front[basei + p]=1;
        }
        for(int j=1;j<=m;++j){
            S=0;
            int mu=min(i,20LL);
            for(int u=1;u<=mu;++u){
                int card = i-u+1;
                int basec = card * MM;
                if(front[basec + j]==0)S|=(1LL<<(u-1));
                if(!tot[u][S])qu[u].push(S);
                tot[u][S]+=j*j;
            }
        }
        int mu=min(i,20LL);
        for(int len=1;len<=mu;++len){
            int distinct=qu[len].size();
            mn=1LL<<60;
            while(!qu[len].empty()){
                now=qu[len].front();qu[len].pop();
                mn=min(mn,tot[len][now]);
                tot[len][now]=0;
            }
            if(distinct<(1LL<<len)){
                ans[i][len]=sum;
            }else{
                ans[i][len]=sum-mn;
            }
        }
    }
    for(int i=1;i<=q;++i){
        cin>>ql>>qr;
        int len=qr-ql+1;
        if(len>=20)cout<<sum<<'\n';
        else cout<<ans[qr][len]<<'\n';
    }
    return 0;
}