A40206. 奇偶覆盖
填空题
困难
知识点
题目描述
奇偶覆盖
题目描述
在平面内有一些矩形，它们的两条边都平行于坐标轴。
我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。请问，被奇数个矩形覆盖和被偶数(> 2) 个矩形覆盖的点的面积分别是多少？
输入格式
输入的第一行包含一个整数 n，表示矩形的个数
接下来 n 行描述这些矩形，其中第i行包含四个整数 i,bi,,ti，表示矩形的两个对角坐标分别为(,b;),(r,s)。
输出格式
输出两行。
第一行包含一个整数，表示被奇数个矩形覆盖的点的面积
第二行包含一个整数，表示被偶数(> 2) 个矩形覆盖的点的面积
样例输入
3
1 1 3 3
2 2 4 4
3 3 5 5
样例输出
8
2
参考答案
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long ll;
using namespace std;
#define int long long
const int N = 300010;
vector<int>v;
struct Seg{
int x;
int l;
int r;
int k;
bool operator<(const Seg&w)const
{
if(x!=w.x)
return x<w.x;
return k>w.k;
}
}seg[N<<1];
struct node{
int l;
int r;
int len1;
int len2;
int cnt;
}tr[N<<2];
int get(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin();
}
void pushup(int u)
{
if(tr[u].cnt)
{
if(tr[u].cnt&1)
{
tr[u].len1=tr[u<<1].len2+tr[u<<1|1].len2;
tr[u].len2=tr[u<<1].len1+tr[u<<1|1].len1;
tr[u].len1+=v[tr[u].r+1]-v[tr[u].l]-tr[u].len1-tr[u].len2;
}
else
{
tr[u].len1=tr[u<<1].len1+tr[u<<1|1].len1;
tr[u].len2=tr[u<<1].len2+tr[u<<1|1].len2;
tr[u].len2+=v[tr[u].r+1]-v[tr[u].l]-tr[u].len1-tr[u].len2;
}
}
else if(tr[u].l!=tr[u].r)
{
tr[u].len1=tr[u<<1].len1+tr[u<<1|1].len1;
tr[u].len2=tr[u<<1].len2+tr[u<<1|1].len2;
}
else
{
tr[u].len1=tr[u].len2 = 0;
}
}
void build(int u,int l,int r)
{
tr[u] ={l,r};
if(l==r)
return ;
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
void mdf(int u,int l,int r,int k){
if(tr[u].l>=l && tr[u].r<=r)
{
tr[u].cnt+=k;
pushup(u);
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) mdf(u<<1,l,r,k);
if(r>mid) mdf(u<<1|1,l,r,k);
pushup(u);
}
signed main()
{
ios;
int n;
ll res1=0;
ll res2=0;
int cnt=0;
cin >> n;
for(int i=1;i<=n;i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
v.push_back(b);
v.push_back(d);
seg[cnt++]={a,b,d,1};
seg[cnt++]={c,b,d,-1};
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
build(1,0,(int)v.size()-2);
sort(seg,seg+cnt);
// return 0;
for(int i=0;i<cnt;i++)
{
if(i)
{
res1+=1ll*(seg[i].x-seg[i-1].x)*tr[1].len1;
res2+=1ll*(seg[i].x-seg[i-1].x)*tr[1].len2;
}
mdf(1,get(seg[i].l),get(seg[i].r)-1,seg[i].k);
}
cout<<res1<<endl<<res2<<endl;
return 0;
}
上一题
下一题