记录编号	597510	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	魔法卡片	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	7.187 s
提交时间	2024-11-28 18:53:31	内存使用	53.26 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[1000010],ma;
long long sum,val[1000010];
vector<int> b[1000010];
vector<long long> ans[1000010];
int main()
{
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
	ma=log2(m)+1;
    for(int i=1;i<=m;i++)
	{
		sum+=(long long)i*i;
	}
    for(int i=1;i<=n;i++)
	{
        b[i].resize(m+2);
        int x;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
		{
			int c;
			scanf("%d",&c);
			b[i][c]=1;
		}
    }
    for(int l=1;l<=n;l++)
	{
        ans[l].resize(ma+1);
        for(int i=1;i<=m;i++)
		{
			a[i]=0;
		}
        for(int r=l;r<=min(n,l+ma);r++)
		{
            for(int i=1;i<=m;i++)
			{
				a[i]=(a[i]<<1)|b[r][i];
				val[a[i]]+=(long long)i*i;
			}
            long long res=sum;
            for(int i=0;i<(1<<(r-l+1));i++)
			{
				res=min(res,val[i]);
				val[i]=0;
			}
            ans[l][r-l]=sum-res;
        }
    }
    while(q--)
	{
        int l,r;
        scanf("%d%d",&l,&r);
        if(r-l+1>ma) printf("%lld\n",sum);
        else printf("%lld\n",ans[l][r-l]);
    }
    return 0;
}