#include<stdio.h>
#include<map>
#include<algorithm>
#include<string.h>
using namespace std;
int b[80400],lazy[80400];
void Put(int l,int r,int a,int s,int e,int c)
{
	if(s>=l&&e<=r)
	{
		b[c]=a;
		lazy[c]=a;
		return;
	}
	if(lazy[c])
	{
		lazy[c*2]=lazy[c*2+1]=lazy[c];
		b[c*2]=b[c*2+1]=lazy[c];
		lazy[c]=0;
	}
	int m=(s+e)/2;
	if(l<=m)Put(l,r,a,s,m,c*2);
	if(r>m)Put(l,r,a,m+1,e,c*2+1);
}
int Query(int a,int s,int e,int c)
{
	if(s==e)
	{
		return b[c];
	}
	if(lazy[c])
	{
		lazy[c*2]=lazy[c*2+1]=lazy[c];
		b[c*2]=b[c*2+1]=lazy[c];
		lazy[c]=0;
	}
	int m=(s+e)/2;
	int p;
	if(a<=m)p=Query(a,s,m,c*2);
	if(a>m)p=Query(a,m+1,e,c*2+1);
	return p;
}
int main()
{
	int p,result,count,s[10050],e[10050],a[20100],i,T,n;
	map<int,int>mymap;
	map<int,int>mark;
	scanf("%d",&T);
	while(T--)
	{
		memset(b,0,sizeof(b));
		memset(lazy,0,sizeof(lazy));
		mymap.clear();
		mark.clear();
		scanf("%d",&n);
		count=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&s[i],&e[i]);
			if(mark[s[i]]==0)
			{
				mark[s[i]]++;
				a[count]=s[i];
				count++;
			}
			if(mark[e[i]]==0)
			{
				mark[e[i]]++;
				a[count]=e[i];
				count++;
			}
		}
		sort(a,a+count);
		for(i=0;i<count;i++)
		mymap[a[i]]=i+1;
		for(i=1;i<=n;i++)
		{
			Put(mymap[s[i]],mymap[e[i]],i,1,count,1);
		}
		result=0;
		mark.clear();
		for(i=1;i<=count;i++)
		{
			p=Query(i,1,count,1);
			if(mark[p]==0){mark[p]++;result++;}
		}
		printf("%d\n",result);
	}
	return 0;
}

• Re:求问为什么会TLE 我已经离散化了啊 (41) sperc4 2016-08-05 22:12:25
  • Re:求问为什么会TLE 我已经离散化了啊 (78) gnchenweiyu2019 2023-08-17 20:19:46