POJ 3695 Rectangles 1w询问求20个矩阵面积并容斥

题目大意是给出若干个矩形(n <= 20) 然后m个询问(m <= 100000)

每个询问会给出一些矩形的编号，问这些矩形的面积并有多大

谈到矩形并，也许第一反应都是线段树

但是此题有一个特点，就是n非常小，m却非常大

用线段树很有可能会不行

于是换个思路，n很小，我们可以把所有的可能组合情况都考虑到，然后呢预处理出来，这样询问时就是O(1)的查询了

但是1<<20显然是远大于100000的

也就是说我们没必要把所有情况都考虑到。

只需要考虑这m个询问中的情况就可以了

于是我们先把询问中情况都读进来，用二进制存起来。

然后就是DFS，根据容斥原理

一个矩形的面积-二个矩形相交的面积+三个矩形相交的面积。。。。。。就这样

所以DFS中可以有两种分支，一种是拿这个矩形，另一种是不拿

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 const int inf = 1e8; const double eps = 1e-8; const double pi = acos(-1.0); template 
                 
                   inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template 
                  
                    inline void pt(T x) { if (x <0) { putchar('-');x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; typedef pair
                   
                     pii; int n, m; struct node{ int x1, x2, y1, y2; int area(){return abs(x1-x2)*abs(y1-y2);} }a[30]; int ask[100005]; int st[1<<21]; 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, a[deep+1].x1), max(ya, a[deep+1].y1), min(xb, a[deep+1].x2), min(yb, a[deep+1].y2), deep+1, -flag, sta|(1<
                    
                     >n>>m, n+m){ printf(Case %d: , Cas++); for(int i = 1; i <= n; i++){ rd(a[i].x1); rd(a[i].y1); rd(a[i].x2); rd(a[i].y2); } for(int i = 1, siz, num; i <= m; i++){ ask[i] = 0; rd(siz); while(siz-->0){rd(num); ask[i]|=1<<(num-1);} } memset(st, 0, sizeof st); dfs(0,0,inf,inf, 0,-1,0); for(int i = 1; i <= m; i++) printf(Query %d: %d , i, st[ask[i]]); puts(); } return 0; }

POJ 3695 Rectangles 1w询问求20个矩阵面积并 容斥