[loj3220]Terytoria

显然两维是独立的，不妨考虑其中一维的答案

将其离散，枚举交包含的某一段（若不存在即交为空），进而即可确定所有段的方向，用线段树维护取到最大值的位置数即可

时间复杂度为$o(n\log n)$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 500005
 4 #define ll long long
 5 #define pii pair
 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 vectorint,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 } 

另外，还有一个更加巧妙的做法：注意到每一个区间的两种选择是互补的，对每一段区间异或一个随机值，那么可以认为众数的出现次数即为答案，这直接排序即可得到

关于错误的概率，并不太会分析，反正大概就对了QAQ

时间复杂度为$o(n\log n)$，也可以通过（比第一种算法常数更小）

 1 #include
 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 pairint>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 }