NUAA ACM OJ源码

				#include 
				#include 
				#include 
				#include 
				#include 
				using namespace std;
				
				//POJ 2528 线段覆盖 线段树
				//注意 输入3 4，其实表示的是覆盖的线段从2到4，注意看图，被阴了。。。
				#define NMAX 60000
				#define MIN 0.000000001
				#define PI 3.1415926535
				typedef struct line
				{
					int ll;
					int rr;
				}line;
				
				typedef struct tree
				{
					int left;
					int right;
					int color;
				}tree;
				
				int lisan[NMAX*2];
				line shuru[NMAX];
				int temp[NMAX*2];
				tree fun[NMAX*4];
				int cc[NMAX];
				int lsnum;
				
				int cmpx(const void *a,const void *b)
				{
					return (*(int *)a) - (*(int *)b);
				}
				
				int search(int key)
				{
					int *p;
					p=(int *)bsearch(&key,lisan+1,lsnum,sizeof(int),cmpx);
					return (p-lisan);
				}
				
				void init(int num)
				{
					int i,j;
					for(i=1,j=0;i					{
						temp[++j]=shuru[i].ll;
						temp[++j]=shuru[i].rr;
					}
					qsort(temp+1,num*2,sizeof(int),cmpx);
					lisan[1]=temp[1];
					for(i=2,j=1;i					{
						while(i						if(i 					}
					lsnum=j;
				}
				
				void create(int p,int l,int r)
				{
					if(l==r) return;
					fun[p].left=l;
					fun[p].right=r;
					fun[p].color=0;
					if(r-l>1)
					{
						create(2*p,l,(l+r)/2);
						create(2*p+1,(l+r)/2,r);
					}
				}
				
				void insert(int p,int l,int r,int c)
				{
					int mid=(fun[p].left+fun[p].right)/2;
					if(fun[p].color!=c)
					{
						if(l==fun[p].left && r==fun[p].right) fun[p].color=c;
						else
						{
							if(fun[p].color>0)
							{
								fun[2*p].color=fun[p].color;
								fun[2*p+1].color=fun[p].color;
							}
							fun[p].color=-1;
							if(r							else if(l>=mid) insert(2*p+1,l,r,c);
							else 
							{
								insert(2*p,l,mid,c);
								insert(2*p+1,mid,r,c);
							}
						}
					}
				}
				
				void cal(int p)
				{
					if(fun[p].color>0) cc[fun[p].color]++;
					else if(fun[p].color == -1)
					{
						cal(2*p);
						cal(2*p+1);
					}
				}
				
				int solve(int num)
				{//广告个数
					int ans=0,a,b,i,tt;
					for(i=1;i					init(num);
					create(1,1,lsnum);
					for(i=1;i					{
						a=search(shuru[i].ll);
						b=search(shuru[i].rr);
						if(a!=b) 
						{
							if(a							if(a>b) insert(1,b,a,i);
						}
					}
					cal(1);
					for(i=1;i						if(cc[i]>0) ans++;
					return ans;
				}
				
				int main()
				{
					int num,nnum,i,j,a,b;
					scanf("%d",&nnum);
					for(i=1;i					{
						memset(lisan,0,sizeof(lisan));
						memset(temp,0,sizeof(temp));
						memset(cc,0,sizeof(cc));
						scanf("%d",&num);
						for(j=1;j						{
							scanf("%d %d",&a,&b);
							shuru[j].ll=a-1;
							shuru[j].rr=b;
						}
						printf("%d\n",solve(num));
					}
					return 0;
				}