题意：
n<=1e5,abs(x[i]),abs(y[i]<=1e9
思路：这是正解
离散后线段树强打，数据结构越学越傻
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 1100000 21 #define MOD 1000000007 22 #define eps 1e-8 23 #define pi acos(-1) 24 struct arr1 25 { 26 int x1,y1,x2,y2; 27 }a[N]; 28 29 struct arr2 30 { 31 int x,y1,y2,z; 32 }c[N]; 33 34 struct tree 35 { 36 int a,s,x; 37 }t[N<<2]; 38 39 int b[N],d[N],q[N],m; 40 41 int read() 42 { 43 int v=0,f=1; 44 char c=getchar(); 45 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 46 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 47 return v*f; 48 } 49 50 void swap(int &x,int &y) 51 { 52 int t=x;x=y;y=t; 53 } 54 55 int hash1(int x) 56 { 57 int l=1; 58 int r=m; 59 while(l<=r) 60 { 61 int mid=(l+r)>>1; 62 if(b[mid]==x) return d[mid]; 63 if(b[mid]<x) l=mid+1; 64 else r=mid-1; 65 } 66 } 67 68 bool cmp(arr2 a,arr2 b) 69 { 70 return a.x<b.x; 71 } 72 73 void pushdown(int p) 74 { 75 int l=p<<1; 76 int r=l+1; 77 if(!t[p].a) return; 78 t[l].s=t[l].s+t[p].a; 79 t[l].a=t[l].a+t[p].a; 80 t[r].s=t[r].s+t[p].a; 81 t[r].a=t[r].a+t[p].a; 82 t[p].a=0; 83 } 84 85 void pushup(int p) 86 { 87 if(t[p<<1].s<t[p+p+1].s) 88 { 89 t[p].s=t[p+p+1].s; 90 t[p].x=t[p+p+1].x; 91 } 92 else 93 { 94 t[p].s=t[p<<1].s; 95 t[p].x=t[p<<1].x; 96 } 97 } 98 99 void build(int l,int r,int p) 100 { 101 if(l>r) return; 102 t[p].a=0; 103 t[p].x=l; 104 if(l==r) return; 105 int mid=(l+r)>>1; 106 build(l,mid,p<<1); 107 build(mid+1,r,p<<1|1); 108 } 109 110 int query(int l,int r,int x,int y,int p) 111 { 112 if(x<=l&&r<=y) return t[p].s; 113 pushdown(p); 114 int mid=(l+r)>>1; 115 int ret=-1; 116 if(x<=mid) ret=query(l,mid,x,y,p<<1); 117 if(y>mid) 118 { 119 int t=query(mid+1,r,x,y,p<<1|1); 120 if(t>ret) ret=t; 121 } 122 return ret; 123 } 124 125 126 void update(int l,int r,int x,int y,int v,int p) 127 { 128 if(x<=l&&r<=y) 129 { 130 t[p].s+=v; 131 t[p].a+=v; 132 return; 133 } 134 pushdown(p); 135 int mid=(l+r)>>1; 136 if(x<=mid) update(l,mid,x,y,v,p<<1); 137 if(y>mid) update(mid+1,r,x,y,v,p<<1|1); 138 pushup(p); 139 } 140 141 int main() 142 { 143 // freopen("cf1028C.in","r",stdin); 144 // freopen("cf1028C.out","w",stdout); 145 int x; 146 scanf("%d",&x); 147 int k1=x; 148 m=0; 149 int n=0; 150 for(int i=1;i<=x;i++) 151 { 152 scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); 153 b[++m]=a[i].x1; 154 b[++m]=a[i].y1; 155 b[++m]=a[i].x2; 156 b[++m]=a[i].y2; 157 } 158 sort(b+1,b+m+1); 159 d[1]=1; 160 for(int i=2;i<=m;i++) 161 if(b[i]==b[i-1]) d[i]=d[i-1]; 162 else d[i]=d[i-1]+1; 163 q[1]=b[1]; 164 int len=1; 165 for(int i=2;i<=m;i++) 166 if(b[i]!=b[i-1]) q[++len]=b[i]; 167 168 for(int i=1;i<=x;i++) 169 { 170 c[++n].x=hash1(a[i].x1); 171 c[n].y1=hash1(a[i].y1); 172 c[n].y2=hash1(a[i].y2); 173 c[n].z=1; 174 c[++n].x=hash1(a[i].x2)+1; 175 c[n].y1=hash1(a[i].y1); 176 c[n].y2=hash1(a[i].y2); 177 c[n].z=-1; 178 } 179 sort(c+1,c+n+1,cmp); 180 int line=0; 181 int row=0; 182 for(int i=1;i<=n;i++) 183 { 184 line=max(line,c[i].x); 185 row=max(row,c[i].y2); 186 } 187 build(1,row,1); 188 189 190 int j=1; 191 for(int i=1;i<=line;i++) 192 { 193 while(j<=n&&c[j].x==i) 194 { 195 update(1,row,c[j].y1,c[j].y2,c[j].z,1); 196 // printf("%d %d %d ",c[j].y1,c[j].y2,c[j].z); 197 j++; 198 } 199 int k=query(1,row,1,row,1); 200 //printf("%d %d ",i,k); 201 if(k>=k1-1) 202 { 203 // int p=find(1,row,1,row,1); 204 int p=t[1].x; 205 // printf("%d %d ",i,p); 206 int x=q[i]; 207 int y=q[p]; 208 printf("%d %d ",x,y); 209 return 0; 210 } 211 } 212 return 0; 213 }