调试通过：
#include
usingnamespacestd;
structNote{
intbegin;
intend;
Note*next;
};
intmain()
{
intl,m;
inti;
Note*p,*q;
cin>>l>>m;
Note*head=newNote;
Note*tail;
head->next=NULL;
cin>>head->begin>>head->end;
tail=head;
for(i=1;i<m;i++)
{//依次读入m个区域，并按照升序排列区域
p=newNote;
cin>>p->begin>>p->end;
p->next=NULL;
q=head;
if(p->endbegin)
{//在链表头插入节点
p->next=head;
head=p;
continue;
}
if(p->begin>tail->end)
{//在链表尾插入节点
tail->next=p;
tail=p;
continue;
}
while(q)
{
if(p->beginbegin&&p->end>=q->begin||p->beginend&&p->endnext->begin)
{//两个区域相交
q->begin=p->beginbegin?p->begin:q->begin;
q->end=p->endend?q->end:p->end;
deletep;
break;
}
elseif(p->beginend&&p->end>=q->next->begin)
{//新增区域连接两个相邻区域
q->begin=p->beginbegin?p->begin:q->begin;
q->end=q->next->end;
deletep;
q->next=q->next->next;
p=q->next;
deletep;
break;
}
elseif(p->begin>q->end&&p->endnext->begin)
{//在某个节点后插入新增区域
p->next=q->next;
q->next=p;
break;
}
q=q->next;
}
}
l++;//从0到l有l+1棵树
q=head;
while(q)
{
//coutbeginend<<endl;调试用
l-=q->end-q->begin+1;
q=q->next;
}
cout<<l<<endl;
return0;
}
