地平线(x轴)上有n个矩(lou)形(fang)，用三个整数h[i],l[i],r[i]来表示第i个矩形：矩形左下角为(l[i],0)，右上角为(r[i],h[i])。地平线高度为0。在轮廓线长度最小的前提下，从左到右输出轮廓线。
第一行一个整数n，表示矩形个数
以下n行，每行3个整数h[i],l[i],r[i]表示第i个矩形。
第一行一个整数m，表示节点个数
以下m行，每行一个坐标表示轮廓线上的节点。从左到右遍历轮廓线并顺序输出节点。第一个和最后一个节点的y坐标必然为0。
【样例输入】
2
3 0 2
4 1 3
【样例输入2】
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
【样例输出】
6
0 0
0 3
1 3
1 4
3 4
3 0
【样例输出2】
14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0
对于30%的数据，n<=100
对于另外30%的数据，n<=100000,1<=h[i],l[i],r[i]<=1000
对于100%的数据，1<=n<=100000,1<=h[i]<=10^9,-10^9<=l[i]<r[i]<=10^9
#include <map> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct node { long long int l,r,dis; }; struct node edge[100001]; inline void read_int(long long int &now_); class T_tree { public: int l,r,mid; long long int dis,flag; void mid_() { mid=(l+r)>>1; } void flag_() { flag=0; } void dis_() { dis=0; } }; class T_tree tree[100001*4*2]; long long int n,if_Z,num=0,before=0,before_=0; long long int point[100001*2],ans=0,ans_now[100001*4],ans_dis[100001*4]; char Cget; bool if_fi=true; map<long long int,long long int>if_; inline void read_int(long long int &now_) { now_=0,if_Z=1,Cget=getchar(); while(Cget<‘0‘||Cget>‘9‘) { if(Cget==‘-‘) if_Z=-1; Cget=getchar(); } while(Cget<=‘9‘&&Cget>=‘0‘) { now_=now_*10+Cget-‘0‘; Cget=getchar(); } now_*=if_Z; } inline bool cmp(struct node some1,struct node some2) { return some1.dis<some2.dis; } void tree_build(int now,int l,int r) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis_(); return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); } inline void tree_down(int now) { if(tree[now].l==tree[now].r) return ; tree[now<<1].dis=tree[now].flag; tree[now<<1].flag=tree[now].flag; tree[now<<1|1].dis=tree[now].flag; tree[now<<1|1].flag=tree[now].flag; tree[now].flag_(); } void tree_change(int now,int l,int r,long long int dis) { if(tree[now].l==l&&tree[now].r==r) { tree[now].dis=dis; tree[now].flag=dis; tree_down(now); return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,dis); else if(r<=tree[now].mid) tree_change(now<<1,l,r,dis); else { tree_change(now<<1,l,tree[now].mid,dis); tree_change(now<<1|1,tree[now].mid+1,r,dis); } } int times=0; void tree_check(int now) { if(tree[now].l==tree[now].r) { if(tree[now].dis!=before) { ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } return ; } if(tree[now].flag) tree_down(now); tree_check(now<<1),tree_check(now<<1|1); } int main() { read_int(n); for(int i=1;i<=n;i++) { read_int(edge[i].dis),read_int(edge[i].l),read_int(edge[i].r); if_[edge[i].l]=edge[i].l,if_[edge[i].r]=edge[i].r; } for(map<long long int,long long int>::iterator it=if_.begin();it!=if_.end();it++) { point[++num]=it->first; it->second=num; } tree_build(1,1,num+1); sort(edge+1,edge+n+1,cmp); for(int i=1;i<=n;i++) { tree_change(1,if_[edge[i].l],if_[edge[i].r]-1,edge[i].dis); } tree_check(1); printf("%lld\n",ans); for(int i=1;i<=ans;i++) printf("%lld %lld\n",ans_now[i],ans_dis[i]); return 0; }
附失败代码（>.<）：
#include <map> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct node { int l,r,dis; }; struct node edge[100001]; inline void read_int(int &now_); class T_tree { public: int l,r,mid,dis,flag; void mid_() { mid=(l+r)>>1; } void flag_() { flag=0; } void dis_() { //read_int(dis); dis=0; } }; class T_tree tree[100001*4*2]; class T_tree ok[100001*4*2]; int n,if_Z,num=0,before=0,before_=0; int point[100001*2],ans=0,ans_now[100001*2+1000],ans_dis[100001*2+1000]; char Cget; bool if_fi=true; map<int,int>if_; inline void read_int(int &now_) { now_=0,if_Z=1,Cget=getchar(); while(Cget<‘0‘||Cget>‘9‘) { if(Cget==‘-‘) if_Z=-1; Cget=getchar(); } while(Cget<=‘9‘&&Cget>=‘0‘) { now_=now_*10+Cget-‘0‘; Cget=getchar(); } now_*=if_Z; } inline bool cmp(struct node some1,struct node some2) { return some1.dis<some2.dis; } void ok_build(int now,int l,int r) { ok[now].l=l,ok[now].r=r; if(l==r) return ; ok[now].mid_(); ok_build(now<<1,l,ok[now].mid); ok_build(now<<1|1,ok[now].mid+1,r); } void ok_down(int now) { if(ok[now].l==ok[now].r) return ; ok[now<<1].dis=ok[now].flag; ok[now<<1].flag=ok[now].flag; ok[now<<1|1].dis=ok[now].flag; ok[now<<1|1].flag=ok[now].flag; ok[now].flag=0; } void ok_change(int now,int l,int r) { if(ok[now].dis) return ; if(ok[now].l==ok[now].r) { ok[now].dis=1; ok[now].flag=1; ok_down(now); return ; } if(ok[now].flag) ok_down(now); if(l>ok[now].mid) ok_change(now<<1|1,l,r); else if(r<=ok[now].mid) ok_change(now<<1,l,r); else { ok_change(now<<1,l,ok[now].mid); ok_change(now<<1|1,ok[now].mid+1,r); } } bool ok_ko(int now,int to) { if(ok[now].dis) return true; if(ok[now].l==ok[now].r&&ok[now].l==to) { return false; } if(ok[now].flag) ok_down(now); if(ok[now].l>to) return ok_ko(now<<1|1,to); else return ok_ko(now<<1,to); } void tree_build(int now,int l,int r) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis_(); return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); } inline void tree_down(int now) { if(tree[now].l==tree[now].r) return ; tree[now<<1].dis=tree[now].flag; tree[now<<1].flag=tree[now].flag; tree[now<<1|1].dis=tree[now].flag; tree[now<<1|1].flag=tree[now].flag; tree[now].flag_(); } void tree_change(int now,int l,int r,int dis) { if(tree[now].l==l&&tree[now].r==r) { tree[now].dis=dis; tree[now].flag=dis; tree_down(now); return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,dis); else if(r<=tree[now].mid) tree_change(now<<1,l,r,dis); else { tree_change(now<<1,l,tree[now].mid,dis); tree_change(now<<1|1,tree[now].mid+1,r,dis); } } int times=0; void tree_check(int now) { if(tree[now].l==tree[now].r) { /*if(tree[now].dis!=before_) { times++; if(times==1) { printf("%d %d\n",point[tree[now].l],before); printf("%d %d\n",point[tree[now].l],tree[now].dis); } else { printf("%d %d\n",point[tree[now].l],tree[now].dis); } before_=tree[now].dis; }*/ //printf("(%d,%d)",point[tree[now].l],tree[now].dis); if(tree[now].l==num+1) { if(before!=0) { //printf("%d %d\n",point[num],before); //printf("%d %d\n",point[num],0); ans_now[++ans]=point[num]; ans_dis[ans]=before; ans_now[++ans]=point[num]; ans_dis[ans]=0; } } else { if(ok_ko(1,tree[now].l-1)) { if(tree[now].dis!=before) { //printf("%d %d\n%d %d\n",point[tree[now].l],before,point[tree[now].l],tree[now].dis); ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } } else { if(before!=0) { //printf("%d %d\n",point[tree[now].l-1],point[tree[now].l]); ans_now[++ans]=point[tree[now].l-1]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l-1]; ans_dis[ans]=0; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=0; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } } } //printf("(%d %d)\n",point[tree[now].l],tree[now].dis); return ; } if(tree[now].flag) tree_down(now); tree_check(now<<1),tree_check(now<<1|1); } int main() { read_int(n); for(int i=1;i<=n;i++) { read_int(edge[i].dis),read_int(edge[i].l),read_int(edge[i].r); if_[edge[i].l]=edge[i].l,if_[edge[i].r]=edge[i].r; } // printf("\n\n"); for(map<int,int>::iterator it=if_.begin();it!=if_.end();it++) { point[++num]=it->first; it->second=num; // printf("%d %d\n",num,point[num]); } tree_build(1,1,num+1); ok_build(1,0,num-1); ok_change(1,0,0); sort(edge+1,edge+n+1,cmp); for(int i=1;i<=n;i++) { printf("%d %d\n",if_[edge[i].l],if_[edge[i].r]); } printf("\n\n"); for(int i=1;i<=n;i++) { //printf("%d %d %d\n\n",if_[edge[i].l],if_[edge[i].r],edge[i].dis); tree_change(1,if_[edge[i].l],if_[edge[i].r],edge[i].dis); ok_change(1,if_[edge[i].l],if_[edge[i].r]-1); printf("%d %d\n",if_[edge[i].l],if_[edge[i].r]-1); //ans=0; //before=0; //tree_check(1); //printf("\n"); //printf("%d %d %d\n",if_[edge[i].l],if_[edge[i].r],edge[i].dis); } printf("\n\n"); //ans=0; //before=0; tree_check(1); //printf("\n\n"); printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d %d\n",ans_now[i],ans_dis[i]); return 0; }
原文：http://www.cnblogs.com/IUUUUUUUskyyy/p/6254196.html
