程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> L - Colourful Rectangle(面積並加強版)

L - Colourful Rectangle(面積並加強版)

編輯：C++入門知識

L - Colourful Rectangle(面積並加強版)

花了兩個多小時才寫完，結果一直RE。

我用1 2 4表示三原色，結構體裡有兩個信息：sta(1~7)表示這段區間的顏色狀態,len[8]表示這段區間每種顏色的長度。後來想想這樣處理不對，因為同一區間可能會被同一種顏色多次覆蓋。但是我在sta中只記錄了一次這樣的顏色。

但是稍微一改就對了，不需要sta,拿一個數組cnt[3]表示0 1 2 這三種顏色出現了幾次，然後再用三原色去合成其他顏色。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define PP pair
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 20010;
const int mod = 1000000007;

int x[maxn];
LL area[10];

struct Line
{
	int x1,x2,y;
	int tag,col;
	bool operator < (const struct Line &tmp)const
	{
		 return y < tmp.y;
	}
}line[maxn];

struct node
{
	int l,r;
	int cnt[4]; //該區間被三原色覆蓋的次數
	int len[10];//每種顏色的長度
}tree[maxn*4];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	for(int i = 1; i <= 7; i++)
		tree[v].len[i] = 0;
	for(int i = 0; i <= 2; i++)
		tree[v].cnt[i] = 0;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

int Binsearch(int l, int r, int key)
{
	int mid,low = l,high = r;
	while(high >= low)
	{
		mid = (low + high)>>1;
		if(x[mid] == key)
			return mid;
		if(x[mid] > key)
			high = mid-1;
		else low = mid+1;
	}
	return -1;
}
//維護區間的長度
void maintain(int v)
{
	int sta = 0;
	for(int i = 0; i <= 2; i++)
	{
		if(tree[v].cnt[i] > 0)
			sta += (1 << i);
	}
	if(sta) //該區間有一種顏色覆蓋
	{
		memset(tree[v].len,0,sizeof(tree[v].len)); //先把所有顏色初始化為0
		tree[v].len[sta] = x[tree[v].r+1] - x[tree[v].l];//sta這種顏色的長度
		if(tree[v].l == tree[v].r)//葉子節點
			return;
		for(int i = 1; i <= 7; i++)//若子節點還有別的顏色，
		{
			if(sta != (sta|i) )
			{
				int tmp = tree[v*2].len[i] + tree[v*2+1].len[i];
				tree[v].len[sta|i] += tmp;//混合後的顏色長度增加
				tree[v].len[sta] -= tmp;//原來的顏色減少
			}
		}
	}
	else if(tree[v].l == tree[v].r)
		memset(tree[v].len,0,sizeof(tree[v].len));
	else
	{
		for(int i = 1; i <= 7; i++)
			tree[v].len[i] = tree[v*2].len[i] + tree[v*2+1].len[i];
	}
	return;
}

void update(int v, int l, int r, int col, int tag)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		tree[v].cnt[col] += tag;
		maintain(v);
		return;
	}
	int mid = (tree[v].l + tree[v].r)>>1;
	if(r <= mid)
		update(v*2,l,r,col,tag);
	else if(l > mid)
		update(v*2+1,l,r,col,tag);
	else
	{
		update(v*2,l,mid,col,tag);
		update(v*2+1,mid+1,r,col,tag);
	}
	maintain(v);
}

int main()
{
	int test;
	int n,k,x1,x2,y1,y2,t1;
	char ch[3];
	scanf(%d,&test);
	for(int item = 1; item <= test; item++)
	{
		memset(area,0,sizeof(area));
		scanf(%d,&n);
		t1 = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf(%s %d %d %d %d,ch,&x1,&y1,&x2,&y2);
			struct Line tmp;
			if(ch[0] == 'R')
				tmp.col = 0;
			else if(ch[0] == 'G')
				tmp.col = 1;
			else tmp.col = 2;
			tmp.x1 = x1;
			tmp.x2 = x2;
			tmp.y = y1;
			tmp.tag = 1;
			line[++t1] = tmp;
			x[t1] = x1;
			tmp.y = y2;
			tmp.tag = -1;
			line[++t1] = tmp;
			x[t1] = x2;
		}

		sort(line+1,line+1+t1);
		sort(x+1,x+1+t1);
		k = 1;
		for(int i = 2; i <= t1; i++)
		{
			if(x[i] != x[i-1])
				x[++k] = x[i];
		}

		build(1,1,k);
		for(int i = 1; i < t1; i++)
		{
			int l = Binsearch(1,k,line[i].x1);
			int r = Binsearch(1,k,line[i].x2)-1;

			update(1,l,r,line[i].col,line[i].tag);

			for(int j = 1; j <= 7; j++)
				area[j] += (LL)tree[1].len[j] * (LL)(line[i+1].y - line[i].y);
		}
		printf(Case %d:
,item);
		for(int i = 1; i <= 2; i++)
			printf(%I64d
,area[i]);
		printf(%I64d
%I64d
,area[4],area[3]);
		for(int i = 5; i <= 7; i++)
			printf(%I64d
,area[i]);
	}
	return 0;
}