[SGU 177]利用并差集处理矩形覆盖问题**

【题目大意】给定一个N*N的矩阵和M次染色，问最后是白色的格子还有多少个？

【算法分析】这题一看是线段树or矩形切割，但是仔细一想，可以发现一种新的算法，这中间利用了并差集。定义next[i,j]表示如果要染i，j这一个格子的话，应当去染哪一个格子。考虑我们写矩形切割的“浮冰法”，从后面开始进行insert，这样的话，后insert的必须避开先insert得。所以可以利用这个next进行跳跃。我这个next只针对当前行，就是next[i,j]的跳跃位置是对于第i行而言的。

初始时next[i,j]=j，表示要染这一格，那么就应该染这一格，比较拗口

然后如果对这一格被染色的话，那么next[i,j]=j+1，这样下一次就会越过我跳到下一格了，然后用并差集进行路径压缩，这样就能在平摊O(1)的复杂度调到下一个能染得格了！

这个算法中，对每个格子最多碰一次，所以染色的复杂度为O(N^2)，但是由于对于每一次染色，都必须枚举行，所以总复杂度是O(N^2+NM)。

【其它】1A,时限7S

997757 09.02.10 16:53 edward 177 .CPP Accepted 796 ms 9739 kb

【CODE】

#include #include const int N=1111;
const int M=5555;
int n,m,next[N][N],x1[M],x2[M],y1[M],y2[M],color[N][N],dc[M];

void swap(int &x,int &y){
    int tmp=x; x=y; y=tmp;
}   

void init(){
    for (int i=0;i<=n+1;i++)
      for (int j=0;j<=n+1;j++)
        next[i][j]=j;
}   

int findnext(int i,int j){
    if (next[i][j]==j) return j;
    next[i][j]=findnext(i,next[i][j]);
    return next[i][j];
}   

void work(){
    memset(color,200,sizeof(200));
    for (int tmp=m;tmp>=0;tmp–)
      for (int i=x1[tmp];i<=x2[tmp];i++){
          for (int j=y1[tmp];j<=y2[tmp];)
            if (next[i][j]==j){
                color[i][j]=dc[tmp];
                next[i][j]=j+1;
                j++;
            }
            else j=findnext(i,j);
      }
}   

void print(){
    int ans=0;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (color[i][j]==0) ans++;
    printf("%dn",ans);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    x1[0]=1; y1[0]=1; x2[0]=n; y2[0]=n;
    for (int i=1;i<=m;i++){
        int lx,ly,rx,ry;
        char co;
        scanf("%d%d%d%d %c",&lx,&ly,&rx,&ry,&co);
        if (lx>rx) swap(lx,rx);
        if (ly>ry) swap(ly,ry);
        x1[i]=lx; x2[i]=rx; y1[i]=ly; y2[i]=ry;
        if (co==’b’) dc[i]=1;
    }   
    init();
    work();
    print();
    return 0;
}