有$??$张卡片，每张卡片有正反两面。正面和反面一共有$1, 2, ..,??$这$??$个数，有些数在正面，有些在反面，但是不会有数同时存在于两个面。这$??$张卡片排成一排，标号为$1, 2, .., ??$。
进行$??$次询问，每次给出两个数$??, ??(?? ≤ ??)$，定义$??(??, ??)$为所有在第$??, ?? + 1, .., ??$张卡片的正面出现过的数的平方和。你可以随意将卡片翻面，使得$??(??, ??)$最大化，输出这个值。
首先如果每次都选择占没被选中部分的一半以上的方案，至多 $log_{2}^{m}$ 次就能得到全集。
所有当区间长度大于 $log_{2}^{m}$ 的时候直接得到答案。
对于区间长度小的部分暴力求效率是 $O(m^{2}n)$ 。
至少我们发现对于一个数字如果不选，意味着所有包含这个数字的那面都得朝下，只有一种。所以我们去看至少能有几个数不选。总权值减去最小价值即为答案。
#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 n,m,Q,a[N],Lg; LL sum,val[N]; vector<int> v[N]; vector<LL> ans[N]; il int read(){ int x,f=1;char ch; _(!)ch==‘-‘?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x; } int main() { n=read();m=read();Q=read();Lg=log2(m)+1; for(int i=1;i<=m;i++)sum+=1ll*i*i; for(int i=1;i<=n;i++){ v[i].resize(m+2); int x=read(); for(int j=1;j<=x;j++)v[i][read()]=1; } for(int l=1;l<=n;l++){ ans[l].resize(Lg+1); for(int i=1;i<=m;i++)a[i]=0; for(int r=l;r<=min(n,l+Lg);r++){ for(int i=1;i<=m;i++)a[i]=(a[i]<<1)|v[r][i],val[a[i]]+=1ll*i*i; LL 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=read(),r=read(); if(r-l+1>Lg)printf("%lld\n",sum); else printf("%lld\n",ans[l][r-l]); } return 0; }
原文：https://www.cnblogs.com/Jessie-/p/11015190.html
