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

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e6+10;
int n,m,q,p[N],g[N],lim;
long long sum,val[N][21];
vector<int>H[N]; 
const int MAXSIZE=(1<<20);
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
inline void read(int &a){
	int x=0,f=1;char ch=gc();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-48,ch=gc();
	return a=x*f,void();
}
void dfs(int st,int dep,int x,int l,int r){
	if(dep>=lim)return;
	if(l>r){
		long long res=sum;lim=min(lim,dep);
		for(int k=dep;k<=20;k++)val[st][k]=sum;
		return;
	}
	long long res=sum;
	for(int k=l;k<=r;k++)res-=1ll*p[k]*p[k];
	val[st][dep]=max(val[st][dep],res);
	if(x==n+1)return;
	int i=l,j=r;
	for(int k=l;k<=r;k++){
		if(H[x][p[k]])g[i++]=p[k];
		else g[j--]=p[k];
	}
	for(int k=l;k<=i-1;k++)p[k]=g[k];
	for(int k=j-1;k<=r;k++)p[k]=g[k];
	dfs(st,dep+1,x+1,l,i-1);
	dfs(st,dep+1,x+1,j+1,r);
	return;
}
int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	read(n),read(m),read(q);
	for(int i=1;i<=n;i++){
		int x;read(x);
		H[i].resize(m+2);
		for(int j=1,p;j<=x;j++){
			read(p);
			H[i][p]=1;
		}
	}
	for(int i=1;i<=m;i++)sum+=1ll*i*i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)p[j]=j;
		lim=20;dfs(i,0,i,1,m);
	}
	int l,r;
	while(q--){
		read(l),read(r);
		if(r-l+1>=20){
			printf("%lld\n",sum);
		}else{
			printf("%lld\n",val[l][r-l+1]);
		}
	}
	return 0;
}