hdu4419Colourful Rectangle

链接

分别求出7种颜色覆盖的面积。

做法：每种颜色设定一个标号，以二进制表示R：100 G：010 B：001 。这样很明显可以知道RG：110 GB：011 以此类推。

求解时，需要开一个二维标记数组，标记了这一段的某种颜色被标记了几次，然后类似状压的方式求解。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define N 41010

 #define LL __int64

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 map<int,int>f;

 int s[N<<][];

 int fs[N<<],a[N],ff[N<<][];

 int val[N];

 int id[];

 LL num[N];

 struct node

 {

     int x1,x2,y;

     int f;

     node(){}

     node(int x1,int x2,int y,int f):x1(x1),x2(x2),y(y),f(f){}

     bool operator <(const node &S)const

     {

         return y<S.y;

     }

 }p[N];

 void up(int w,int l,int r)

 {

     int i;

     if(fs[w]==)

     {

         for(i = ; i <=  ; i++)

         {

             if(l==r)

             s[w][i] = ;

             else

             s[w][i] = s[w<<][i]+s[w<<|][i];

         }

     }

     else

     {

         int res = val[r+]-val[l];

         int cnt[] = {};

         for(i = ; i <= ; i++)

         {

             if(l==r)

             {

                 if(i==fs[w])

                 cnt[i] += val[r+]-val[l];

                 else

                 cnt[i] += ;

             }

             else

             {

                 cnt[i|fs[w]] += s[w<<][i]+s[w<<|][i];

             }

         }

         for(i = ; i <= ; i++)

         res-=cnt[i];

         cnt[fs[w]]+=res;

         for(i = ; i <=  ; i++)

         s[w][i] = cnt[i];

     }

 }

 void build(int l,int r,int w)

 {

     int i;

     for(i = ;i<= ; i++)

     {s[w][i] = ff[w][i] = ;}

     fs[w] = ;

     if(l==r)

     {

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

 }

 void update(int a,int b,int d,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         ff[w][abs(d)]+=d/abs(d);

         if(d>)

         fs[w]|=d;

         else if(ff[w][-d]==) fs[w]+=d;

         up(w,l,r);

         return ;

     }

     int m = (l+r)>>;

     if(a<=m) update(a,b,d,l,m,w<<);

     if(b>m) update(a,b,d,m+,r,w<<|);

     up(w,l,r);

 }

 int main()

 {

     id['R'] = ;

     id['G'] = ;

     id['B'] = ;

     int i,j,t,n,cas = ;

     char sr[];

     cin>>t;

     while(t--)

     {

         f.clear();

         scanf("%d",&n);

         memset(num,,sizeof(num));

         int g=  ,dd[];

         for(i = ; i <= n; i++)

         {

             int x1,x2,y1,y2,k;

             scanf("%s%d%d%d%d",sr,&x1,&y1,&x2,&y2);

             if(sr[]=='R') k = id['R'];

             else if(sr[]=='G') k = id['G'];

             else k = id['B'];

             p[++g] = node(x1,x2,y1,k);

             a[g] = x1;

             p[++g] = node(x1,x2,y2,-k);

             a[g] = x2;

         }

         sort(a+,a+g+);

         sort(p+,p+g+);

         int o = ;

         f[a[]] = ++o;

         val[o] = a[];

         for(i = ; i <= g ; i++)

         if(a[i]!=a[i-])

         {

             f[a[i]] = ++o;

             val[o] = a[i];

         }

         build(,o-,);

         for(i = ; i < g; i++)

         {

             int l = f[p[i].x1];

             int r = f[p[i].x2]-;        //cout<<l<<" "<<r<<endl;

             if(l<=r)

             {

                 update(l,r,p[i].f,,o-,);

             }

             for(j = ; j <= ;  j++)

             num[j] += (LL)(p[i+].y-p[i].y)*s[][j];

         }

         dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ;

         printf("Case %d:\n",cas++);

         for(i = ; i <= ; i++)

         printf("%I64d\n",num[dd[i]]);

     }

     return ;

 }