【题目大意】给定一个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
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;
}