「题解」PA2019 Terytoria
agicy
·
·
题解
本文将同步发布于：
- 洛谷博客；
- csdn；
- 博客园；
- 因为简书系统升级，所以本文未在简书上发布。
题目
题目链接：洛谷 P5987、LOJ 3320、官网。
题意概述
在二维平面直角坐标系上，有一个长度为 X，宽度为 Y 的地图，注意这个地图的左边界和右边界是连通的，下边界和上边界也是连通的，换言之它是个球形结构。
在这个地图里，有 X\times Y 个格子以及 n 个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标，请问在最好情况下，被所有 n 个矩形都覆盖住的格子数量有多少？
## 题解
### 几何性质
首先不难发现，$x,y$ 两维是独立的。
考虑一个矩形的选取情况，只有 $00,01,10,11$ 四种情况。
然而，两个状态 $0,1$ 相乘即可得到上面的所有状态，因此我们可以两维分开做。
### 枚举答案区间
考虑对于一维的情况，一个点对 $(x_1,y_1),(x_2,y_2)$ 仅对应两种可能 $[x_1,x_2]$ 或者 $[0,x_1)\cup(x_2,x]$。
这两个集合显然不交，因此，我们可以考虑枚举一个区间 $[i,i+1]$，那么可以轻易地确定每个区间的选择方案，因而求出最终的长度。
这个可以离散化后可以用扫描线维护，用线段树维护：
- 查询操作：区间最大值及个数；
- 修改操作：区间加法。
时间复杂度为 $\Theta(n\log_2n)$，可以通过本题。
### 随机算法有前途
我们想到一个简单的方案，如果区间数量 $\leq 64$，那么我们对于第 $i$ 个区间 $[x_1,x_2]$ 内的数，都异或上 $2^i$，那么操作结束之后，所有异或值相同的区间对应的集合选择方案必然相同，换句话说，它们是一块的。
因此，如果区间数量 $\leq 64$，我们只需要求出相同异或值的出现次数的最大值即可。
可是这个题目显然不会有上面那么紧的约束，我们考虑放松约束。
具体地，我们不再强求异或的值为 $2^i$，而是变成一个随机非负整数 $\in[0,2^{64})$。统计答案的方法与之前相同，时间复杂度为 $\Theta(n\log_2n)$，可是正确性呢？
我们的答案出错，是因为有两个不该在同一块的位置经过异或后出现了相同的值，那么我们考虑每一位上异或值相同的概率均为 $\frac{1}{2}$，那么这个算法正确的概率根据生日悖论为：
$$
\prod_{k=0}^{2n-1}(1-\frac{k}{2^{64}})^2
$$
这个数字经过计算可以知道非常接近 $1$，正确性得到保证。
### 参考程序
线段树的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
static char buf[1<<21],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
inline int max(reg int a,reg int b){
return a>b?a:b;
}
inline int min(reg int a,reg int b){
return a<b?a:b;
}
const int MAXN=5e5+5;
struct Interval{
int l,r;
inline Interval(reg int l=0,reg int r=0):l(min(l,r)),r(max(l,r)){
return;
}
};
struct Event{
int x,id;
inline Event(reg int x=0,reg int id=0):x(x),id(id){
return;
}
inline bool operator<(const Event& a)const{
return x<a.x;
}
};
int n,X,Y;
Interval a[MAXN];
Interval b[MAXN];
vector<int> V;
namespace SegmentTree{
#define lson ( (k) << 1 )
#define rson ( (k) << 1 | 1 )
#define mid ( ( (l) + (r) ) >> 1 )
struct Node{
int Max,cnt;
int tAdd;
#define Max(x) unit[(x)].Max
#define cnt(x) unit[(x)].cnt
#define tAdd(x) unit[(x)].tAdd
};
Node unit[MAXN<<3];
inline void pushup(reg int k){
if(Max(lson)>Max(rson))
Max(k)=Max(lson),cnt(k)=cnt(lson);
else if(Max(lson)==Max(rson))
Max(k)=Max(lson),cnt(k)=cnt(lson)+cnt(rson);
else
Max(k)=Max(rson),cnt(k)=cnt(rson);
return;
}
inline void build(reg int k,reg int l,reg int r){
tAdd(k)=0;
if(l==r){
Max(k)=0,cnt(k)=V[l+1]-V[l];
return;
}
build(lson,l,mid),build(rson,mid+1,r);
pushup(k);
return;
}
inline void add(reg int k,reg int val){
Max(k)+=val,tAdd(k)+=val;
return;
}
inline void pushdown(reg int k){
if(tAdd(k)){
add(lson,tAdd(k)),add(rson,tAdd(k));
tAdd(k)=0;
}
return;
}
inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){
if(L<=l&&r<=R){
add(k,val);
return;
}
pushdown(k);
if(L<=mid)
update(lson,l,mid,L,R,val);
if(R>mid)
update(rson,mid+1,r,L,R,val);
pushup(k);
return;
}
#undef lson
#undef rson
#undef mid
#undef Max
#undef cnt
#undef tAdd
}
inline int solve(reg int n,reg Interval a[],int X){
V.clear();
V.reserve((n+1)<<1);
for(reg int i=1;i<=n;++i){
V.push_back(a[i].l);
V.push_back(a[i].r);
}
V.push_back(0),V.push_back(X);
sort(V.begin(),V.end()),V.erase(unique(V.begin(),V.end()),V.end());
for(reg int i=1;i<=n;++i){
a[i].l=lower_bound(V.begin(),V.end(),a[i].l)-V.begin();
a[i].r=lower_bound(V.begin(),V.end(),a[i].r)-V.begin();
}
X=lower_bound(V.begin(),V.end(),X)-V.begin();
reg int s=V.size()-1;
vector<Event> E;
E.reserve(n<<1);
SegmentTree::build(1,0,s-1);
for(reg int i=1;i<=n;++i){
E.push_back(Event(a[i].l,i));
E.push_back(Event(a[i].r,-i));
SegmentTree::update(1,0,s-1,0,s-1,1);
SegmentTree::update(1,0,s-1,a[i].l,a[i].r-1,-1);
}
sort(E.begin(),E.end());
reg int ptr=0;
reg int res=0;
for(reg int i=0;i<s;++i){
while(ptr<(int)E.size()&&E[ptr].x<=i){
reg int id=abs(E[ptr].id);
if(E[ptr].id>0){
SegmentTree::update(1,0,s-1,0,s-1,-1);
SegmentTree::update(1,0,s-1,a[id].l,a[id].r-1,2);
}
else{
SegmentTree::update(1,0,s-1,0,s-1,1);
SegmentTree::update(1,0,s-1,a[id].l,a[id].r-1,-2);
}
++ptr;
}
res=max(res,SegmentTree::unit[1].cnt);
}
return res;
}
int main(void){
n=read(),X=read(),Y=read();
for(reg int i=1;i<=n;++i){
static int x1,y1,x2,y2;
x1=read(),y1=read(),x2=read(),y2=read();
a[i]=Interval(x1,x2);
b[i]=Interval(y1,y2);
}
reg int ansx=solve(n,a,X);
reg int ansy=solve(n,b,Y);
reg ll ans=1ll*ansx*ansy;
printf("%lld\n",ans);
return 0;
}
```
随机化算法的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
static char buf[1<<21],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
inline int max(reg int a,reg int b){
return a>b?a:b;
}
inline int min(reg int a,reg int b){
return a<b?a:b;
}
const int MAXN=5e5+5;
struct Interval{
int l,r;
inline Interval(reg int l=0,reg int r=0):l(min(l,r)),r(max(l,r)){
return;
}
};
int n,X,Y;
Interval a[MAXN];
Interval b[MAXN];
struct Event{
int x;
ull val;
inline Event(reg int x=0,reg ull val=0):x(x),val(val){
return;
}
inline bool operator<(const Event& a)const{
return x<a.x;
}
};
struct Segment{
int len;
ull val;
inline Segment(reg int len=0,reg ull val=0):len(len),val(val){
return;
}
inline bool operator<(const Segment& a)const{
return val<a.val;
}
};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int solve(reg int n,reg Interval a[],reg int X){
vector<Event> E;
E.reserve((n+1)<<1);
for(reg int i=1;i<=n;++i){
reg ull tag=rng();
E.push_back(Event(a[i].l,tag));
E.push_back(Event(a[i].r,tag));
}
E.push_back(Event(0,0));
E.push_back(Event(X,0));
sort(E.begin(),E.end());
vector<Segment> V;
reg ull val=0;
for(reg int i=0,siz=E.size();i<siz-1;++i){
val^=E[i].val;
if(E[i].x<E[i+1].x)
V.push_back(Segment(E[i+1].x-E[i].x,val));
}
sort(V.begin(),V.end());
reg ull las=0;
reg int sum=0;
reg int res=0;
for(reg int i=0,siz=V.size();i<siz;++i){
if(las==V[i].val)
sum+=V[i].len;
else
las=V[i].val,sum=V[i].len;
res=max(res,sum);
}
return res;
}
int main(void){
n=read(),X=read(),Y=read();
for(reg int i=1;i<=n;++i){
static int x1,y1,x2,y2;
x1=read(),y1=read(),x2=read(),y2=read();
a[i]=Interval(x1,x2);
b[i]=Interval(y1,y2);
}
reg int ansx=solve(n,a,X);
reg int ansy=solve(n,b,Y);
reg ll ans=1ll*ansx*ansy;
printf("%lld\n",ans);
return 0;
}
```