1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <math.h>
 5 #include <algorithm>
 6 using namespace std;
 7 #define INF 100000000
 8 typedef struct point
 9 {
10     int x1,y1,x2,y2;
11 }point;
12 point p[100];
13 int ans[1100000]={0};
14 int n;
15 void dfs(int x1,int y1,int x2,int y2,int deep,int sign,int sta)
16 {
17     if( x1 >= x2 || y1 >= y2 ) return;
18     if(deep==n)
19     {
20         if(sta)
21         for(int i=1;i<(1<<n);i++)
22         {
23             if((i|sta)<=i)
24             ans[i]+=sign*(x2-x1)*(y2-y1);
25         }
26         return ;
27     }
28     dfs(x1,y1,x2,y2,deep+1,sign,sta);
29     dfs(max(x1,p[deep].x1),max(y1,p[deep].y1),min(x2,p[deep].x2),min(y2,p[deep].y2),deep+1,-sign,sta|(1<<deep));
30 }
31 int main()
32 {
33     int m,i,ss,cas=1,mm,x,cass;
34     while(scanf("%d%d",&n,&m),(n||m))
35     {
36         memset(ans,0,sizeof(ans));
37         for(i=0;i<n;i++)
38             scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
39         dfs(0,0,INF,INF,0,-1,0);
40         printf("Case %d:\n",cas++);
41         cass=1;
42         while(m--)
43         {
44             scanf("%d",&mm);
45             ss=0;
46             for(i=0;i<mm;i++)
47             {
48                 scanf("%d",&x);
49                 ss|=(1<<(x-1));
50             }
51             printf("Query %d: %d\n",cass++,ans[ss]);
52         }
53         printf("\n");
54     }
55 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <math.h>
 5 #include <algorithm>
 6 using namespace std;
 7 #define INF 100000000
 8 typedef struct point
 9 {
10     int x1,y1,x2,y2;
11 } point;
12 point p[100];
13 int ans[1100000],staa[100005];
14 int n,m;
15 void dfs(int x1,int y1,int x2,int y2,int deep,int sign,int sta)
16 {
17     if( x1 >= x2 || y1 >= y2 ) return;
18     if(deep==n)
19     {
20         if(sta)
21             for(int i=0; i<m; i++)
22             {
23                 if((staa[i]|sta)<=staa[i])
24                     ans[staa[i]]+=sign*(x2-x1)*(y2-y1);
25             }
26         return ;
27     }
28     dfs(x1,y1,x2,y2,deep+1,sign,sta);
29     dfs(max(x1,p[deep].x1),max(y1,p[deep].y1),min(x2,p[deep].x2),min(y2,p[deep].y2),deep+1,-sign,sta|(1<<deep));
30 }
31 int main()
32 {
33     int i,cas=1,mm,x,cass;
34     while(scanf("%d%d",&n,&m),(n||m))
35     {
36         memset(ans,0,sizeof(ans));
37         memset(staa,0,sizeof(staa));
38         for(i=0; i<n; i++)
39             scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
40         printf("Case %d:\n",cas++);
41         cass=0;
42         while(m--)
43         {
44             scanf("%d",&mm);
45             for(i=0; i<mm; i++)
46             {
47                 scanf("%d",&x);
48                 staa[cass]|=(1<<(x-1));
49             }
50             cass++;
51         }
52         m=cass;
53         dfs(0,0,INF,INF,0,-1,0);
54         for(i=1; i<=cass; i++)
55             printf("Query %d: %d\n",i,ans[staa[i-1]]);
56         printf("\n");
57     }
58 }