程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> U - Count the Colors(成段更新+統計)

U - Count the Colors(成段更新+統計)

編輯：C++入門知識

U - Count the Colors(成段更新+統計)

有n個操作，每個操作定義為x1,x2,c，表示把區間[x1,x2]染成c色，區間可重復染色，最後問每種顏色存在幾個間斷的區間中。

注意是對區間進行染色，而不是點。

成段更新很簡單，在統計每種顏色所在間斷的區間時，先把線段樹中節點信息映射到數組中然後統計，沒想到這一點，一直在想怎麼在線段樹上進行統計。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int maxn = 8010;

struct node
{
	int l,r;
	int col;
}tree[maxn*4];
int ans[maxn];
int arr[maxn];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].col = -1;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

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

void query(int v, int l, int r)
{
	if(tree[v].col != -1)
	{
		for(int i = tree[v].l; i <= tree[v].r; i++)
		{
			arr[i] = tree[v].col;
		}
		return;
	}
	if(tree[v].l == tree[v].r)
	{
		arr[tree[v].l] = tree[v].col;
		return;
	}

	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		query(v*2,l,r);
	else if(l > mid)
		query(v*2+1,l,r);
	else
	{
		query(v*2,l,mid);
		query(v*2+1,mid+1,r);
	}
}

int main()
{
	int n,cn,t;
	int ll[maxn],rr[maxn],cc[maxn];

	while(~scanf(%d,&t))
	{
		memset(ans,0,sizeof(ans));
		n = -1;
		cn = -1;
		for(int i = 1; i <= t; i++)
		{
			scanf(%d %d %d,&ll[i],&rr[i],&cc[i]);
			n = max(n,rr[i]);
			cn = max(cn,cc[i]);
		}
		build(1,0,n-1);

		for(int i = 1; i <= t; i++)
		{
			update(1,ll[i],rr[i]-1,cc[i]);
		}
		query(1,0,n-1);
		
		ans[arr[0]] += 1;
		for(int i = 1; i <= n-1; i++)
		{
			if(arr[i] != arr[i-1])
				ans[arr[i]] += 1;
		}
		for(int i = 0; i <= cn; i++)
		{
			if(ans[i])
				printf(%d %d
,i,ans[i]);
		}
		printf(
);
	}
	return 0;
}