题目链接
题目大意
给你一些平行线和竖直线 问你在边长为1e6正方形内有几个密闭空间
题目思路
经过观察发现
密闭空间数量=每条线交点数量+两端都达到正方形边界的线数量+1
考虑运用扫描线思想
先将水平线存入
左端点为入点
右端点+1为出点
然后对于每一个水平线的端点 依靠x进行排序
对于每一条垂直线 依靠x进行排序
由于范围为1e6 不需要离散化
然后使用线段树进行操作
对于竖直线直接排序 逐个竖直线操作 对于x值小于等于当前竖直线的端点 进行updata
对于每条竖直线 i 的区间 加上这条区间的端点数量
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
struct xy{ll cnt=0;ll sum=0;int v,add;
}ans[maxn<<2];
struct node{int x,y,type;bool operator<(const node &xx)const {return x < xx.x;}
}a[maxn<<2];
struct nodeb{int up,down,x;int d;bool operator<(const nodeb &xx)const {return x<xx.x;}
}b[maxn<<2];
int n,m;
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
void pushup(int x,int l,int r)
{//if(l==r)return ;//ans[x].cnt=ans[ls(x)].cnt+ans[rs(x)].cnt;if(ans[x].cnt)ans[x].sum=1;//每一个节点是一个块而数组代表的值是每一个块左端点 else if(l>=r) ans[x].sum=0;else ans[x].sum=ans[ls(x)].sum+ans[rs(x)].sum;
}
void bt(int x,int l,int r)
{ans[x].cnt=0;ans[x].sum=0;if(l==r){ans[x].cnt=0;ans[x].sum=0;return ;}int mid=(l+r)/2;bt(ls(x),l,mid);bt(rs(x),mid+1,r);pushup(x,l,r);
}
void updata(int l,int r,int nl,int nr,int x,int k)
{//if(nl<nr)pushdown(x,nl,nr);int mid=(nl+nr)/2;if(nl>=l&&nr<=r){ans[x].cnt+=k;pushup(x,nl,nr);return ;}//pushdown(x,nl,nr);if(mid>=l){updata(l,r,nl,mid,ls(x),k);}if(mid<r){updata(l,r,mid+1,nr,rs(x),k);}pushup(x,nl,nr);}
ll query(ll l,ll r,ll nl,ll nr,ll x)
{ll res=0;ll mid=(nl+nr)/2;if(nl>=l&&nr<=r){return ans[x].sum;}//pushdown(x,nl,nr);if(mid>=l){res+=query(l,r,nl,mid,ls(x));}if(mid<r){res+=query(l,r,mid+1,nr,rs(x));}pushup(x,nl,nr);return res;}
int main()
{cin>>n>>m;ll ans=1;for(int i=1;i<=n;i++){int y,l,r;cin>>y>>l>>r;if(l==0&&r==1e6)ans++;a[i*2-1].x=l;a[i*2-1].y=y;a[i*2-1].type=1;a[i*2].x=r+1;a[i*2].y=y;a[i*2].type=-1;} bt(1,0,1e6);for(int i=1;i<=m;i++){int x,l,r;cin>>x>>l>>r;if(l==0&&r==1e6)ans++;b[i].x=x;b[i].down=l;b[i].up=r;} sort(b+1,b+m+1);sort(a+1,a+2*n+1);int anow=1;int j=anow;for(int i=1;i<=m;i++){int nowx=b[i].x;for(;j<=2*n&&a[j].x<=nowx;j++){updata(a[j].y,a[j].y,0,1e6,1,a[j].type);//cout<<j<<" "<<a[j].x<<endl;}ans+=query(b[i].down,b[i].up,0,1e6,1);//cout<<ans<<endl;}cout<<ans<<endl;return 0;
}