这个sb题目，剧毒。。。
STL大法好
首先，我准备用经典的线段树优化扫描线来做。之前的矩形周长把我困了数天导致我胸有成竹。
然后，敲代码半小时，调试半个月......这个，sb，怎么改都是0分＋2个RE...
然后我爆炸了，请胡雨菲来帮忙。他还是提议我用set做。然后就set了...
跑的贼慢，不过90分，第八个点日常RE...
但是了解了一点set的用法，让我慢慢道来(嘿)
首先，可以看这个博客。
我自己的理解：
1，这是一种功能有限的搜索树。
2，它有序，资瓷插入删除，但是缓慢
3，这东西是返回指针的。
然后，反正这个set很naive就是了。
看下面一段代码：
#include <cstdio>
#include <set>
using namespace std;
set<int>s;
int main()
{
s.insert();
s.insert();
s.insert();
s.insert();
printf("%d\n",*s.end());
printf("%d\n",*s.rbegin());
return ;
}
set用法①
输出：
4
32
好，大致理解了吧。
#include <cstdio>
#include <set>
using namespace std;
set<int>s;
int main()
{
s.insert();
s.insert();
s.insert();
s.insert();
set<int>::iterator iter;
for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);
printf("\n");
s.erase();
for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);
s.erase(s.find());
printf("\n");
for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);
return ;
}
set用法②
输出：
15 22 24 32
15 22 32
15 32
这里说一下思路：我惯用的手法，重载运算符加优先队列存边。先出x小的，先出入边，入边先高，出边先低。然后如果某次出边后x和h都改变了就记录答案。
那么来看看我的90分代码。如果有机会A掉我再来改。
#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int x[],k;
int ans[][],ansk;
int cnt[];
struct Edge
{
int x,high,flag;
bool operator < (const Edge &a) const
{
if(this->x!=a.x) return this->x>a.x;
if(this->flag!=a.flag) return this->flag<a.flag;
if(a.flag==) return this->high<a.high;
return this->high>a.high;
}
};
priority_queue<Edge>p;
set<int>s;
void add_e(int high,int l,int r)
{
Edge ll,rr;
ll.flag=;
rr.flag=-;
ll.high=high;
rr.high=high;
ll.x=l;
rr.x=r;
p.push(ll);
p.push(rr);
return;
}
int main()
{
int n,xx,y,z;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&xx,&y,&z);
add_e(xx,y,z);
x[i]=xx;
}
sort(x+,x+n+);
for(int i=;i<=n;i++) if(x[i]!=x[i-]) x[++k]=x[i];
//for(int i=1;i<=k;i++) printf("%d ",x[i]);
//printf("\n");
Edge e;int lastx=-0x3f3f3f3f,lasth=;
s.insert();
while(!p.empty())
{
e=p.top();
p.pop();
int h=e.high;
//printf("h:%d\n",h);
h = upper_bound(x+,x++k,h) - x - ;
//printf("h:%d\n",h);
if(e.flag==)
{
if(!cnt[h]) s.insert(h);
cnt[h]++;
if( (*s.rbegin()!=lasth) && (e.x!=lastx) )
{
//printf("new ans!%d %d\n",e.x,x[*s.rbegin()]);
ans[++ansk][]=e.x;
ans[ansk][]=lasth;
ans[++ansk][]=e.x;
ans[ansk][]=*s.rbegin();
lasth=*s.rbegin();
lastx=e.x;
}
}
else
{
cnt[h]--;
if(!cnt[h]) s.erase(s.find(h));
if(*s.rbegin()!=lasth&&e.x!=lastx)
{
//printf("new ans!%d %d\n",e.x,x[*s.rbegin()]);
ans[++ansk][]=e.x;
ans[ansk][]=lasth;
ans[++ansk][]=e.x;
ans[ansk][]=*s.rbegin();
lasth=*s.rbegin();
lastx=e.x;
}
}
}
printf("%d\n",ansk);
for(int i=;i<=ansk;i++) printf("%d %d\n",ans[i][],x[ans[i][]]);
return ;
}
90分代码，跑的贼慢
还用到了离散化，具体看代码吧。
原来的naive爆0代码
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int x[],k,ans[][],ansk;
struct Edge
{
int x,flag,high;
bool operator < (const Edge &a) const /// !!!!
{
if(this->x!=a.x)return this->x>a.x;
if(this->flag!=a.flag)return this->flag<a.flag;
if(this->flag==) return this->high<a.high;
return this->high>a.high;
}
};
priority_queue<Edge>p;
int c[],len[];
void add_e(int high,int l,int r)
{
Edge ll,rr;
ll.x=l;
rr.x=r;
ll.high=high;
rr.high=high;
ll.flag=;
rr.flag=-;
p.push(ll);
p.push(rr);
return;
} void update(int l,int r,int o)
{
if(c[o]>) /// !!!
{
if(l!=r)len[o]=x[r]-x[l];/// !
else if(l)len[o]=x[r]-x[l-];
else len[o]=x[r];
}
else if(l==r) len[o]=;
else len[o]=len[o<<]+len[o<<|];
return; } void add(int L,int R,int v,int l,int r,int o)
{
if(L<=l && r<=R)
{
c[o]+=v;
update(l,r,o);
return;
}
if(r<L || R<l) return;
int mid=(l+r)>>;
add(L,R,v,l,mid,o<<);
add(L,R,v,mid+,r,o<<|);
update(l,r,o);
return;
} int main()
{
int n,xx,y,z;
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d%d%d",&xx,&y,&z);
add_e(xx,y,z);
x[i]=xx;
}
sort(x+,x++n);
for(int i=; i<=n; i++)
{
if(x[i]!=x[i-]) x[++k]=x[i];
} ///离散化去重
Edge e;
int poi;
int lastx=-0x3f3f3f3f,lasth=; while(!p.empty())
{
e=p.top();
p.pop();
poi=upper_bound(x+,x+k+,e.high)-x-;
//printf("add:0 %d %d 0 %d 1\n",poi,e.flag,k);
add(,poi,e.flag,,k,);
//printf("len:%d\n",len[1]);
if(len[]!=lasth&&e.x!=lastx)
//if((e.x!=lastx||e.x==0) && len[1]!=lasth) ///!!!serious!
{
//printf("new ans!\n");
ans[++ansk][]=e.x;
ans[ansk][]=lasth;
ans[++ansk][]=e.x;
ans[ansk][]=len[];
lastx=e.x;
lasth=len[];
}
/**
if(e.flag==1) ///++
{
if(lasth==len[1]) continue;///高度没变，continue; }
else ///--
{ }
*/
}
printf("%d\n",ansk);
for(int i=; i<=ansk; i++) printf("%d %d\n",ans[i][],ans[i][]);
return ;
}
！！！！！!!!!!!!
再见。
不再见
A了，看看代码有什么变化？
#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
long long int x[],k;
long long int ans[][],ansk;
long long int cnt[];
struct Edge
{
long long int x,high,flag;
bool operator < (const Edge &a) const
{
if(this->x!=a.x) return this->x>a.x;
if(this->flag!=a.flag) return this->flag<a.flag;
if(a.flag==) return this->high<a.high;
return this->high>a.high;
}
};
priority_queue<Edge>p;
set<long long int>s;
void add_e(long long int high,long long int l,long long int r)
{
Edge ll,rr;
ll.flag=;
rr.flag=-;
ll.high=high;
rr.high=high;
ll.x=l;
rr.x=r;
p.push(ll);
p.push(rr);
return;
}
int main()
{
long long int n,xx,y,z;
scanf("%lld",&n);
for(int i=;i<=n;i++)
{
scanf("%lld%lld%lld",&xx,&y,&z);
add_e(xx,y,z);
x[i]=xx;
}
sort(x+,x+n+);
for(int i=;i<=n;i++) if(x[i]!=x[i-]) x[++k]=x[i];
//for(int i=1;i<=k;i++) printf("%d ",x[i]);
//printf("\n");
Edge e;long long int lastx=-0x3f3f3f3f,lasth=;
s.insert();
while(!p.empty())
{
e=p.top();
p.pop();
long long int h=e.high;
//printf("h:%d\n",h);
h = upper_bound(x+,x++k,h) - x - ;
//printf("h:%d\n",h);
if(e.flag==)
{
if(!cnt[h]) s.insert(h);
cnt[h]++;
if( (*s.rbegin()!=lasth) && (e.x!=lastx) )
{
//printf("new ans!%d %d\n",e.x,x[*s.rbegin()]);
ans[++ansk][]=e.x;
ans[ansk][]=lasth;
ans[++ansk][]=e.x;
ans[ansk][]=*s.rbegin();
lasth=*s.rbegin();
lastx=e.x;
}
}
else
{
cnt[h]--;
if(!cnt[h]) s.erase(s.find(h));
if(*s.rbegin()!=lasth&&e.x!=lastx)
{
//printf("new ans!%d %d\n",e.x,x[*s.rbegin()]);
ans[++ansk][]=e.x;
ans[ansk][]=lasth;
ans[++ansk][]=e.x;
ans[ansk][]=*s.rbegin();
lasth=*s.rbegin();
lastx=e.x;
}
}
}
printf("%lld\n",ansk);
for(int i=;i<=ansk;i++) printf("%lld %lld\n",ans[i][],x[ans[i][]]);
return ;
}
就是她