题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3356
先做下离散化，然后按照左边从小到大排序，碰到左边缘时将上下边分别插入到两个树状数组中，当碰到右边缘时，找到有多少个下边缘在当前的围栏的上边缘下，再减去有多少个上边缘在当前的围栏下边缘下，这样就是有多少个围栏围住了当前的围栏，因为保证了围栏不相交，不重叠
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<bits/stdc++.h> #define MAXN 500050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int x,up,down; bool add; }a[MAXN]; int n,m,sumup[MAXN],sumdown[MAXN],val[MAXN],ans=-1,num=0; bool cmp(node aa,node bb){ return aa.x<bb.x; } inline void add_up(int x,int k){ for(int i=x; i<=m; i+=i&-i)sumup[i]+=k; } inline void add_down(int x,int k){ for(int i=x; i<=m; i+=i&-i)sumdown[i]+=k; } inline int query_down(int x){ int ret=0; for(int i=x; i; i-=i&-i)ret+=sumdown[i]; return ret; } inline int query_up(int x){ int ret=0; for(int i=x; i; i-=i&-i)ret+=sumup[i]; return ret; } inline int Find(int x){ int l=1,r=m,ret,mid; while(l<=r){ mid=(l+r)/2; if(val[mid]<=x)ret=mid,l=mid+1; else r=mid-1; } return ret; } int main(){ n=rd(); for(int i=1; i<=n; i++){ int x=rd(),y=rd(),xx=rd(),yy=rd(); a[++m].x=x,a[m].down=val[m]=y,a[m].up=yy;a[m].add=1; a[++m].x=xx,a[m].down=y,a[m].up=val[m]=yy; } sort(val+1,val+1+m); sort(a+1,a+1+m,cmp); for(int i=1; i<=m; i++){ a[i].up=Find(a[i].up); a[i].down=Find(a[i].down); if(a[i].add)add_up(a[i].up,1),add_down(a[i].down,1); else{ int now=query_down(a[i].up)-query_up(a[i].down-1); if(now>ans)ans=now,num=1; else if(now==ans)num++; add_up(a[i].up,-1); add_down(a[i].down,-1); } } printf("%d %d\n",ans,num); return 0; } |
