/*暴力30分*/ #include<iostream> #include<cstring> #include<cstdio> #include<map> #define maxn 100010 using namespace std; int n,l=0x7fffffff,r=-0x7fffffff; int s,ans1[maxn*5],ans2[maxn*5],h[maxn]; struct node { int li,ri,hi; }p[maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&p[i].hi,&p[i].li,&p[i].ri); l=min(l,p[i].li);r=max(r,p[i].ri); } for(int i=1;i<=n;i++) for(int j=p[i].li;j<p[i].ri;j++) h[j]=max(h[j],p[i].hi); int pre=0; for(int i=l;i<=r;i++) { if(h[i]!=pre) { ans1[++s]=i; ans2[s]=pre; ans1[++s]=i; ans2[s]=h[i]; pre=h[i]; } } printf("%d ",s); for(int i=1;i<=s;i++) printf("%d %d ",ans1[i],ans2[i]); return 0; }
/*神奇的set+sort*/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<set> #define maxn 200010 using namespace std; multiset<int,greater<int> >s; int n,tot,t,ans1[maxn*5],ans2[maxn*5]; struct node { int x,k,b,h; }q[maxn]; int cmp(const node &q1,const node &q2)//关键的cmp { if(q1.x!=q2.x)return q1.x<q2.x; if(q1.k!=q2.k)return q1.k<q2.k;//挨在一起的 先考虑左 后考虑右 就不会把这里的4个点输出 if(q1.k==1)return q1.h>q2.h;//左边 先考虑高的 把低的覆盖了 if(q1.k==2)return q1.h<q2.h;//同理 } int main() { scanf("%d",&n); int l,r,hi; for(int i=1;i<=n;i++) { scanf("%d%d%d",&hi,&l,&r); q[++tot].x=l;q[tot].b=i;q[tot].k=1;q[tot].h=hi; q[++tot].x=r;q[tot].b=i;q[tot].k=2;q[tot].h=hi; } sort(q+1,q+1+tot,cmp); for(int i=1;i<=tot;i++) { if(q[i].k==1) { if(*s.begin()>=q[i].h)s.insert(q[i].h); else { t+=1; ans1[t]=q[i].x;ans2[t]=*s.begin(); t+=1; ans1[t]=q[i].x;ans2[t]=q[i].h; s.insert(q[i].h); } } if(q[i].k==2) { if(*s.begin()==q[i].h&&s.count(q[i].h)==1) { s.erase(s.find(q[i].h)); t+=1; ans1[t]=q[i].x;ans2[t]=q[i].h; t+=1; ans1[t]=q[i].x;ans2[t]=*s.begin(); } else s.erase(s.find(q[i].h)); } } printf("%d ",t); for(int i=1;i<=t;i++) printf("%d %d ",ans1[i],ans2[i]); return 0; }
/* 离散化然后线段树维护每个点的hmax 然后按照打爆力的方法找 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100010 using namespace std; int n,m,num,tot,a[maxn*2],b[maxn*2]; int ans1[maxn*5],ans2[maxn*5],cnt; struct node { int l,r,h; }p[maxn]; struct tree { int l,r,lc,rc,ans,lazy; }t[maxn*4]; int cmp(const node &x,const node &y) { return x.h<y.h; } void Build(int li,int ri) { int k=++tot; t[k].l=li;t[k].r=ri; if(li!=ri-1) { t[k].lc=tot+1;Build(li,(li+ri)/2); t[k].rc=tot+1;Build((li+ri)/2,ri); t[k].ans=max(t[t[k].lc].ans,t[t[k].rc].ans); } else t[k].ans=0; } void updata(int k) { t[t[k].lc].ans=max(t[t[k].lc].ans,t[k].lazy); t[t[k].rc].ans=max(t[t[k].rc].ans,t[k].lazy); t[t[k].lc].lazy=max(t[t[k].lc].lazy,t[k].lazy); t[t[k].rc].lazy=max(t[t[k].rc].lazy,t[k].lazy); t[k].lazy=0; } void Change(int k,int li,int ri,int data) { if(li<=t[k].l&&ri>=t[k].r) { t[k].ans=max(data,t[k].ans); t[k].lazy=max(t[k].lazy,data); return; } if(t[k].lazy)updata(k); int mid=(t[k].l+t[k].r)/2; if(li<mid)Change(t[k].lc,li,ri,data); if(ri>mid)Change(t[k].rc,li,ri,data); t[k].ans=max(t[t[k].lc].ans,t[t[k].rc].ans); } int Query(int k,int p) { if(t[k].l==t[k].r-1)return t[k].ans; if(t[k].lazy)updata(k); int mid=(t[k].l+t[k].r)/2; if(p<mid)return Query(t[k].lc,p); else return Query(t[k].rc,p); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&p[i].h,&p[i].l,&p[i].r); a[++m]=p[i].l;a[++m]=p[i].r; } sort(a+1,a+m+1);sort(p+1,p+1+n,cmp); b[++num]=a[1]; for(int i=2;i<=m;i++) if(a[i]!=a[i-1])b[++num]=a[i]; Build(1,m+1); for(int i=1;i<=n;i++) { int p1=lower_bound(b+1,b+1+num,p[i].l)-b; int p2=lower_bound(b+1,b+1+num,p[i].r)-b; Change(1,p1,p2,p[i].h); } for(int i=1;i<=num;i++) { ans1[i]=b[i];ans2[i]=Query(1,i); if(ans2[i]!=ans2[i-1])cnt++; } printf("%d ",cnt*2); for(int i=1;i<=num;i++) if(ans2[i]!=ans2[i-1]) { printf("%d %d ",ans1[i],ans2[i-1]); printf("%d %d ",ans1[i],ans2[i]); } return 0; }