线段树+扫描线 NAIPC 2019 Intersecting Rectangles

你看看你有多菜,一点线段树的小小的运用,就不会写了;

题意:如果矩阵有交集,输出1,否则输出0(不包含内嵌);

思路:本题求交集,还得不包括内嵌的情况;

做过一道是求面积的题。跟这道类似,但在这里定义的方式跟那道题定的相反。

这里把下面的线定为了-1,上面定为了1;

在这道题里,先把矩阵的横向边按上下两种储存在一个结构体里,上的权值为1,下的为-1;

然后离散化这些坐标(为浮点数的时候和数太大的时候都要离散化,太大的话线段树放不下)

所以用离散化后的x1,x2去更新线段树;

当更新的边为下边的时候(权值为-1) 如果这个时候这个区间里已经有值了,证明相交;

当更新的边为上边的时候(权值为1) 如果这个时候这个区间里的值没有变为0,也证明相交;

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<math.h>
  4 #include<string.h>
  5 using namespace std;
  6 const int maxn=2e5+10;
  7 int cnt1;
  8 int cnt2,c[maxn];
  9 struct node
 10 {
 11     int l,r,h,id;
 12 }b[maxn];
 13 struct Node
 14 {
 15     int l,r,sum;
 16 }tree[maxn<<2];
 17 void init()
 18 {
 19     memset(c,0,sizeof(c));
 20     cnt1=cnt2=0;
 21 }
 22 bool cmp(node x,node y)
 23 {
 24     return x.h<y.h;
 25 }
 26 void build(int l,int r,int root)
 27 {
 28     tree[root].l=l,tree[root].r=r;
 29     tree[root].sum=0;
 30     if(l==r) return;
 31     int mid=l+r>>1;
 32     build(l,mid,root<<1);
 33     build(mid+1,r,root<<1|1);
 34 }
 35 void pushup(int root)
 36 {
 37     tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
 38 }
 39 void update(int base,int key,int root)
 40 {
 41     int l=tree[root].l,r=tree[root].r;
 42     if(l==r){
 43         tree[root].sum+=key;
 44         return;
 45     }
 46     int mid=l+r>>1;
 47     if(mid>=base) update(base,key,root<<1);
 48     else       update(base,key,root<<1|1);
 49     pushup(root);
 50 }
 51 int query(int L,int R,int root)
 52 {
 53     int l=tree[root].l,r=tree[root].r;
 54     if(l>=L&&r<=R){
 55         return tree[root].sum;
 56     }
 57     int mid=l+r>>1;
 58     int ans=0;
 59     if(mid>=L) ans+=query(L,R,root<<1);
 60     if(mid<R)  ans+=query(L,R,root<<1|1);
 61     return ans;
 62 }
 63 int main()
 64 {
 65     int n;
 66     while(scanf("%d",&n)!=EOF){
 67         init();
 68         for(int i=1;i<=n;i++){
 69             int x1,x2,y1,y2;
 70             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 71             b[++cnt1].l=x1,b[cnt1].r=x2,b[cnt1].h=y1,b[cnt1].id=-1;  //下边;
 72             b[++cnt1].l=x1,b[cnt1].r=x2,b[cnt1].h=y2,b[cnt1].id=1;   //上边;
 73             c[++cnt2]=x1;     //离散化坐标的预处理;
 74             c[++cnt2]=x2;     //离散化坐标的预处理;
 75         }
 76         sort(c+1,c+1+cnt2);   //离散化
 77         int len=unique(c+1,c+1+cnt2)-c-1;
 78         for(int i=1;i<=cnt1;i++){
 79             b[i].l=lower_bound(c+1,c+1+len,b[i].l)-c;   //将离散化后的值存储起来
 80             b[i].r=lower_bound(c+1,c+1+len,b[i].r)-c;
 81         }
 82         sort(b+1,b+1+cnt1,cmp);   //从小到排序,这里的操作弄不太清楚,只知道这样子之后
 83                                   //才能一步一步的去判断是否相交;
 84         build(1,cnt1,1);          //建树;
 85         int flag=0;
 86         for(int i=1;i<=cnt1;i++){
 87             if(b[i].id==-1){      //如果为下边
 88                 int tmp=query(b[i].l,b[i].r,1);
 89                 if(tmp){
 90                     flag=1;
 91                     break;
 92                 }
 93             }
 94             update(b[i].l,b[i].id,1);
 95             update(b[i].r,b[i].id,1);
 96             if(b[i].id==1){
 97                 int tmp=query(b[i].l,b[i].r,1);
 98                 if(tmp){
 99                     flag=1;
100                     break;
101                 }
102             }
103         }
104         printf("%d\n",flag);
105     }
106     return 0;
107 }

 

上一篇:算法刷题之七链表


下一篇:Codeforces - 1194E - Count The Rectangles - 不知道