显然两维是独立的，不妨考虑其中一维的答案
将其离散，枚举交包含的某一段（若不存在即交为空），进而即可确定所有段的方向，用线段树维护取到最大值的位置数即可
时间复杂度为$o(n\log n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 500005
4 #define ll long long
5 #define pii pair<int,int>
6 #define fi first
7 #define se second
8 #define L (k<<1)
9 #define R (L+1)
10 #define mid (l+r>>1)
11 int n,X,Y,M,vis[N],tag[N<<3],mx[N<<3],f[N<<3],dta[N<<1];
12 ll ans;
13 vector<int>v0;
14 vector<pair<int,int> >v;
15 struct Data{
16 int l,r;
17 }x[N],y[N],a[N];
18 void build(int k,int l,int r){
19 if (l==r){
20 mx[k]=n-dta[l],f[k]=v0[l+1]-v0[l];
21 return;
22 }
23 build(L,l,mid),build(R,mid+1,r);
24 mx[k]=max(mx[L],mx[R]),f[k]=0;
25 if (mx[k]==mx[L])f[k]+=f[L];
26 if (mx[k]==mx[R])f[k]+=f[R];
27 mx[k]+=tag[k];
28 }
29 void update(int k,int l,int r,int x,int y,int z){
30 if ((l>y)||(x>r))return;
31 if ((x<=l)&&(r<=y)){
32 tag[k]+=z,mx[k]+=z;
33 return;
34 }
35 update(L,l,mid,x,y,z);
36 update(R,mid+1,r,x,y,z);
37 mx[k]=max(mx[L],mx[R]),f[k]=0;
38 if (mx[k]==mx[L])f[k]+=f[L];
39 if (mx[k]==mx[R])f[k]+=f[R];
40 mx[k]+=tag[k];
41 }
42 void add(int id){
43 if (!vis[id]){
44 tag[1]--,mx[1]--;
45 update(1,0,M,a[id].l,a[id].r-1,2);
46 vis[id]=1;
47 }
48 else{
49 tag[1]++,mx[1]++;
50 update(1,0,M,a[id].l,a[id].r-1,-2);
51 vis[id]=0;
52 }
53 }
54 int calc(int m){
55 v.clear(),v0.clear();
56 memset(vis,0,sizeof(vis));
57 memset(tag,0,sizeof(tag));
58 memset(dta,0,sizeof(dta));
59 for(int i=1;i<=n;i++){
60 v.push_back(make_pair(a[i].l,i));
61 v.push_back(make_pair(a[i].r,i));
62 }
63 sort(v.begin(),v.end());
64 v0.push_back(0);
65 for(int i=0;i<(n<<1);i++)
66 if ((!i)||(v[i].fi!=v[i-1].fi))v0.push_back(v[i].fi);
67 M=v0.size()-1,v0.push_back(m);
68 for(int i=1;i<=n;i++){
69 a[i].l=lower_bound(v0.begin(),v0.end(),a[i].l)-v0.begin();
70 a[i].r=lower_bound(v0.begin(),v0.end(),a[i].r)-v0.begin();
71 dta[a[i].l]++,dta[a[i].r]--;
72 }
73 for(int i=1;i<=M;i++)dta[i]+=dta[i-1];
74 build(1,0,M);
75 int ans=0;
76 for(int i=0;i<(n<<1);i++){
77 add(v[i].se);
78 if (mx[1]==n)ans=max(ans,f[1]);
79 }
80 return ans;
81 }
82 int main(){
83 scanf("%d%d%d",&n,&X,&Y);
84 for(int i=1;i<=n;i++){
85 scanf("%d%d%d%d",&x[i].l,&y[i].l,&x[i].r,&y[i].r);
86 if (x[i].l>x[i].r)swap(x[i].l,x[i].r);
87 if (y[i].l>y[i].r)swap(y[i].l,y[i].r);
88 }
89 memcpy(a,x,sizeof(a));
90 ans=calc(X);
91 memcpy(a,y,sizeof(a));
92 ans*=calc(Y);
93 printf("%lld\n",ans);
94 return 0;
95 }
View Code
另外，还有一个更加巧妙的做法：注意到每一个区间的两种选择是互补的，对每一段区间异或一个随机值，那么可以认为众数的出现次数即为答案，这直接排序即可得到
关于错误的概率，并不太会分析，反正大概就对了QAQ
时间复杂度为$o(n\log n)$，也可以通过（比第一种算法常数更小）
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 500005
4 #define ll long long
5 #define llu unsigned ll
6 vector<int>v;
7 int n,X,Y;
8 ll ans;
9 llu dta[N<<1];
10 pair<llu,int>P[N];
11 struct Data{
12 int l,r;
13 }x[N],y[N],a[N];
14 llu rnd(){
15 llu x=0;
16 for(int i=0;i<4;i++)x=((x<<16)|rand()%(1<<16));
17 return x;
18 }
19 int calc(int m){
20 v.clear();
21 memset(dta,0,sizeof(dta));
22 for(int i=1;i<=n;i++){
23 v.push_back(a[i].l);
24 v.push_back(a[i].r);
25 }
26 v.push_back(0),v.push_back(m);
27 sort(v.begin(),v.end());
28 for(int i=1;i<=n;i++){
29 a[i].l=lower_bound(v.begin(),v.end(),a[i].l)-v.begin();
30 a[i].r=lower_bound(v.begin(),v.end(),a[i].r)-v.begin();
31 llu p=rnd();
32 dta[a[i].l]^=p,dta[a[i].r]^=p;
33 }
34 for(int i=1;i<=(n<<1);i++)dta[i]^=dta[i-1];
35 for(int i=0;i<=(n<<1);i++)P[i]=make_pair(dta[i],v[i+1]-v[i]);
36 sort(P,P+(n<<1)+1);
37 int cnt=0,ans=0;
38 for(int i=0;i<=(n<<1);i++){
39 cnt+=P[i].second;
40 if ((i==(n<<1))||(P[i+1].first!=P[i].first)){
41 ans=max(ans,cnt);
42 cnt=0;
43 }
44 }
45 return ans;
46 }
47 int main(){
48 srand(time(0));
49 scanf("%d%d%d",&n,&X,&Y);
50 for(int i=1;i<=n;i++){
51 scanf("%d%d%d%d",&x[i].l,&y[i].l,&x[i].r,&y[i].r);
52 if (x[i].l>x[i].r)swap(x[i].l,x[i].r);
53 if (y[i].l>y[i].r)swap(y[i].l,y[i].r);
54 }
55 memcpy(a,x,sizeof(a));
56 ans=calc(X);
57 memcpy(a,y,sizeof(a));
58 ans*=calc(Y);
59 printf("%lld\n",ans);
60 return 0;
61 }
View Code