记录编号	606985	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	6.080 s
提交时间	2025-10-04 20:28:53	内存使用	99.32 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 x,y,z,b[N],K;
LL s,tmp[N];
vector<int> c[N];
vector<LL> res[N];
il int in(){
    int a,f=1;char ch;
    _(!)ch=='-'?f=-1:f;a=ch^48;
    _()a=(a<<1)+(a<<3)+(ch^48);
    return f*a;
}
int main(){
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    
    x=in();y=in();z=in();K=0;
    while((1<<K)<=y)K++;K++;
    for(int i=1;i<=y;i++)s+=1ll*i*i;
    for(int i=1;i<=x;i++){
        c[i].resize(y+2);
        int t=in();
        for(int j=1;j<=t;j++)c[i][in()]=1;
    }
    
    for(int l=1;l<=x;l++){
        res[l].resize(K+1);
        for(int i=1;i<=y;i++)b[i]=0;
        for(int r=l;r<=min(x,l+K-1);r++){
            int len=r-l+1;
            for(int i=1;i<=y;i++)b[i]=(b[i]<<1)|c[r][i],tmp[b[i]]+=1ll*i*i;
            LL mn=s;
            for(int i=0;i<(1<<len);i++)mn=min(mn,tmp[i]),tmp[i]=0;
            res[l][len-1]=s-mn;
        }
    }
    while(z--){
        int l=in(),r=in();
        int len=r-l+1;
        if(len>=K)printf("%lld\n",s);
        else printf("%lld\n",res[l][len-1]);
    }
    return 0;
}