POJ2528，Mayor's posters（线段树+区间覆盖）

这道题可以抽象化为一个模型：给定一个定长（可能非常大）的线段，有N次操作，每次在[l,r]区间染上上一种颜色（后染上的会覆盖前染上的，每种颜色都不同），问最后有多少种颜色能够辨别出来。

本人弱鸡没有自己做出来。。。解题方法可以参考博客：

https://blog.csdn.net/qq_36908995/article/details/71698244

总的来说就是区间离散化+线段树处理。

先将区间离散化。

先将所有区间的端点值存入一个数组中，用x[]表示，然后对x[]排序，剔除相同的元素，生成新的数组x0[]，然后对于原区间，如[l0,r0]，我们用找到l0,r0在x0[]中的位置（即下标），并用它们代替原区间，如下面的样例：

1 4, 5 8, 1 10，排完序后就是1,1,4,5,8,10，去重后为1,4,5,8,10，现在用数组下标表示原区间：

1 4 -> 1 2

5 8 -> 3 4

1 10 -> 1 5

那么我们要怎么找到l0,r0在x0[]中的位置呢？其实，我们可以用二分查找，很快就可以找到，因为x0[]本身就是一个严格递增序列。

不过，只处理到这里是还不够的，如下面样例：

1 10, 1 4, 6 10，去重后为1,4,6,10，因此原区间就变成：

1 10 -> 1 4

1 4 -> 1 2

6 10 -> 3 10

但是这样做的话结果会输出2，而正确结果应当是3。为什么会这样呢，因为其实4,6本来是不连续的，而经过我们离散化处理之后变成了连续的了（变成了2,3），所以，在完成上面的步骤后，我们还要检测一遍去重后的数组x0[]，当x0[i]-x0[i-1]>1时，我们在i,i-1之间再插入一个数（满足>x0[i-1]，<x0[i]即可），这样就能避免这种情况。

接下来讨论如何用线段树处理。

这里可以参考浙大ACM校队的线段树讲解：

https://wenku.baidu.com/view/0218cceb6294dd88d0d26bce.html （很详细的线段树讲解，不局限于本题）

我们考虑一下每个区间有多少种涂色的情况：

1.一种颜色都没有；

2.只有一种颜色；

3.大于一种颜色。

看起来很像一个三进制数啊，不过用三进制数还没法具体表达出区间的状态。我们可以在线段树结点中设置一个域c，当c=0时，表示一种颜色也没有，c=k时，表示只有一种颜色，且这种颜色为k，当c=-1时，表示大于一种颜色。这样一来，我们就不难写出push_up函数了：

1.当左右子树的域c都等于-1，该结点c=-1；

2.当左右子树c不为0，也不为-1，若两者c不同，则该节点c=-1，相同且等于k，该节点c=k；

3.左子树c为0，记录该节点c与右子树相同，反之与左子树相同。

大致就这些了。

最后我们可以设置Flag[i]，表示第i颜色是否有出现，然后遍历一遍线段树就可以了。

代码如下：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstring> 
using namespace std;
typedef int ll;
const int maxn=1e4+5;
bool Flag[maxn<<3];
ll l[maxn],r[maxn],x[maxn<<3];
struct Node
{
	ll l,r;
	ll lazy,c;
}tr[maxn<<5];

int unique(int num)
{
	sort(x+1,x+1+num);
	int cnt0=1;	ll temp=x[1];
	for(int i=2;i<=num;++i)
	{
		if(x[i]==temp)	continue;
		temp=x[i];
		x[++cnt0]=temp;
	}
	int cnt=cnt0;
	for(int i=2;i<=cnt0;++i)
	{
		if(x[i]-x[i-1]>1)
			x[++cnt]=x[i]-1;
	}
	sort(x+1,x+1+cnt);
	return cnt;
}

int b_search(int l,int r,ll val)
{
	int m;
	while(l<r)
	{
		m=l+(r-l)/2;
		if(x[m]==val)	return m;
		else if(x[m]>val)	r=m;
		else l=m+1;
	}
	return l;
}

void push_up(int rt)
{
	if(tr[rt<<1].c==-1||tr[rt<<1|1].c==-1)
		tr[rt].c=-1;
	else if(tr[rt<<1].c&&tr[rt<<1|1].c)
	{
		if(tr[rt<<1].c==tr[rt<<1|1].c)
			tr[rt].c=tr[rt<<1].c;
		else tr[rt].c=-1;
	}
	else if(tr[rt<<1].c)
		tr[rt].c=tr[rt<<1].c;
	else tr[rt].c=tr[rt<<1|1].c;
}

void push_down(int rt)
{
	tr[rt<<1].lazy=tr[rt<<1|1].lazy=tr[rt].lazy;
	tr[rt<<1].c=tr[rt].lazy;
	tr[rt<<1|1].c=tr[rt].lazy;
	tr[rt].lazy=0;
}

void build(int rt,int l,int r)
{
	tr[rt].l=l;	tr[rt].r=r;
	tr[rt].c=tr[rt].lazy=0;
	if(l==r)	
		return;
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}

void update(int rt,int l,int r,ll val)
{
	if(l<=tr[rt].l&&tr[rt].r<=r)
	{
		tr[rt].lazy=val;
		tr[rt].c=val;
		return;
	}
	if(tr[rt].l==tr[rt].r)	return;
	if(tr[rt].lazy)
		push_down(rt);
	int mid=(tr[rt].l+tr[rt].r)>>1;
	if(mid<l)	 update(rt<<1|1,l,r,val);
	else if(mid>=r)	update(rt<<1,l,r,val);
	else
	{
		update(rt<<1,l,mid,val);
		update(rt<<1|1,mid+1,r,val);
	}
	push_up(rt);
}

void traversal(int rt)
{
	if(tr[rt].l==tr[rt].r)
	{
		Flag[tr[rt].c]=1;
		return;
	}
	if(tr[rt].lazy)	//遍历的时候也要记得向下更新
		push_down(rt);
	traversal(rt<<1);
	traversal(rt<<1|1);
}

inline void read(ll &ret)
{
	char c;
	while((c=getchar())&&(c>'9'||c<'0'));
	ret=0;
	while(c>='0'&&c<='9')	ret=ret*10+c-'0', c=getchar();
}

inline void out(ll x)
{
	if(x>9)	out(x/10);
	putchar(x%10+'0');
}

int main()
{
	ll T;
	read(T);
	while(T--)
	{
		ll n;
		read(n);
		int num=0;
		for(int i=1;i<=n;++i)
		{
			read(l[i]);
			read(r[i]);
			x[++num]=l[i];
			x[++num]=r[i];
		}
		num=unique(num);
		build(1,1,num);
		for(int i=1;i<=n;++i)
		{
			int l0,r0;
			l0=b_search(1,num+1,l[i]);
			r0=b_search(1,num+1,r[i]);
			update(1,l0,r0,i);
		}
		memset(Flag,0,sizeof(Flag));
		traversal(1);
		ll ans=0;
		for(int i=1;i<=num;++i)
			ans+=Flag[i];
		out(ans);
		putchar('\n');
	}
	return 0;
}
           

PS：这里的区间离散化技巧很重要哦，要多留意。