记录编号	606879	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	7.230 s
提交时间	2025-10-04 16:24:31	内存使用	57.87 MiB

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