这个sb题目，剧毒。。。
STL大法好
首先，我准备用经典的线段树优化扫描线来做。之前的矩形周长把我困了数天导致我胸有成竹。
然后，敲代码半小时，调试半个月......这个，sb，怎么改都是0分＋2个RE...
然后我爆炸了，请胡雨菲来帮忙。他还是提议我用set做。然后就set了...
跑的贼慢，不过90分，第八个点日常RE...
但是了解了一点set的用法，让我慢慢道来(嘿)
首先，可以看这个博客。
我自己的理解：
1，这是一种功能有限的搜索树。
2，它有序，资瓷插入删除，但是缓慢
3，这东西是返回指针的。
然后，反正这个set很naive就是了。
看下面一段代码：
1 #include <cstdio>
2 #include <set>
3 using namespace std;
4 set<int>s;
5 int main()
6 {
7 s.insert(22);
8 s.insert(24);
9 s.insert(32);
10 s.insert(15);
11 printf("%d
",*s.end());
12 printf("%d
",*s.rbegin());
13 return 0;
14 }
输出：
4
32
好，大致理解了吧。
1 #include <cstdio> 2 #include <set> 3 using namespace std; 4 set<int>s; 5 int main() 6 { 7 s.insert(22); 8 s.insert(24); 9 s.insert(32); 10 s.insert(15); 11 set<int>::iterator iter; 12 for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter); 13 printf(" "); 14 s.erase(24); 15 for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter); 16 s.erase(s.find(22)); 17 printf(" "); 18 for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter); 19 return 0; 20 }
输出：
15 22 24 32
15 22 32
15 32
这里说一下思路：我惯用的手法，重载运算符加优先队列存边。先出x小的，先出入边，入边先高，出边先低。然后如果某次出边后x和h都改变了就记录答案。
那么来看看我的90分代码。如果有机会A掉我再来改。
1 #include <cstdio>
2 #include <set>
3 #include <queue>
4 #include <algorithm>
5 using namespace std;
6 int x[200010],k;
7 int ans[200010][2],ansk;
8 int cnt[200010];
9 struct Edge
10 {
11 int x,high,flag;
12 bool operator < (const Edge &a) const
13 {
14 if(this->x!=a.x) return this->x>a.x;
15 if(this->flag!=a.flag) return this->flag<a.flag;
16 if(a.flag==1) return this->high<a.high;
17 return this->high>a.high;
18 }
19 };
20 priority_queue<Edge>p;
21 set<int>s;
22 void add_e(int high,int l,int r)
23 {
24 Edge ll,rr;
25 ll.flag=1;
26 rr.flag=-1;
27 ll.high=high;
28 rr.high=high;
29 ll.x=l;
30 rr.x=r;
31 p.push(ll);
32 p.push(rr);
33 return;
34 }
35 int main()
36 {
37 int n,xx,y,z;
38 scanf("%d",&n);
39 for(int i=1;i<=n;i++)
40 {
41 scanf("%d%d%d",&xx,&y,&z);
42 add_e(xx,y,z);
43 x[i]=xx;
44 }
45 sort(x+1,x+n+1);
46 for(int i=1;i<=n;i++) if(x[i]!=x[i-1]) x[++k]=x[i];
47 //for(int i=1;i<=k;i++) printf("%d ",x[i]);
48 //printf("
");
49 Edge e;int lastx=-0x3f3f3f3f,lasth=0;
50 s.insert(0);
51 while(!p.empty())
52 {
53 e=p.top();
54 p.pop();
55 int h=e.high;
56 //printf("h:%d
",h);
57 h = upper_bound(x+1,x+1+k,h) - x - 1 ;
58 //printf("h:%d
",h);
59 if(e.flag==1)
60 {
61 if(!cnt[h]) s.insert(h);
62 cnt[h]++;
63 if( (*s.rbegin()!=lasth) && (e.x!=lastx) )
64 {
65 //printf("new ans!%d %d
",e.x,x[*s.rbegin()]);
66 ans[++ansk][0]=e.x;
67 ans[ansk][1]=lasth;
68 ans[++ansk][0]=e.x;
69 ans[ansk][1]=*s.rbegin();
70 lasth=*s.rbegin();
71 lastx=e.x;
72 }
73 }
74 else
75 {
76 cnt[h]--;
77 if(!cnt[h]) s.erase(s.find(h));
78 if(*s.rbegin()!=lasth&&e.x!=lastx)
79 {
80 //printf("new ans!%d %d
",e.x,x[*s.rbegin()]);
81 ans[++ansk][0]=e.x;
82 ans[ansk][1]=lasth;
83 ans[++ansk][0]=e.x;
84 ans[ansk][1]=*s.rbegin();
85 lasth=*s.rbegin();
86 lastx=e.x;
87 }
88 }
89 }
90 printf("%d
",ansk);
91 for(int i=1;i<=ansk;i++) printf("%d %d
",ans[i][0],x[ans[i][1]]);
92 return 0;
93 }
还用到了离散化，具体看代码吧。
原来的naive爆0代码
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 using namespace std; 5 int x[200010],k,ans[100010][2],ansk; 6 struct Edge 7 { 8 int x,flag,high; 9 bool operator < (const Edge &a) const /// !!!! 10 { 11 if(this->x!=a.x)return this->x>a.x; 12 if(this->flag!=a.flag)return this->flag<a.flag; 13 if(this->flag==1) return this->high<a.high; 14 return this->high>a.high; 15 } 16 }; 17 priority_queue<Edge>p; 18 int c[500010],len[500010]; 19 void add_e(int high,int l,int r) 20 { 21 Edge ll,rr; 22 ll.x=l; 23 rr.x=r; 24 ll.high=high; 25 rr.high=high; 26 ll.flag=1; 27 rr.flag=-1; 28 p.push(ll); 29 p.push(rr); 30 return; 31 } 32 33 void update(int l,int r,int o) 34 { 35 if(c[o]>0) /// !!! 36 { 37 if(l!=r)len[o]=x[r]-x[l];/// ! 38 else if(l)len[o]=x[r]-x[l-1]; 39 else len[o]=x[r]; 40 } 41 else if(l==r) len[o]=0; 42 else len[o]=len[o<<1]+len[o<<1|1]; 43 return; 44 45 } 46 47 void add(int L,int R,int v,int l,int r,int o) 48 { 49 if(L<=l && r<=R) 50 { 51 c[o]+=v; 52 update(l,r,o); 53 return; 54 } 55 if(r<L || R<l) return; 56 int mid=(l+r)>>1; 57 add(L,R,v,l,mid,o<<1); 58 add(L,R,v,mid+1,r,o<<1|1); 59 update(l,r,o); 60 return; 61 } 62 63 int main() 64 { 65 int n,xx,y,z; 66 scanf("%d",&n); 67 for(int i=1; i<=n; i++) 68 { 69 scanf("%d%d%d",&xx,&y,&z); 70 add_e(xx,y,z); 71 x[i]=xx; 72 } 73 sort(x+1,x+1+n); 74 for(int i=1; i<=n; i++) 75 { 76 if(x[i]!=x[i-1]) x[++k]=x[i]; 77 } ///离散化去重 78 Edge e; 79 int poi; 80 int lastx=-0x3f3f3f3f,lasth=0; 81 82 while(!p.empty()) 83 { 84 e=p.top(); 85 p.pop(); 86 poi=upper_bound(x+1,x+k+1,e.high)-x-1; 87 //printf("add:0 %d %d 0 %d 1 ",poi,e.flag,k); 88 add(0,poi,e.flag,0,k,1); 89 //printf("len:%d ",len[1]); 90 if(len[1]!=lasth&&e.x!=lastx) 91 //if((e.x!=lastx||e.x==0) && len[1]!=lasth) ///!!!serious! 92 { 93 //printf("new ans! "); 94 ans[++ansk][0]=e.x; 95 ans[ansk][1]=lasth; 96 ans[++ansk][0]=e.x; 97 ans[ansk][1]=len[1]; 98 lastx=e.x; 99 lasth=len[1]; 100 } 101 /** 102 if(e.flag==1) ///++ 103 { 104 if(lasth==len[1]) continue;///高度没变，continue; 105 106 107 } 108 else ///-- 109 { 110 111 } 112 */ 113 } 114 printf("%d ",ansk); 115 for(int i=1; i<=ansk; i++) printf("%d %d ",ans[i][0],ans[i][1]); 116 return 0; 117 }
再见。
不再见
A了，看看代码有什么变化？
1 #include <cstdio> 2 #include <set> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 long long int x[2000100],k; 7 long long int ans[2000100][2],ansk; 8 long long int cnt[2000100]; 9 struct Edge 10 { 11 long long int x,high,flag; 12 bool operator < (const Edge &a) const 13 { 14 if(this->x!=a.x) return this->x>a.x; 15 if(this->flag!=a.flag) return this->flag<a.flag; 16 if(a.flag==1) return this->high<a.high; 17 return this->high>a.high; 18 } 19 }; 20 priority_queue<Edge>p; 21 set<long long int>s; 22 void add_e(long long int high,long long int l,long long int r) 23 { 24 Edge ll,rr; 25 ll.flag=1; 26 rr.flag=-1; 27 ll.high=high; 28 rr.high=high; 29 ll.x=l; 30 rr.x=r; 31 p.push(ll); 32 p.push(rr); 33 return; 34 } 35 int main() 36 { 37 long long int n,xx,y,z; 38 scanf("%lld",&n); 39 for(int i=1;i<=n;i++) 40 { 41 scanf("%lld%lld%lld",&xx,&y,&z); 42 add_e(xx,y,z); 43 x[i]=xx; 44 } 45 sort(x+1,x+n+1); 46 for(int i=1;i<=n;i++) if(x[i]!=x[i-1]) x[++k]=x[i]; 47 //for(int i=1;i<=k;i++) printf("%d ",x[i]); 48 //printf(" "); 49 Edge e;long long int lastx=-0x3f3f3f3f,lasth=0; 50 s.insert(0); 51 while(!p.empty()) 52 { 53 e=p.top(); 54 p.pop(); 55 long long int h=e.high; 56 //printf("h:%d ",h); 57 h = upper_bound(x+1,x+1+k,h) - x - 1 ; 58 //printf("h:%d ",h); 59 if(e.flag==1) 60 { 61 if(!cnt[h]) s.insert(h); 62 cnt[h]++; 63 if( (*s.rbegin()!=lasth) && (e.x!=lastx) ) 64 { 65 //printf("new ans!%d %d ",e.x,x[*s.rbegin()]); 66 ans[++ansk][0]=e.x; 67 ans[ansk][1]=lasth; 68 ans[++ansk][0]=e.x; 69 ans[ansk][1]=*s.rbegin(); 70 lasth=*s.rbegin(); 71 lastx=e.x; 72 } 73 } 74 else 75 { 76 cnt[h]--; 77 if(!cnt[h]) s.erase(s.find(h)); 78 if(*s.rbegin()!=lasth&&e.x!=lastx) 79 { 80 //printf("new ans!%d %d ",e.x,x[*s.rbegin()]); 81 ans[++ansk][0]=e.x; 82 ans[ansk][1]=lasth; 83 ans[++ansk][0]=e.x; 84 ans[ansk][1]=*s.rbegin(); 85 lasth=*s.rbegin(); 86 lastx=e.x; 87 } 88 } 89 } 90 printf("%lld ",ansk); 91 for(int i=1;i<=ansk;i++) printf("%lld %lld ",ans[i][0],x[ans[i][1]]); 92 return 0; 93 }