题目大意是给出若干个矩形(n <= 20) 然后m个询问(m <= 100000)
每个询问会给出一些矩形的编号，问这些矩形的面积并有多大
谈到矩形并，也许第一反应都是线段树
但是此题有一个特点，就是n非常小，m却非常大
用线段树很有可能会不行
于是换个思路，n很小，我们可以把所有的可能组合情况都考虑到，然后呢预处理出来，这样询问时就是O(1)的查询了
但是1<<20显然是远大于100000的
也就是说我们没必要把所有情况都考虑到。
只需要考虑这m个询问中的情况就可以了
于是我们先把询问中情况都读进来，用二进制存起来。
然后就是DFS，根据容斥原理
一个矩形的面积-二个矩形相交的面积+三个矩形相交的面积。。。。。。就这样
所以DFS中可以有两种分支，一种是拿这个矩形，另一种是不拿
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 111111
#define MAXM 555555
#define INF 100000011
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define eps 1e-7
using namespace std;
int ask[MAXN];
int st[1111111];
struct Rec
{int x1, x2, y1, y2;
}p[22];
int n, m;
void dfs(int xa, int ya, int xb, int yb, int deep, int flag, int sta)
{if(xa >= xb || ya >= yb) return;if(deep == n){if(sta){for(int i = 1; i <= m; i++)if((ask[i] | sta) == ask[i])st[ask[i]] += flag * (xb - xa) * (yb - ya);}return;}dfs(xa, ya, xb, yb, deep + 1, flag, sta);dfs(max(xa, p[deep + 1].x1), max(ya, p[deep + 1].y1), min(xb, p[deep + 1].x2), min(yb, p[deep + 1].y2), deep + 1, -flag, sta |(1 << deep));
}
int in()
{char ch;int a = 0;while((ch = getchar()) == ' ' || ch == '\n');a += ch - '0';while((ch = getchar()) != ' ' && ch != '\n'){a *= 10;a += ch - '0';}return a;
}
int main()
{int cas = 0;while(scanf("%d%d", &n, &m) != EOF){if(!n && !m) break;memset(st, 0, sizeof(st));memset(ask, 0, sizeof(ask));for(int i = 1; i <= n; i++) scanf("%d%d%d%d", &p[i].x1, &p[i].y1, &p[i].x2, &p[i].y2);int t, x;for(int i = 1; i <= m; i++){t = in();while(t--){x = in();ask[i] |= (1 << (x - 1));}}dfs(0, 0, INF, INF, 0, -1, 0);printf("Case %d:\n", ++cas);for(int i = 1; i <= m; i++)printf("Query %d: %d\n", i, st[ask[i]]);printf("\n");}return 0;
}