HackerRank - Week of Code 34 - Magic Cards

题目大意

桌面上有$n$张牌,每张牌上都写上了$1$到$m$的所有正整数各一次,其中有的数字写在牌的正面,有的在反面。
有$q$次询问,每次询问一个区间$[l,r]$的所有牌,每张牌可以任意决定正面还是反面朝上,问朝上的牌中所有出现过至少一次的数的平方和的最大值是多少。

$1\leq n\times m,q\leq10^6$


题目分析

挺有趣的一道题目,一开始看上去不怎么可做。发现了性质之后就简单很多了。

可以发现只要区间内牌的数目超过了$L=\lceil\log_2 m\rceil$,就一定可以让所有的数字都出现。
证明很简单,假设我们现在要大小为$x$的数字集合全部出现,由于一张牌上写了所有的数字,因此正面朝上或者反面朝上一定有一种情况出现数字集合与目标集合的交集大小$\geq\lceil\frac x2\rceil$,因此目标集合大小至少减半。
接下来就很简单了,考虑预处理所有长度为$L$的区间的答案,我们直接算出每个数字在各个牌的正反情况存成一个$L$位二进制$s$,然后枚举出现情况的二进制$S$,将总和减去$s=\lnot S$的数字平方和更新就好了。
时间复杂度$O(nm\log m+q)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int buf[30];
inline void write(LL x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}
const int N=1000005;
const int M=1000005;
const int MAXL=22;
vector<int> cards[N];
LL ans[N][MAXL];
int state[M];
int cnt[N];
LL bin[M];
int n,m,q,L;
LL all;
void pre()
{
L=(int)ceil(log(m)/log(2));
for (int l=1;l<=L;++l)
for (int i=1;i+l-1<=n;++i)
{
if (i==1)
{
for (int s=0;s<1<<l;++s) bin[s]=0;
for (int j=1;j<=m;++j) state[j]=0;
for (int j=1;j<=l;++j)
for (int x:cards[i+j-1])
state[x]|=1<<j-1;
for (int j=1;j<=m;++j) bin[(~state[j])&((1<<l)-1)]+=1ll*j*j;
}
else
{
for (int j=1;j<=m;++j) bin[(~state[j])&((1<<l)-1)]-=1ll*j*j,state[j]>>=1;
for (int x:cards[i+l-1]) state[x]|=1<<l-1;
for (int j=1;j<=m;++j) bin[(~state[j])&((1<<l)-1)]+=1ll*j*j;
}
LL ret=0;
for (int s=0;s<1<<l;++s) ret=max(ret,all-bin[s]);
ans[i][l-1]=ret;
}
}
int main()
{
freopen("magiccards.in","r",stdin),freopen("magiccards.out","w",stdout);
n=read(),m=read(),q=read(),all=0;
for (int i=1;i<=m;++i) all+=1ll*i*i;
for (int i=1;i<=n;++i)
{
cnt[i]=read();
for (int j=1;j<=cnt[i];++j) cards[i].push_back(read());
}
pre();
for (int i=1,l,r;i<=q;++i,putchar('\n'))
{
l=read(),r=read();
if (r-l+1>L) write(all);
else write(ans[l][r-l]);
}
fclose(stdin),fclose(stdout);
return 0;
}