New Year and Conference

· · 个人记录

Codeforces 1284D

水平有限，如有疏漏，墙裂欢迎提出
思路，代码借鉴题解

Codeforces原题

简要题意：给定若干组区间，每一组区间由a,b两个区间组成，验证是否任意两组区间i,j的a[i],a[j]和b[i],b[j]的[重叠]情况相同

注意到我们可以使用$set$在$log(n)$的时间里确定一个区间$u$是否和另外一些区间$v[1],v[2]...v[k]$**存在**不重叠的情况，只需要看$u.start>min\{v[1].end,v[2].end...v[k].end\} \ ||\ u.end<max\{v[1].start,v[2].start...v[k].start\}$并且可以对$v[1],v[2]...v[k]$进行添加删减操作 我们考虑“定一挪一”，假设我们现在知道$a[i]$和$a[j_1],a[j_2]...a[j_k]$是相交的$^1$，问题就转化成了确定$b[i]$是否与$b[j_1],b[j_2]...b[j_k]$**存在**不重叠的情况 对于1操作：可以将所有$a[i].start,a[i].endd$一起排序，顺着走的时候遇到$a[i].start$就查询$b[i]$的重叠情况，然后将$b[i]$加入序列，否则将$b[i]$移除序列 $\color{Fuchsia}\text{Talk is Cheap, Show Me the Code!}

口胡谁都会，我要看代码

#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int MAX=100005;
struct node{
    int starta,enda,startb,endb;
}h[MAX];
struct point{
    int t,startb,endb;
    bool in;
    bool operator < (const point &a)const{
        if(a.t!=t)return a.t>t;
        else return a.in>in;      //这里要注意处在同一时间点的情况，要先删除过期的
    }
}t[MAX<<1];
int n,cnt;
multiset<int> start,endd;
multiset<int>::iterator it;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d %d %d %d",&h[i].starta,&h[i].enda,&h[i].startb,&h[i].endb);
    //整体思路，先固定a剧场时间是交的，如果b剧场没交(与a剧场能交的 那些演讲的b剧场时间)，那么就输出NO
    for(int i=1;i<=n;i++){
        t[++cnt]=point{h[i].starta,h[i].startb,h[i].endb,1};
        t[++cnt]=point{h[i].enda+1,h[i].startb,h[i].endb,0};      //在enda+1处要先将已经过期的删除，不要影响新开始的
    }
    sort(t+1,t+cnt+1);
    for(int i=1;i<=cnt;i++){
        if(t[i].in){
            if(!start.empty()){     //存在没有结束的演讲，也就是在a剧场它们交了
                it=start.end(),it--;
                if(t[i].endb<*it){      //存在在b剧场无法交的演讲，那么就NO
                    printf("NO");
                    return 0;
                }
                it=endd.begin();
                if(*it<t[i].startb){   //存在在b剧场无法交的演讲，那么就NO
                    printf("NO");
                    return 0;
                }
            }
            start.insert(t[i].startb),endd.insert(t[i].endb);
        }else{
            start.erase(start.find(t[i].startb));
            endd.erase(endd.find(t[i].endb));
        }
    }
    //再反之固定b剧场相交，操作相同
    cnt=0,start.clear(),endd.clear();
    for(int i=1;i<=n;i++){
        t[++cnt]=point{h[i].startb,h[i].starta,h[i].enda,1};
        t[++cnt]=point{h[i].endb+1,h[i].starta,h[i].enda,0};
    }
    sort(t+1,t+cnt+1);
    for(int i=1;i<=cnt;i++){
        if(t[i].in){
            if(!start.empty()){     //存在没有结束的演讲，也就是在b剧场它们交了
                it=start.end(),it--;
                if(t[i].endb<*it){      //存在在a剧场无法交的演讲，那么就NO
                    printf("NO");
                    return 0;
                }
                it=endd.begin();
                if(*it<t[i].startb){   //存在在a剧场无法交的演讲，那么就NO
                    printf("NO");
                    return 0;
                }
            }
            start.insert(t[i].startb),endd.insert(t[i].endb);
        }else{
            start.erase(start.find(t[i].startb));
            endd.erase(endd.find(t[i].endb));
        }
    }
    printf("YES");
    return 0;
}