[BOI2010 pcb]贪心、平衡树

【题目和数据下载地址】http://www.ut.ee/boi/
【题目大意】
给定n条电线(Ai,Bi)，其中A点都在一矩形箱子的上方，B点都在矩形箱子的下方。
其中Ai和Bi分别表示他们的横坐标。
然后这些电线交叉的话会短路，问至少要弄多少层（每层之间完全隔开），才能把这些电线全连上而又不短路。
数据保证Ai和Bi是2*n个不相同的整数。

【算法分析】
显然，假如对于一对电线(i,j)，Ai我们先对电线按Ai从小到大排序，那么就变成了求把用最少的递增数列，把这个Bi数列全部分出来。
显然，假如Bi但是N<=100000。显然很难通过，因为边都有可能超过1000 0000。
于是我们可以贪心一下。
对于每个递增序列，记录它的最后一个就可以了，因为前面的已经和扩展无关了。
然后每一次对于一个Bi，在开了的ans个递增序列里找一个这样的序列i，满足：
Max(End[i]  ：End[i]然后将Bi插到那个序列后面去。
遇过找不到这样一个序列，那么就新开一个序列，ans++，End[ans]=Bi。
最后输出ans即可。
然后对于上面那个找Max(End[i]  ：End[i]【CODE】
#include #include #include const int N=100005;
struct Point{int x,y;}a[N];
int n,ans;

struct SBT_Type{
struct Node{int l,r,key,s;}tr[N*3];
int tot,root;
void update(int p){if (p) tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;}
int max(int x,int y){return x>y?x:y;}

void left(int &p){
int k=tr[p].r;
tr[p].r=tr[k].l;
tr[k].l=p;
update(p);
update(k);
p=k;
}

void right(int &p){
int k=tr[p].l;
tr[p].l=tr[k].r;
tr[k].r=p;
update(p);
update(k);
p=k;
}

void repair(int &p){
if (!p) return;
bool flag=false;
if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
right(p);
flag=true;
}
if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
left(tr[p].l);
right(p);
flag=true;
}
if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
left(p);
flag=true;
}
if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
right(tr[p].r);
left(p);
flag=true;
}
if (flag){
repair(tr[p].l);
repair(tr[p].r);
repair(p);
}
}

int del(int &p,int key){
tr[p].s–;
if (key int res=tr[p].key;
if (!tr[p].l || !tr[p].r) p=tr[p].l+tr[p].r;
else tr[p].key=del(tr[p].l,0x7FFFFFFF);
return res;
}
if (key else return del(tr[p].r,key);
}

void ins(int &p,int key){
if (!p){
p=++tot;
tr[p].l=tr[p].r=0; tr[p].s=1; tr[p].key=key;
return;
}
tr[p].s++;
if (key else ins(tr[p].r,key);
repair(p);
}

int Find(int p,int key){
if (!p) return -0x7FFFFFFF;
if (key>tr[p].key) return max(tr[p].key,Find(tr[p].r,key));
return Find(tr[p].l,key);
}
}SBT;

int cmp(const void *x,const void *y){
return ((Point*)x)->x-((Point*)y)->x;
}

int main(){
freopen("pcb.in","r",stdin);
freopen("pcb.out","w",stdout);
int i,tmp;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
qsort(a+1,n,sizeof(Point),cmp);
SBT.tot=SBT.root=ans=0;
for (i=1;i<=n;i++){
tmp=SBT.Find(SBT.root,a[i].y);
if (tmp==-0x7FFFFFFF){
ans++;
SBT.ins(SBT.root,a[i].y);
}
else{
SBT.del(SBT.root,tmp);
SBT.ins(SBT.root,a[i].y);
}
}
printf("%dn",ans);
}