Vasya likes to formalize everything. For
example, Vasya sees a lot of vegetables in his grandmother’s garden, and a lot
of toys in his younger brother. And what will happen if you try to combine or
to intersect n sets? Large and different sets – up to a million elements
(inclusive)!
Since Vasya dreams to become a
mathematician, he decided to start his research with the study of simpler sets,
namely sets of integers.
Input. First line contains the number of different sets n
(1 ≤ n ≤ 20). Then n sets given in the next format:
· First line contains number t (1 ≤
t ≤ 106) – the number of integers in the next line.
· Second line contains t integers xi (1
≤ xi ≤ 106) – the elements of the set.
Next line contains the number of queries m
(1 ≤ m ≤ 100). Each of the next m lines contains
the queries of two types:
·
INTERSECTION
a b, where 1 ≤ a, b ≤ n
·
UNION a
b, where 1 ≤ a, b ≤ n
Output. Print for each query:
For the query of the first type the number
of elements in the intersection of sets a and b.
For the query of the second type the number
of elements in the union of sets a and b.
|
Sample
input |
Sample
output |
|
2 2 1 2 2 2 3 2 INTERSECTION
1 2 UNION 1 2 |
1 3 |
dynamic programming - masks
There are 20
sets in total, each of them stores numbers from 1 to 106.
Let’s declare an array bitset<1000001> bs[20]; for their
storage. The next step is to perform operations on the sets.
The elements of
the sets are numbers from 1 to 106. There are no more than 20 sets,
number them starting from 0. Let’s declare an array b of length 106, in the cell b[i] store the set (mask) of the
numbers of the sets to which the number i belongs. Consider the
following example:
·
number 1 belongs to the zero’s set: b[1] = (1 << 0) = 12
= 1;
·
number 2 belongs to the zero’s and the first set: b[2] = (1
<< 0) || (1 << 1) = 112 = 3;
·
number 3 belongs to the first set: b[3] = (1 << 1) = 102
= 2;
To determine the
number of elements in the intersection (union) of the a-th and b-th
sets, it is necessary to iterate all numbers from 1 to 106 and count how many of them belong to
sets a and / or b.
Algorithm realization
Declare an array
bs to store 20 sets.
#define MAX 1000001
bitset<MAX>
bs[20];
Read the input data.
scanf("%d", &n);
for(i = 0; i < n; i++)
{
Read the size of the set t.
scanf("%d",
&t);
Read t elements of the set.
while(t--)
{
scanf("%d",
&x);
In set number i, set the x-th bit to one.
bs[i][x] = 1;
}
}
Read the number of queries m.
scanf("%d\n",
&m);
while(m--)
{
scanf("%s%d%d\n",
s, &t, &x);
t--; x--;
Perform the operation given in s on sets number t and x. In the condition of the problem, the sets numbering starts from 1. In our
case numbering starts from zero. Subtract one from
the sets numbers.
bitset<MAX> cur;
if(s[0] == 'U')
{
cur = bs[t] | bs[x];
printf("%d\n",
cur.count());
}
else
{
cur = bs[t] & bs[x];
printf("%d\n",
cur.count());
}
}
}
#define MAX 1000000
int b[MAX];
char c[20];
Read n sets.
scanf("%d", &n);
for(i = 0; i < n; i++)
{
Current set contains t elements.
scanf("%d",
&t);
for(j = 0; j
< t; j++)
{
scanf("%d",&a);
The number a is contained in the set number i.
Set the i-th bit in the mask b[a] to one.
b[a] |= (1 << i);
}
}
Process q queries.
scanf("%d\n", &q);
while(q--)
{
Read the type of the query.
scanf("%s %d
%d\n", c, &x, &y);
x--; y--;
ans = 0;
Iterate through all the numbers j from 1 to 106. If the number j belongs to the set x and / or y, add one to the
resulting number of elements res.
if(c[0] == 'U')
for(j = 1; j < MAX; j++)
ans += ((b[j] & (1 << x)) ||
(b[j] & (1 << y)));
else
for(j = 1;
j < MAX; j++)
ans += ((b[j] & (1 << x))
&& (b[j] & (1 << y)));
Print the answer.
printf("%d\n",
ans);
}