文章目录

题目链接：

http://poj.org/problem?id=2528
题意：就是有 N 种海报，每种海报有个长度[L,R]，后来的海报会覆盖前面来的海报，问最后从最上面看，能看得到几种海报

我的代码C++提交阔以AC，但是G++就会T，搜了一下G++与C++的区别：
https://blog.csdn.net/dt2131/article/details/58689903
这道题poj上的数据有点弱，贴一个讨论里很火的三组数据：

input：
3
3
5 6
4 5
6 8
3
1 10
1 3
6 10
5
1 4
2 6
8 10
3 4
7 10
output:
2
3
4

这道题关键就是离散化，<mark>而给的区间是格子，而不是点</mark>

比如图上的：
给的区间是
2
1 5
6 10

离散化后应该为
2
1 1
2 2

他们有的是在中间差值大于1的地方加点，但是我不喜欢这种T_T
我是先把格子弄成点然后再映射，右端点+1就是这段区间的右边比如上面这个例子弄了之后就只有 1 6 11 三个点，就是两段了

//#include"bits/stdc++.h"
#include"iostream"
#include"map"
#include"algorithm"
#include"vector"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int tree[maxn];
int N,n;
map<int,int>Mp,ans;
pair<int,int>a[maxn],b[maxn];
vector<int>vec;
void Build(int id,int L,int R)
{
	tree[id]=-1;//-1表示没有颜色 
	if(L==R)return ;
	int mid=L+R>>1;
	Build(id<<1,L,mid);
	Build(id<<1|1,mid+1,R);
}
void pushdown(int id)//把颜色传给子区间,并把这个节点的颜色改成0，表示有多种颜色 
{
	if(tree[id])tree[id<<1]=tree[id<<1|1]=tree[id];
	tree[id]=0;//0代表有很多种颜色 
}
void Change(int id,int L,int R,int qL,int qR,int x)
{
	if(qL>R||qR<L)return ;//超过了需要查询的区间就直接退出 
	if(qL<=L&&qR>=R)
	{
		tree[id]=x;
		return ;
	}
	pushdown(id);//更新当前节点的值 
	int mid=L+R>>1;
	Change(id<<1  ,L    ,mid,qL,qR,x);
	Change(id<<1|1,mid+1,  R,qL,qR,x);
}
void solve(int id,int L,int R)
{
	if(tree[id]==-1)return ;//没有颜色 
	if(tree[id])//如果不是0，那说明只有一种这个区间只有一种颜色 
	{
		ans[tree[id]]=1;
		return ;
	}
	if(L==R)
	{
		if(tree[id])ans[tree[id]]=1;
		return ;
	}
	int mid=L+R>>1;
	solve(id<<1,L,mid);
	solve(id<<1|1,mid+1,R);
}
void print()//输出离散化后的端点以及离散化后的区间 
{
	cout<<"vec :\n";
	for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";
	cout<<endl;
	cout<<"distinct:\n";
	for(int i=1;i<=N;i++)cout<<a[i].first<<" "<<a[i].second<<endl;
	cout<<endl;
}
void printTree()//输出线段树 
{
	cout<<"tree :"<<endl;
	for(int i=1;i<=(n-1)*4;i++)
	{
		cout<<"id="<<i<<" tree="<<tree[i]<<" | ";
		if((i&(i+1))==0)cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int T;
	cin>>T; 
	while(T--)
	{
		ans.clear();
		Mp.clear();
		vec.clear();
		cin>>N;
		for(int i=1;i<=N;i++)
		{
			cin>>b[i].first>>b[i].second;//这道题给的区间不是点区间，而是格子区间 
			Mp[b[i].first]=1;//用Mp记录一哈哪些点是出现过的，方便之后离散化 
			Mp[b[i].second+1]=1;//右端点+1 
		}
		for(map<int,int>::iterator it=Mp.begin();it!=Mp.end();it++)vec.push_back(it->first);//存储离散化后的点 
		sort(vec.begin(),vec.end());//把原来的点排序 
		n=vec.size();//离散化后的点 
		for(int i=0;i<n;i++)Mp[vec[i]]=i+1;//对原来的点进行离散化 
		for(int i=1;i<=N;i++)
		{
			a[i].first=Mp[b[i].first];
			a[i].second=Mp[b[i].second+1]-1;//注意是找+1后的右端点的映射的值的前一个点 
		}
		//print();
		Build(1,1,n);
		for(int i=1;i<=N;i++)Change(1,1,n,a[i].first,a[i].second,i);
		solve(1,1,n);
		cout<<ans.size()<<endl;
	}
}