HR34E Magic Cards <状压>

Problem

Magic Cards

by Birjik

Description

Birzhan has $n$ cards, numbered from $1$ to $n$. Every card has each number from $1$ to $m$ written on it. Some numbers exist on the front side of the card and some on the back side. No number exists on both the sides of a card at the same time. These cards are placed on the table in a row such that only one side is visible. Birzhan is allowed to flip them any number of times.
Now, Birzhan has to answer $q$ queries each of them consisting of two integers $l$ and $r$ ($1\le l\le r\le n$). We define $f(l,r)$ as the sum of the squares of every integer from $1$ to $m$ if it exists on the visible side of any card numbered from $l$ to $r$. Given that Birzhan can flip any number of cards any number of times, find and print the maximum value of $f(l,r)$.
For example, given $3$ cards and $m=5$ we have the as follows:-

Now, for $l=1$ and $r=2$. We have $1,2,4,5$ on the two cards, the sum of their squares is $46$.
If we flip the first card, we get $3,4,5$, the sum of their squares is $50$.
And, if we flip both cards, we get $1,2,3,4,5$, the sum of their squares is $55$
Hence, the maximum value of $f(1,2)$ in the above case is $55$.

Input Format

The first line contains three space-separated integers, $n$, $m$, and $q$, denoting the number of cards, what numbers written on each card, and the number of queries, respectively.
Each of the next $n$ lines describes the cards. On each line, the first number is $x_i$, denoting the count of numbers written on the visible side of the $i^{th}$ card. Next $x_i$ space-separated unique integers represent the numbers written on the visible side of that card, each between $1$ and $m$.
Next $q$ lines contain two space-separated integers, $l$ and $r$, describing the query mentioned above.

Constraints

• $1\le n\times m,q\le 10^6$
• $0\le x_i\le m$
• $1\le l\le r\le n$

Output Format

Print the maximum value of $f(l,r)$ for each query.

Sample

Sample Input 0

2 3 2
2 2 1
2 2 3
1 1
1 2

Sample Output 0

9
14

Explanation 0
In the first query, there is only $1$ card, and Birzhan has $2$ options:

• Let it be as it is: sum of squares would be $1^2+2^2=5$
• Or flip it: sum of squares would be $3^2=9$

So the maximum $f(1,1)$ Birzhan can achieve is $9$.
On the second query, Birzhan doesn’t need to flip any of them to maximize $f(1,2)$ so the answer would be $1^2+2^2+3^2=14$.
Sample Input 1

2 5 1
3 4 2 1
2 4 3
1 2

Sample Output 1

50

Explanation 1
If Birzhan flipped only the first card, the answer would be $3^2+4^2+5^2=50$. You can notice that it’s impossible to get a better result.

标签：状压

Translation

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

Solution

没结论是神仙题，有结论立马变水题。

结论：若牌的数量大于$\lceil\log_2m\rceil$，则一定可以通过某种方式使得所有数都至少出现一次。
证明：对于第$i$张牌，若前面还没出现过的数有$k$个，那么这张牌取正面或反面至少可以出现$\lceil\frac{k}{2}\rceil$个前面未出现过的数。于是$\lceil\log_2m\rceil$张牌可以保证出现所有$m$个数。

对于询问$[l,r]$，若$r-l+1>\log_2m$，则答案为$sum=1^2+2^2+\cdots+m^2$，否则，区间长度一定不大于$20$。预处理出长度不大于$20$的所有区间的最大可能答案，直接回答询问即可。

接下来用状态压缩加速预处理。对于区间$[l,r]$的一种方案，用$r-l+1$位二进制数表示，其中$0$表示这一位置的牌背面朝上，$1$表示这一位置的牌正面朝上。对于$1\sim m$中的每一个数，均可以处理出一个数$S$，其中第$i$位表示第$i$个位置的牌上这个数是在正面($1$)还是背面($0$)。那么当且仅当这个区间的方案为$\neg S$时，才不可能出现这个数。用$s_i$表示情况$i$下所有不能出现的数的平方和。处理每个数对应的$S$并在$s_{\neg S}$减去这个数的平方，然后枚举每种方案取最大值即可。用滑动窗口即可在$O(m)$的时间内从一个区间转移到另一个区间，如此即可在$O(nm\log m)$的复杂度下进行预处理。

Code

#include <bits/stdc++.h>
#define MAX_N 2000000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <int> a[MAX_N+5];
int n, m, q, L, sta[MAX_N+5];
lnt s[MAX_N+5], f[MAX_N+5][21], sum;
int main() {
    read(n), read(m), read(q);
    for (int i = 1; i <= n; i++) {
        int cnt; read(cnt);
        for (int j = 0, x; j < cnt; j++)
            read(x), a[i].push_back(x);
    }
    L = (int)ceil(log2(m));
    sum = 1LL*m*(m+1)*(2*m+1)/6;
    for (int len = 1; len <= L; len++)
        for (int l = 1, r = len; r <= n; l++, r++) {
            if (l == 1) {
                for (int i = 1; i <= m; i++) sta[i] = 0;
                for (int i = 0; i < (1<<len); i++) s[i] = 0;
                for (int i = l; i <= r; i++)
                    for (int x : a[i]) sta[x] |= 1<<(i-l);
                for (int i = 1; i <= m; i++)
                    s[(~sta[i])&((1<<len)-1)] += 1LL*i*i;
            } else {
                for (int i = 1; i <= m; i++)
                    s[(~sta[i])&((1<<len)-1)] -= 1LL*i*i;
                for (int i = 1; i <= m; i++) sta[i] >>= 1;
                for (int x : a[r]) sta[x] |= 1<<(r-l);
                for (int i = 1; i <= m; i++)
                    s[(~sta[i])&((1<<len)-1)] += 1LL*i*i;
            }
            for (int i = 0; i < (1<<len); i++)
                f[l][len] = max(f[l][len], sum-s[i]);
        }
    while (q--) {
        int l, r; read(l), read(r);
        if (r-l+1 > L) printf("%lld\n", sum);
        else printf("%lld\n", f[l][r-l+1]);
    }
    return 0;
}