USACO Training Section 3.1 Shaping Regions

英文原题  中文题译

大意：在一张白色大纸上放若干个不透明的矩形纸片，每个纸片有一种颜色（可以是白色），这样，有重叠的话，后放的纸片的颜色覆盖了之前的颜色。问最后每种颜色占多大面积。

数据限制条件：底板长宽N<=10000，纸条数量K<=1000，颜色数C<=2500，所有数值都是整数。纸条的边界与底板边界均平行。

最粗暴的设想，设一个底板大小的二维数组，来一张纸条，把相应区域的颜色都改变。不过，显然这是不可接受的：空间O(N^2)，时间O(K*N^2)。

纸条的边界与底板边界均平行，使得可以用离散化，这样，区间的数量不是N^2，而是(2K)^2。暴力算法的时间复杂度变成O(K^3)，空间O(K^2)，完全可以一试了。

/*
ID: blackco3
TASK: rect1 
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_rect_ 1000
#define _max_color_ 2500
#define _max_size_ 10000
struct t_rect {
	int llx, lly, urx, ury, color ;
} rects[_max_rect_];
int mx[_max_size_+1], my[_max_size_+1];
int pos_x[_max_size_], pos_y[_max_size_], n_x=0, n_y=0;
//int mtrx[(_max_rect_<<1)+2][(_max_rect_<<1)+2];
int area[_max_color_];

int main() {
	freopen("rect1.in", "r", stdin);
	freopen("rect1.out", "w", stdout);

    int max_y, max_x, n_rect, max_color=0 ;
    cin >> max_y >> max_x >> n_rect ;
	for( t_rect *pc=rects; pc!=rects+n_rect; pc++ ){
		cin >> pc->llx >> pc->lly >> pc->urx >> pc->ury >> pc->color ;
		mx[pc->llx] = mx[pc->urx] = my[pc->lly] = my[pc->ury] = 1 ;
		max_color= max_color<pc->color ? pc->color : max_color, pc->color--;
	}
	mx[0] = my[0] = mx[max_x] = my[max_y] = 1 ;
	for( int *px=mx ; px!=mx+max_x+1; px++ )
		if( *px )
			pos_x[n_x]=px-mx, *px = n_x++ ;
	for( int *py=my ; py!=my+max_y+1; py++ )
		if( *py )
			pos_y[n_y]=py-my, *py = n_y++ ;
	int *mtrx=(int*)malloc(sizeof(int)*(n_x*n_y));
	memset( mtrx, 0, sizeof(int)*n_x*n_y);
	for( t_rect *pc=rects; pc!=rects+n_rect; pc++ ) {
		register int cur_color = pc->color ;
		for( register int iy=my[pc->lly], *py=mtrx+iy*n_x; iy!=my[pc->ury]; iy++, py+=n_x )
			for( register int ix=mx[pc->llx], *px=py+ix; ix!=mx[pc->urx]; ix++, px++ )
				*px=cur_color ;
	}
	register int* pm=mtrx;
	for( int *py=pos_y; py!=pos_y+n_y-1; py++){	
		for( int *px=pos_x; px!=pos_x+n_x-1; px++)
			area[*(pm++)] += (*(px+1)-*px)*(*(py+1)-*py) ;
		pm++;
	}
	for( int *pa=area; pa!=area+max_color; pa++ ){
		if( *pa )
			cout << (pa-area)+1 << " " << *pa << endl ;
	}
	free(mtrx);
	return 0;
}

一小时后，上述代码完成，用指针优化过的程序调通，但无法通过测试。时间是够，空间不够，晕。OJ给的空间，真小。POJ上一般64M，这里，10M就挂。好吧，既然如此，离散化之后不能开空间记录，就用线性空间。

继续暴力，每行直接填充计数。通过，最大数据用0.5秒。中途散步想的备用方案还没用上。

备用方案：填充时每个矩阵只填充最大最小值，按顺序来。然后扫描一次。这样，时间复杂度降低到O(k^2)。

/*
ID: blackco3
TASK: rect1 
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_rect_ 1000
#define _max_color_ 2500
#define _max_size_ 10000
struct t_rect {
	int llx, lly, urx, ury, color ;
} rects[_max_rect_];
int mx[_max_size_+1], my[_max_size_+1];
int pos_x[_max_size_], pos_y[_max_size_], n_x=0, n_y=0;
int area[_max_color_], line[(_max_rect_<<1)+2];

int main() {
	freopen("rect1.in", "r", stdin);
	freopen("rect1.out", "w", stdout);

    int max_y, max_x, n_rect, max_color=0 ;
    cin >> max_x >> max_y >> n_rect ;
	for( t_rect *pc=rects; pc!=rects+n_rect; pc++ ){
		cin >> pc->llx >> pc->lly >> pc->urx >> pc->ury >> pc->color ;
		mx[pc->llx] = mx[pc->urx] = my[pc->lly] = my[pc->ury] = 1 ;
		max_color= max_color<pc->color ? pc->color : max_color, pc->color--;
	}
	mx[0] = my[0] = mx[max_x] = my[max_y] = 1 ;
	for( int *px=mx ; px!=mx+max_x+1; px++ )
		if( *px )
			pos_x[n_x]=px-mx, *px = n_x++ ;
	for( int *py=my ; py!=my+max_y+1; py++ )
		if( *py )
			pos_y[n_y]=py-my, *py = n_y++ ;
	for( t_rect *pc=rects; pc!=rects+n_rect; pc++ ){
		pc->llx=mx[pc->llx], pc->urx=mx[pc->urx], pc->lly=my[pc->lly], pc->ury=my[pc->ury];
	}
	int lsize=sizeof(int)*(n_x+1) ;
	for( int y=0; y<n_y-1; y++ ){
		register int dy=pos_y[y+1]-pos_y[y];
		memset(line, 0, lsize);
		for( t_rect *pc=rects; pc!=rects+n_rect; pc++ ) {
			if( pc->lly>y || pc->ury<=y )
				continue ;
			register int cur_color = pc->color ;
			for( register int *px=line+pc->llx; px!=line+pc->urx; px++ )
					*px=cur_color ;
		}
		register int* pl=line;
		for( int *px=pos_x; px!=pos_x+n_x-1; px++)
			area[*(pl++)] += (*(px+1)-*px)*dy ;
	}
	for( int *pa=area; pa!=area+max_color; pa++ ){
		if( *pa )
			cout << (pa-area)+1 << " " << *pa << endl ;
	}
	return 0;
}